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

# topSort -- topologically sort the vertices of a digraph

- Usage:
    `topSort(D)`
    `topSort(D,S)`
- Inputs:
  - D, a digraph,
  - S, a string,
- Outputs:
  - a hash table,

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

## See also

- topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.
- SortedDigraph -- hashtable used in topSort
- newDigraph -- key used in the output of topSort

## Ways to use topSort:

- `topSort(Digraph)`
- `topSort(Digraph,String)`

## For the programmer

The object topSort is a method function.

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