Class DepthFirstOrders

src/graph/directed/order.rs:10–18

The DepthFirstOrder represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder. This implementation uses depth-first search.

/// postorder.
/// This implementation uses depth-first search.
pub struct DepthFirstOrders {
    pre_order: Vec<usize>,  // vertices in preorder
    pre: Vec<usize>,        // pre[v] = preorder number of v
    pre_counter: usize,     // counter or preorder numbering
    post_order: Vec<usize>, // vertices in postorder
    post: Vec<usize>,       // post[v] = postorder number of v
    post_counter: usize,    // counter for postorder numbering
    marked: Vec<bool>,      // marked[v] = has v been marked in dfs?
}

impl DepthFirstOrders {
    /// Returns the vertices in preorder.