miraselleuch420's blog

By miraselleuch420, history, 5 weeks ago, In English

In this exercise you should write a function top_order (G) that uses depth-first search to determine a topological sorting of a simple directed graph, if one exists. The graph should be given as a list of objects of the Node type. Here every node object has as attributes - a list of successors of all nodes directly accessible from this node, - a string name and - a string color, which is set to "white" on initialization. It can be assumed that all nodes have different names. Input A list G of node objects is transferred that have a directed graph (G). Output If G has a topological sorting, the name values ​​of the nodes are sorted topologically as a list [v1 ,. . . , vn] returned. Otherwise the list [-1] is returned.

Sample calls 1 >>> n = Node () 2 >>> m = Node () 3 >>> n. name = ”source” 4 >>> m. Name = ”table” 5 >>> n. co l o r = m. co l o r = ”whi te” 6 >>> n. s u c c e s s o r s = [m] 7 >>> m. S u c c e s s o r s = [] 8 >>> G = [m, n] 9 >>> t o p o r d e r (G) 10 ['source', 'table'] 11 >>> n = Node () 12 >>> m = Node () 13 >>> n. name = "l i n k s" 14 >>> m. Name = "r e c h t s" 15 >>> n. co l o r = m. co l o r = ”whi te” 16 >>> n. s u c c e s s o r s = [m] 17 >>> m. S u c c e s s o r s = [n] 18 >>> G = [m, n] 19 >>> t o p o r d e r (G) 20 [−1]

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

example1:

1 >>> n = Node () 2 >>> m = Node () 3 >>> n. name = ”source” 4 >>> m. Name = ”table” 5 >>> n. co l o r = m. co l o r = ”whi te” 6 >>> n. s u c c e s s o r s = [m] 7 >>> m. S u c c e s s o r s = [] 8 >>> G = [m, n] 9 >>> t o p o r d e r (G) 10 ['source', 'table']

example 2:

11 >>> n = Node () 12 >>> m = Node () 13 >>> n. name = "l i n k s" 14 >>> m. Name = "r e c h t s" 15 >>> n. co l o r = m. co l o r = ”whi te” 16 >>> n. s u c c e s s o r s = [m] 17 >>> m. S u c c e s s o r s = [n] 18 >>> G = [m, n] 19 >>> t o p o r d e r (G) 20 [−1]