next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Graphs :: topSort

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

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

See also

Ways to use topSort :

For the programmer

The object topSort is a method function.