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

topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.

Synopsis

Description

This function outputs a list of vertices in a topologically sorted order of a 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 : topologicalSort G

o2 = {5, 4, 2, 0, 3, 1}

o2 : List
i3 : topologicalSort(G,"min")

o3 = {4, 5, 0, 2, 3, 1}

o3 : List
i4 : topologicalSort(G,"max")

o4 = {5, 4, 2, 3, 1, 0}

o4 : List
i5 : topologicalSort(G,"random")

o5 = {5, 2, 4, 3, 0, 1}

o5 : List
i6 : topologicalSort(G,"degree")

o6 = {4, 5, 0, 2, 3, 1}

o6 : List

See also

Ways to use topologicalSort :

For the programmer

The object topologicalSort is a method function.