Topological sort of a petgraph graph for leaf parent chains - https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f8197a11c35adf125c68e61748ab5394

main.rs

// petgraph v0.6.5
use petgraph::graph::DiGraph;
use petgraph::visit::{EdgeRef, Topo};

fn main() {
    // Create a new directed graph
    let mut graph = DiGraph::new();

    // Add nodes and edges (similar to previous examples)
    let a1 = graph.add_node("A1");
    let b1 = graph.add_node("B1");
    let b2 = graph.add_node("B2");
    let c1 = graph.add_node("C1");
    let c2 = graph.add_node("C2");
    let c3 = graph.add_node("C3");
    let c4 = graph.add_node("C4");

    graph.add_edge(a1, b1, ());
    graph.add_edge(a1, b2, ());
    graph.add_edge(b1, c1, ());
    graph.add_edge(b1, c2, ());
    graph.add_edge(b2, c3, ());
    graph.add_edge(b2, c4, ());

    // Perform topological sort
    let mut topo = Topo::new(&graph);

    // Traverse the graph using topological order
    while let Some(node) = topo.next(&graph) {
        let mut stack = vec![node];
        let mut chain = vec![];

        // Traverse up the graph from the current node to the root
        while let Some(curr_node) = stack.pop() {
            chain.push(curr_node);
            if let Some(parent) = graph
                .edges_directed(curr_node, petgraph::Direction::Incoming)
                .next()
                .map(|edge| edge.source())
            {
                stack.push(parent);
            }
        }

        chain.reverse();
        println!(
            "Parent chain of {:?}: {:?}",
            graph[node],
            chain
                .iter()
                .map(|idx| graph[*idx])
                .collect::<Vec<_>>()
        );
    }
}