petgraph::algo

Function toposort

Source 
pub fn toposort<G>(
    g: G,
    space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
) -> Result<Vec<G::NodeId>, Cycle<G::NodeId>>
where
    G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
Expand description

[Generic] Perform a topological sort of a directed graph.

toposort returns Err on graphs with cycles. To handle graphs with cycles, use the one of scc algorithms or DfsPostOrder instead of this function.

The implementation is iterative.

§Arguments

  • g: an acyclic directed graph.
  • space: optional DfsSpace. If space is not None, it is used instead of creating a new workspace for graph traversal.

§Returns

  • Ok: a vector of nodes in topological order: each node is ordered before its successors (if the graph was acyclic).
  • Err: Cycle if the graph was not acyclic. Self loops are also cycles this case.

§Complexity

  • Time complexity: O(|V| + |E|).
  • Auxiliary space: O(|V|).

where |V| is the number of nodes and |E| is the number of edges.