`toposort`

Topological order of the nodes of a directed acyclic graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

N = toposort(G)

Returns the node indices of the digraph G in an order where every edge points from an earlier node to a later one.

Description

A topological order lists the nodes so that for each edge u -> v, node u appears before v. It exists only when the graph has no directed cycle, and is typically used to schedule tasks that depend on one another.

Several valid orders usually exist; toposort returns one of them. If the graph contains a cycle, the function raises an error.

Input arguments

G: A digraph object. It must have no directed cycles.

Output arguments

N: Row vector with the node indices in topological order.

Example

Ordering a small dependency graph

G = digraph([1 1 2 3], [2 3 4 4]);
N = toposort(G)

Output

N = 1×4

     1     3     2     4

toposort