from collections import deque import random def is_topsorted(V,E,sequence): sequence = list(sequence) #from wikipedia definition of top-sort #for every edge uv, u comes before v in the ordering for u,v in E: ui = sequence.index(u) vi = sequence.index(v) if not (ui < vi): return False return True #the collection_type should behave like a set: # it must have add(), pop() and __len__() as members. def topsort(V,E,collection_type): #out edges INS = {} #in edges OUTS = {} for v in V: INS[v] = set() OUTS[v] = set() #for each edge u,v, for u,v in E: #record the out-edge from u OUTS[u].add(v) #record the in-edge to v INS[v].add(u) #1. Store all vertices with indegree 0 in a queue #We will start topvertices = collection_type() for v,in_vertices in INS.iteritems(): if len(in_vertices) == 0: topvertices.add(v) result = [] #4. Perform steps 2 and 3 while the queue is not empty. while len(topvertices) != 0: #2. get a vertex U and place it in the sorted sequence (array or another queue). u = topvertices.pop() result.append(u) #3. For all edges (U,V) update the indegree of V, # and put V in the queue if the updated indegree is 0. for v in OUTS[u]: INS[v].remove(u) if len(INS[v]) == 0: topvertices.add(v) return result class stack_collection: def __init__(self): self.data = list() def add(self,v): self.data.append(v) def pop(self): return self.data.pop() def __len__(self): return len(self.data) class queue_collection: def __init__(self): self.data = deque() def add(self,v): self.data.append(v) def pop(self): return self.data.popleft() def __len__(self): return len(self.data) class random_orderd_collection: def __init__(self): self.data = [] def add(self,v): self.data.append(v) def pop(self): result = random.choice(self.data) self.data.remove(result) return result def __len__(self): return len(self.data) """ Poor man's graph generator. Requires networkx. Don't make the edge_count too high compared with the vertex count, otherwise it will run for a long time or forever. """ def nx_generate_random_dag(vertex_count,edge_count): import networkx as nx V = range(1,vertex_count+1) random.shuffle(V) G = nx.DiGraph() G.add_nodes_from(V) while nx.number_of_edges(G) < edge_count: u = random.choice(V) v = random.choice(V) if u == v: continue for tries in range(2): G.add_edge(u,v) if not nx.is_directed_acyclic_graph(G): G.remove_edge(u,v) u,v = v,u V = G.nodes() E = G.edges() assert len(E) == edge_count assert len(V) == vertex_count return V,E def main(): graphs = [] V = [1,2,3,4,5] E = [(1,2),(1,5),(1,4),(2,4),(2,5),(3,4),(3,5)] graphs.append((V,E)) """ Uncomment this section if you have networkx. This will generate 3 random graphs. """ """ for i in range(3): G = nx_generate_random_dag(30,120) V,E = G print 'random E:',E graphs.append(G) """ #This graph was generated using nx_generate_random_dag() from above V = range(1,31) E = [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23), (1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19), (2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26), (5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29), (7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12), (9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28), (9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5), (12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24), (14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19), (15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23), (16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28), (18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29), (21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10), (24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3), (26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4), (29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7), (30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)] graphs.append((V,E)) #add other graphs here for testing for G in graphs: V,E = G #sets in python are unordered but in practice their hashes usually order integers. top_set = topsort(V,E,set) top_stack = topsort(V,E,stack_collection) top_queue = topsort(V,E,queue_collection) random_results = [] for i in range(0,10): random_results.append(topsort(V,E,random_orderd_collection)) print 'V: ', V print 'E: ', E print 'top_set ({0}): {1}'.format(is_topsorted(V,E,top_set),top_set) print 'top_stack ({0}): {1}'.format(is_topsorted(V,E,top_stack),top_stack) print 'top_queue ({0}): {1}'.format(is_topsorted(V,E,top_queue),top_queue) for random_result in random_results: print 'random_result ({0}): {1}'.format(is_topsorted(V,E,random_result),random_result) assert is_topsorted(V,E,random_result) assert is_topsorted(V,E,top_set) assert is_topsorted(V,E,top_stack) assert is_topsorted(V,E,top_queue) main()
Standard input is empty
V: [1, 2, 3, 4, 5] E: [(1, 2), (1, 5), (1, 4), (2, 4), (2, 5), (3, 4), (3, 5)] top_set (True): [1, 2, 3, 4, 5] top_stack (True): [3, 1, 2, 5, 4] top_queue (True): [1, 3, 2, 4, 5] random_result (True): [1, 2, 3, 5, 4] random_result (True): [1, 2, 3, 5, 4] random_result (True): [1, 3, 2, 4, 5] random_result (True): [3, 1, 2, 4, 5] random_result (True): [1, 2, 3, 5, 4] random_result (True): [3, 1, 2, 4, 5] random_result (True): [1, 2, 3, 4, 5] random_result (True): [1, 2, 3, 5, 4] random_result (True): [1, 2, 3, 5, 4] random_result (True): [1, 2, 3, 5, 4] V: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] E: [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23), (1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19), (2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26), (5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29), (7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12), (9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28), (9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5), (12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24), (14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19), (15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23), (16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28), (18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29), (21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10), (24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3), (26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4), (29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7), (30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)] top_set (True): [16, 1, 21, 30, 7, 13, 6, 9, 14, 20, 29, 2, 15, 25, 17, 4, 8, 24, 28, 26, 19, 12, 10, 18, 3, 22, 11, 5, 23, 27] top_stack (True): [16, 1, 21, 30, 7, 13, 6, 9, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] top_queue (True): [1, 16, 21, 30, 7, 13, 9, 6, 14, 20, 29, 2, 15, 25, 17, 4, 8, 24, 12, 28, 26, 19, 10, 18, 3, 22, 11, 5, 27, 23] random_result (True): [1, 21, 30, 16, 7, 13, 9, 14, 6, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [1, 16, 21, 30, 7, 13, 9, 6, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 27, 23] random_result (True): [1, 16, 21, 30, 7, 13, 6, 9, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 27, 23] random_result (True): [16, 1, 21, 30, 7, 13, 9, 14, 6, 20, 29, 2, 15, 25, 17, 4, 8, 24, 12, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [1, 21, 16, 30, 7, 13, 9, 14, 6, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [16, 1, 21, 30, 7, 13, 6, 9, 14, 20, 29, 2, 15, 25, 17, 4, 8, 24, 12, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [1, 21, 30, 7, 16, 13, 6, 9, 14, 20, 29, 2, 15, 25, 17, 4, 8, 24, 12, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [1, 21, 16, 30, 7, 13, 9, 6, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [1, 21, 16, 30, 7, 13, 9, 6, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27] random_result (True): [16, 1, 21, 30, 7, 13, 9, 6, 14, 20, 29, 2, 15, 25, 17, 4, 8, 12, 24, 28, 26, 19, 10, 18, 3, 22, 11, 5, 23, 27]