toposort

Topological order of directed acyclic graph

Syntax

n = toposort(G)

n = toposort(G,'Order',algorithm)

[n,H] = toposort(___)

Description

n = toposort(G) returns the topological order of the nodes in G such that i < j for every edge (n(i),n(j)) in G. The directed graph G cannot have any cycles.

n = toposort(G,'Order',algorithm) specifies the ordering algorithm. For example, toposort(G,'Order','stable') uses a stable ordering algorithm based on the lexicographical order of the nodes.

[n,H] = toposort(___) additionally returns directed graph H whose nodes are in the given topological order. You can use any of the input argument combinations in previous syntaxes.

Examples

Topological Sort of Nodes

Create and plot a graph that represents a progression of university-level Mathematics courses. An edge between two courses signifies a course requirement.

A = [0 1 1 0 0 0 0
     0 0 0 1 0 0 0
     0 1 0 1 0 0 1
     0 0 0 0 1 1 0
     0 0 0 0 0 0 0
     0 0 0 0 1 0 0
     0 0 0 0 1 0 0];
names = {'Calculus I','Linear Algebra','Calculus II', ...
    'Multivariate Calculus','Topology', ...
    'Differential Equations','Real Analysis'};
G = digraph(A,names);
plot(G)

Find the topological sorting of the courses to determine the proper order in which they should be completed.

N = toposort(G)

N = 1×7

     1     3     7     2     4     6     5

G.Nodes.Name(N,:)

ans = 7x1 cell
    {'Calculus I'            }
    {'Calculus II'           }
    {'Real Analysis'         }
    {'Linear Algebra'        }
    {'Multivariate Calculus' }
    {'Differential Equations'}
    {'Topology'              }

Stable Topological Sort

Create a directed graph using a logical adjacency matrix, and then plot the graph.

rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)

Find the topological sorting of the graph nodes. Even though G is already in topological order, (1 2 3 4 5 6 7 8 9 10), toposort reorders the nodes.

toposort(G)

ans = 1×10

     2     1     4    10     9     8     5     7     3     6

Specify Order as 'stable' to use the stable ordering algorithm, so that the sort orders the nodes with smaller indices first. Stable sort does not rearrange G if it is already in topological order.

toposort(G,'Order','stable')

ans = 1×10

     1     2     3     4     5     6     7     8     9    10

Input Arguments

G — Input graph

digraph object

Input graph, specified as a digraph object. G must be a directed acyclic graph. Use isdag to confirm that G does not contain cycles.

Use digraph to create a directed graph.

Example: G = digraph([1 2],[2 3])

algorithm — Ordering algorithm

'fast' (default) | 'stable'

Ordering algorithm, specified as 'fast' or 'stable':

'fast' (default)	Based on a depth-first search. A node is added to the beginning of the list after considering all of its descendants. If G is already in topological order, this method might still reorder the nodes.
'stable'	Based on lexicographical order. n(1) is the node with smallest index, n(2) the next smallest given n(1), and so on. If G is in topological order then H is unchanged and n is 1:numnodes(G).

Example: [n,H] = toposort(G,'Order','stable')

Output Arguments

n — Node indices

row vector

Node indices, returned as a row vector.

H — Topologically sorted graph

digraph object

Topologically sorted graph, returned as a digraph object. H is the same graph as G, but has the nodes reordered according to n.

More About

Topological Order

The topological ordering of a directed graph is an ordering of the nodes in the graph such that each node appears before its successors (descendants).

Consider a directed graph whose nodes represent tasks and whose edges represent dependencies that certain tasks must be completed before others. For such a graph, the topological sorting of the graph nodes produces a valid sequence in which the tasks could be performed.