Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node:
- def __init__(self, id, color):
- self.id = id # int
- self.color = color # string
- self.adjacentNodes = set()
- # actually this function return the unique string associated with the graph
- # that will be hashed with the function hash() in a second moment
- def new_hash(graph, queue=[]): # graph: list of Node
- if not queue: # first call: find the root of the tree
- graph.sort(key = lambda x: (len(x.adjacentNodes), x.color), reverse=True)
- groups = itertools.groupby(graph, key = lambda x: (len(x.adjacentNodes), x.color))
- roots = []
- result_hash = ''
- for _, group in groups:
- roots = [x for x in group]
- break # I just need the first (the candidates roots)
- temp_hashes = []
- for node in roots:
- temp_queue = [node.id]
- temp_hash = node.color + str(len(node.adjacentNodes)) + str(temp_queue.index(node.id))
- temp_hash += new_hash(list(node.adjacentNodes), temp_queue)
- temp_hashes.append((node, temp_hash, temp_queue))
- temp_hashes.sort(key = lambda x: x[1], reverse=True)
- queue = temp_hashes[0][2]
- result_hash += temp_hashes[0][1]
- result_hash += new_hash(list(temp_hashes[0][0].adjacentNodes), queue=queue)
- else:
- graph.sort(key = lambda x: (len(x.adjacentNodes), x.color), reverse=True)
- groups = itertools.groupby(graph, key = lambda x: (len(x.adjacentNodes), x.color))
- grouped_nodes = []
- result_hash = ''
- for _, group in groups:
- grouped_nodes.append([x for x in group])
- for group in grouped_nodes:
- while len(group) > 0:
- temp_hashes = []
- for node in group:
- if node.id in queue:
- temp_hash = node.color + str(len(node.adjacentNodes)) + str(queue.index(node.id))
- temp_hashes.append((node, temp_hash, queue))
- else:
- temp_queue = queue[:]
- temp_queue.append(node.id)
- temp_hash = node.color + str(len(node.adjacentNodes)) + str(temp_queue.index(node.id))
- temp_hash += new_hash(list(node.adjacentNodes), queue=temp_queue)
- temp_hashes.append((node, temp_hash, temp_queue))
- temp_hashes.sort(key = lambda x: x[1], reverse=True)
- queue = temp_hashes[0][2]
- result_hash += temp_hashes[0][1]
- group.remove(temp_hashes[0][0])
- return result_hash
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement