Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save matthewjberger/9ebc5c368b422f7fea5643890935dd50 to your computer and use it in GitHub Desktop.
Save matthewjberger/9ebc5c368b422f7fea5643890935dd50 to your computer and use it in GitHub Desktop.
// petgraph v0.6.5
use petgraph::graph::{NodeIndex, DiGraph};
fn number_children(graph: &DiGraph<(), ()>, parent: NodeIndex, depth: usize) -> Vec<(NodeIndex, usize, usize)> {
let mut tree = Vec::new();
let mut index = 0;
// Start numbering the children from index 0
for child in graph.neighbors(parent) {
tree.push((child, index, depth));
index += 1;
}
// Recursively number children of children
for child in graph.neighbors(parent) {
tree.extend(number_children(graph, child, depth + 1));
}
tree
}
fn main() {
let mut graph = DiGraph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
let i = graph.add_node(());
let j = graph.add_node(());
graph.add_edge(a, b, ());
graph.add_edge(a, c, ());
graph.add_edge(b, d, ());
graph.add_edge(b, e, ());
graph.add_edge(c, f, ());
graph.add_edge(c, g, ());
graph.add_edge(d, h, ());
graph.add_edge(d, i, ());
graph.add_edge(f, j, ());
let tree = number_children(&graph, a, 0);
for (node, id, depth) in tree {
println!("{:indent$}{:?} has ID {}", "", node, id, indent = depth * 2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment