topSort -- outputs a hashtable containing original digraph, new digraph with vertices topologically sorted and a map from vertices of original digraph to new digraph.

Synopsis

• Usage:
topSort(D)
topSort(D,S)
• Inputs:
• D, an instance of the type Digraph,
• S, ,
• Outputs:
• ,

Description

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 adyclic 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