Macaulay2 » Documentation
Packages » Graphs :: topologicalSort
next | previous | forward | backward | up | index | toc

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

- Usage:
    `topologicalSort(D,S)`
    `topologicalSort(D)`
- Inputs:
  - D, a digraph,
  - S, a string,
- Outputs:
  - a list,

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

- topSort -- topologically sort the vertices of a digraph

## Ways to use topologicalSort:

- `topologicalSort(Digraph)`
- `topologicalSort(Digraph,String)`

## For the programmer

The object topologicalSort is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Graphs.m2:5285:0.