This method outputs a HashTable with keys digraph, map and newDigraph, where digraph is the original digraph, map is the relation between old ordering and the new ordering of vertices and newDigraph is the Digraph with topologically sorted vertices. This method needs the input to be directed acyclic graph (DAG). S provides the preference given to the vertices in order to break ties and provide unique topological sorting to the DAG.
Permissible values of S are: "random", "max", "min", "degree".
S = "random" randomly sort the vertices of graph which have same precedence at any instance of the algorithm to break the ties.
S = "min" sort the vertices according to their indices (from low to high) to break the ties.
S = "max" sort the vertices according to their indices (from high to low) to break the ties.
S = "degree" sort the vertices according to their degree (from low to high) to break the ties.
i1 : G = digraph{{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}}
o1 = Digraph{0 => {} }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
o1 : Digraph
|
i2 : H = topSort G
o2 = SortedDigraph{digraph => Digraph{0 => {} } }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
map => HashTable{0 => 4}
1 => 6
2 => 3
3 => 5
4 => 2
5 => 1
newDigraph => Digraph{1 => {3, 4}}
2 => {4, 6}
3 => {5}
4 => {}
5 => {6}
6 => {}
o2 : SortedDigraph
|
i3 : H#digraph
o3 = Digraph{0 => {} }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
o3 : Digraph
|
i4 : H#map
o4 = HashTable{0 => 4}
1 => 6
2 => 3
3 => 5
4 => 2
5 => 1
o4 : HashTable
|
i5 : topSort(G,"min")
o5 = SortedDigraph{digraph => Digraph{0 => {} } }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
map => HashTable{0 => 3}
1 => 6
2 => 4
3 => 5
4 => 1
5 => 2
newDigraph => Digraph{1 => {3, 6}}
2 => {3, 4}
3 => {}
4 => {5}
5 => {6}
6 => {}
o5 : SortedDigraph
|
i6 : topSort(G,"max")
o6 = SortedDigraph{digraph => Digraph{0 => {} } }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
map => HashTable{0 => 6}
1 => 5
2 => 3
3 => 4
4 => 2
5 => 1
newDigraph => Digraph{1 => {3, 6}}
2 => {5, 6}
3 => {4}
4 => {5}
5 => {}
6 => {}
o6 : SortedDigraph
|
i7 : topSort(G,"random")
o7 = SortedDigraph{digraph => Digraph{0 => {} } }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
map => HashTable{0 => 5}
1 => 6
2 => 2
3 => 4
4 => 3
5 => 1
newDigraph => Digraph{1 => {2, 5}}
2 => {4}
3 => {5, 6}
4 => {6}
5 => {}
6 => {}
o7 : SortedDigraph
|
i8 : topSort(G,"degree")
o8 = SortedDigraph{digraph => Digraph{0 => {} } }
1 => {}
2 => {3}
3 => {1}
4 => {0, 1}
5 => {2, 0}
map => HashTable{0 => 3}
1 => 6
2 => 4
3 => 5
4 => 1
5 => 2
newDigraph => Digraph{1 => {3, 6}}
2 => {3, 4}
3 => {}
4 => {5}
5 => {6}
6 => {}
o8 : SortedDigraph
|