Using PetGraph Graphmap to create sub graphs

I have a GraphMap from petgraph with a bunch of data building a parent child relationship between components.
I want to be able to be able to create a sub graph what is a collection of the child nodes and all of its dependants "downwards".

graphviz

For example for A in the image i would just want a graph of A with C3 as its a dependant.
I understand there is a few algorithms in the petgraph crate but none of them can be used to create a subgraph? I couldn't find any good examples and im a bit stuck

use crate::petgraph::dot::Dot;
use petgraph::prelude::DiGraphMap;
use petgraph;

fn main() {
    let mut g = DiGraphMap::new();
    g.add_edge("A", "B", -1);
    g.add_edge("A", "B2", -1);
    g.add_edge("A", "B3", -1);
    g.add_edge("B3", "C3", -1);
    
    g.add_edge("cA", "cB", -1);
    g.add_edge("cA", "cB2", -1);
    g.add_edge("cA", "cB3", -1);
    g.add_edge("cB3", "cC3", -1);
    
    g.add_edge("cB3", "C3", -1);
    

    
    println!("{}", format!("{}", Dot::new(&g)));
}

(Playground)

Output:

digraph {
    0 [ label = "A" ]
    1 [ label = "B" ]
    2 [ label = "B2" ]
    3 [ label = "B3" ]
    4 [ label = "C3" ]
    5 [ label = "cA" ]
    6 [ label = "cB" ]
    7 [ label = "cB2" ]
    8 [ label = "cB3" ]
    9 [ label = "cC3" ]
    0 -> 1 [ label = "-1" ]
    0 -> 2 [ label = "-1" ]
    0 -> 3 [ label = "-1" ]
    3 -> 4 [ label = "-1" ]
    5 -> 6 [ label = "-1" ]
    5 -> 7 [ label = "-1" ]
    5 -> 8 [ label = "-1" ]
    8 -> 9 [ label = "-1" ]
    8 -> 4 [ label = "-1" ]
}


Do you mean you want the subgraph consisting of [A, B, B2, B3, C3]?

Assuming so, a depth_first_search from A will visit the reachable nodes and edges. You could use this to build a new graph representing the reachable subgraph.

Playground.

1 Like