next | previous | forward | backward | up | index | toc

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

## Synopsis

• Usage:
topologicalSort(D,S)
topologicalSort(D)
• Inputs:
• D, ,
• S, ,
• Outputs:

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