Module tree_from_parent_vector 

Parent-vector tree/forest decoder (ALGO-CN-017).

Counterpart of igraph_tree_from_parent_vector() in references/igraph/src/constructors/trees.c:70-161.

A parent vector of length n represents a rooted forest on n vertices: parents[v] is the vertex id of v’s parent, or any negative value to mark v as a root (no parent). The decoder walks every vertex once and follows its parent chain, emitting one edge per (v, parent[v]) link. Per-round colouring detects both self-loops (parent[v] == v) and longer cycles (v → … → v) in linear time.

TreeMode is re-exported from crate::kary_tree and controls arc orientation:

• TreeMode::Out — directed, every arc flows parent → child.
• TreeMode::In — directed, every arc flows child → parent.
• TreeMode::Undirected — undirected, raw (child, parent) stored as canonical (min, max) by Graph::add_edges.

The output is guaranteed to be a forest (or a tree, when there is exactly one root); validation rejects negative-or-large parent ids, self-loops, and longer cycles up-front.

Time complexity: O(n) where n = parents.len(). Each vertex is visited exactly once across all rounds (once as i, once as the cascading u).

Functions

tree_from_parent_vector

Decode a parent vector into the tree or forest it represents.