import copy
#Graphs are implemented as adjacency lists
class Graph:
def __init__(self, number_of_vertices):
self.vertices = [i for i in range(number_of_vertices)]
self.edges = [ [] for i in self.vertices]
def set_edges(self, edges):
for edge in edges:
self.edges[edge[0]].append(edge[1])
self.edges[edge[1]].append(edge[0])
def add_vertices(self, number):
current_length = len(self.vertices)
for i in range(number):
self.vertices.append(current_length)
self.edges.append([])
current_length = current_length + 1
#returns edge list
def return_edge_tuples(self):
edge_tuples = []
for i in self.vertices:
for j in self.edges[i]:
if j > i:
edge_tuples.append( (i,j) )
return edge_tuples
#returns a list of non-adjacent vertices
def return_non_edge_tuples(self):
non_edge_tuples = []
for i in self.vertices:
for j in list(set(self.vertices) - set(self.edges[i]) ):
if j > i:
non_edge_tuples.append( (i,j) )
return non_edge_tuples
#checks if subgraph is a clique
def is_clique(G, subset):
is_clique = True
for i in list(subset):
if not is_clique:
break
for j in list(subset):
if j > i and j not in G.edges[i]:
is_clique = False
break
return is_clique
#The following function returns a 1 if G decomposes as a join of two subgraph, each of which containing a pair of non-adjacent vertices
#The function returns a 2 if G is the join of a clique with a pair of non-adjacent vertices.
#Function returns a 3 if graph is a clique. 0 is returned for any other graph
def is_trivial_graph(G):
comps = get_join_decomp(G)
non_trivial_comps = 0
z_comps = 0
for c in comps:
if not is_clique(G, c):
non_trivial_comps = non_trivial_comps + 1
if len(c) == 2:
z_comps = z_comps + 1
if non_trivial_comps >= 2:
return 1
elif non_trivial_comps == 1 and z_comps == 1:
return 2
elif non_trivial_comps == 0:
return 3
else:
return 0
#returns a join decomposition of G
def get_join_decomp(G):
complement_edges = []
vertices_in_a_comp = set()
for v in G.vertices:
complement_edges.append(set(G.vertices) - set(G.edges[v]) )
comps = []
for v in G.vertices:
if v not in vertices_in_a_comp:
new_comp = set({v})
vertices_in_a_comp.add(v)
neighbors = complement_edges[v]
while(len(neighbors) > 0):
new_neighbors = set()
for n in neighbors:
if n not in new_comp:
new_comp.add(n)
vertices_in_a_comp.add(n)
new_neighbors = new_neighbors.union(set(complement_edges[n]))
neighbors = new_neighbors
comps.append(new_comp)
return comps
#The following function returns all joins of the form J1 * J2, where J1 is exactly two non-adjacent vertices and J2 is not empty.
#This is enough for the purposes of calculating the hypergraph index when G is not a join
def return_joins(G):
join_graphs = []
non_edges = G.return_non_edge_tuples()
for pair in non_edges:
link1 = set(G.edges[pair[0]])
link2 = set(G.edges[pair[1]])
link_intersect = link1.intersection(link2)
if len(link_intersect) > 0:
this_graph = set({pair[0], pair[1]})
this_graph = this_graph.union(link_intersect)
join_graphs.append(this_graph)
return join_graphs
#The following function accepts as imput a graph and a set of hyperedges (components). It returns the next lambda hypergraph associated to G.
def create_next_lambda(G, components):
#copy of components list is made to be manipulated
components_copy = list(components)
#new components for the next lambda graph
new_comp_list = []
#The following finds components C that are connected to root by a chain of components whose pairwise intersection contains at least two non-adjacent vertices.
for root in components:
#check if root does not already belong to a new component
if root in components_copy:
#these are components connected to the root
connected_components = [root]
#these are the recently found components connected to root. All their neighbors must be found as well.
current_components = [root]
#this is the list of things connected to the current_components. After an iteration, current_components is set equal to new_components, and new_components is cleared.
new_components = []
while current_components:
for comp in current_components:
#New copy of components list to be iterated on. This is necessary as components_copy gets modified in this loop
components_copy2 = list(components_copy)
for comp2 in components_copy2:
#check if intersection of comp and comp2 is not a clique (i.e., contains two non-adjacent vertices)
intersect = comp.intersection(comp2)
clique = is_clique(G, intersect)
if(not clique):
components_copy.remove(comp2)
new_components.append(comp2)
for c in new_components:
connected_components.append(c)
current_components = new_components
new_components = []
new_comp = set()
for c in connected_components:
new_comp = new_comp.union(c)
new_comp_list.append(new_comp)
return new_comp_list
#find the hypergraph index
def get_hyp_index(G):
is_join = False
hyp_index = 0
trivial_number = is_trivial_graph(G)
if trivial_number == 1:
return 0
elif trivial_number == 2:
return 'infinity'
elif trivial_number == 3:
return 'graph is a clique'
hyp_edges = return_joins(G)
full_support = False
is_infinite = False
while not full_support and not is_infinite:
hyp_index = hyp_index + 1
new_hyp_edges = create_next_lambda(G, hyp_edges)
#check if hyperedges remained the same in next hypergraph
if(hyp_edges == new_hyp_edges):
is_infinite = True
hyp_index = 'infinity'
#check if some hyperedge contains every vertex of G
else:
hyp_edges = new_hyp_edges
for e in hyp_edges:
if len(e) == len(G.vertices):
full_support = True
return hyp_index
#The following function takes all pairs of non-adjacent vertices, and decides if they are a rank n pair for all n
#The function returns a list of lists, ranked_pairs. The ranked_pairs[n] are the rank n pairs. ranked_pairs[0] are every pair of non-adjacent vertices
#The function does not yet support infinite ended groups.
def get_rank_n_pairs(G):
#get list of non-adjacent vertices
non_edges = G.return_non_edge_tuples()
high_rank = []
ranked_pairs = []
#first we find all non-adjacent pairs that are not contained in a square. These get included in the high_rank list
for pair in non_edges:
link1 = set(G.edges[pair[0]])
link2 = set(G.edges[pair[1]])
link_intersect = link1.intersection(link2)
clique = is_clique(G, link_intersect)
if clique:
high_rank.append(pair)
#all non-adjacent pairs
ranked_pairs.append(non_edges)
if len(high_rank) > 0:
#pairs not contained in a square
ranked_pairs.append(high_rank)
#take pairs in high rank, and try to determine if they are rank n.
while len(high_rank) > 0:
new_high_rank = []
this_rank_pairs = []
for pair in high_rank:
link1 = set(G.edges[pair[0]])
link2 = set(G.edges[pair[1]])
is_higher_rank1 = True
is_higher_rank2 = True
for i in link1:
for j in link1:
if (j > i) and (i, j) in non_edges and (i,j) not in high_rank:
is_higher_rank1 = False
if is_higher_rank1 == False:
for i in link2:
for j in link2:
if (j > i) and (i, j) in non_edges and (i,j) not in high_rank:
is_higher_rank2 = False
#if all pairs of non-adjacent vertices in link1 or link2 are in high_rank, then this pair must be higher rank
if is_higher_rank1 or is_higher_rank2:
new_high_rank.append(pair)
high_rank = new_high_rank
if len(high_rank) > 0:
ranked_pairs.append(high_rank)
return ranked_pairs
#returns a list of the first "list_size" graphs of the examples in Dani-Thomas, beginning with the square.
#Graph i in this list has polynomial divergence of degree i+1 and is thick of order exactly i
def get_dt_examples(list_size):
#list storing dt example graphs
dt_examples = []
for j in range(0,list_size):
#square example
if j==0:
square = Graph(4)
edge_list = [(0,2),(0,3),(1,2),(1,3)]
square.set_edges(edge_list)
dt_examples.append(square)
#quadratic example
elif j == 1:
quad = Graph(6)
#list of edges
edge_list = [(0,2),(0,3) ,(0,4),(1,2),(1,3),(1,4),(5,2),(5,3)]
#add list of edges
quad.set_edges(edge_list)
dt_examples.append(quad)
elif j == 2:
G = copy.deepcopy(dt_examples[j-1])
G.add_vertices(1)
G.set_edges([(4,6),(5,6)])
dt_examples.append(G)
else:
G = copy.deepcopy(dt_examples[j-1])
G.add_vertices(2)
number_of_vertices = len(G.vertices)
new_vertex1 = number_of_vertices - 2
new_vertex2 = number_of_vertices - 1
G.set_edges([(new_vertex1, 0), (new_vertex1, 1), (new_vertex2, number_of_vertices-3), (new_vertex2, new_vertex1)] )
dt_examples.append(G)
return dt_examples
def group_summary(G):
hyp_index = get_hyp_index(G)
if str(hyp_index) == 'infinity':
return "The graph is relatively hyperbolic and the hypergraph index is infinite."
elif hyp_index == 0:
return "Divergence is linear. Thick of order 0. Hypergraph index is 0"
elif hyp_index == 1:
return "Divergence is quadratic. Thick of order: 1. Hypergraph index is 1"
else:
rank_n_pairs = get_rank_n_pairs(G)
divergence_lower_bound = max(len(rank_n_pairs),3)
divergence_upper_bound = hyp_index + 1
if (hyp_index + 1) == divergence_lower_bound:
return "Divergence is a polynomial of degree "+ str(divergence_lower_bound) + ". Thick of order " + str(hyp_index) + ". Hypergraph index is " + str(hyp_index) + "."
else:
return "Divergence is bound below by a polynomial of degree "+ str(divergence_lower_bound) + " and is bound above by a polynomial of degree " + str(divergence_upper_bound) + ". Thick of order between " + str((divergence_lower_bound - 1)) + " and " + str(hyp_index) + ". Hypergraph index is " + str(hyp_index) + "."