Struct modular_decomposition::MDTree

source ·

pub struct MDTree<NodeId: Copy + PartialEq> { /* private fields */ }

Expand description

A modular decomposition tree. The tree contains at least one node.

Implementations§

source §

impl<NodeId: Copy + PartialEq> MDTree<NodeId>

source

pub fn node_count(&self) -> usize

Return the number of nodes in the modular decomposition tree.

source

pub fn root(&self) -> ModuleIndex

Return the root node index.

source

pub fn module_kind(&self, module: ModuleIndex) -> Option<&ModuleKind<NodeId>>

Access the ModuleKind of a module.

If the module does not exist, return None.

source

pub fn module_kinds(&self) -> impl Iterator<Item = &ModuleKind<NodeId>>

Return an iterator yielding references to ModuleKinds for all nodes.

source

pub fn children( &self, module: ModuleIndex, ) -> impl Iterator<Item = ModuleIndex> + '_

Return an iterator for the children of a node.

source

pub fn into_digraph(self) -> DiGraph<ModuleKind<NodeId>, ()>

Convert to DiGraph.

This allows the use of petgraph algorithms. Use ModuleIndex::index and petgraph::graph::NodeIndex::new to convert the root index.

use petgraph::graph::{NodeIndex, UnGraph};
use petgraph::visit::Dfs;
use modular_decomposition::{modular_decomposition, ModuleKind};

let graph = UnGraph::<(), ()>::from_edges([(0, 2), (1, 2), (2, 3), (3, 4), (3, 5)]);
let md = modular_decomposition(&graph)?;

let root = NodeIndex::new(md.root().index());
let digraph = md.into_digraph();

let mut dfs = Dfs::new(&digraph, root);
let mut node_order = vec![];
while let Some(node) = dfs.next(&digraph) { node_order.push(*digraph.node_weight(node).unwrap()); }

let expected_node_order = [
    ModuleKind::Prime,
    ModuleKind::Node(NodeIndex::new(2)),
    ModuleKind::Parallel,
    ModuleKind::Node(NodeIndex::new(0)),
    ModuleKind::Node(NodeIndex::new(1)),
    ModuleKind::Node(NodeIndex::new(3)),
    ModuleKind::Parallel,
    ModuleKind::Node(NodeIndex::new(4)),
    ModuleKind::Node(NodeIndex::new(5)),
];
assert_eq!(node_order, expected_node_order);

Examples found in repository ?

examples/adj_vector_graph.rs (line 74)

fn main() {
    let graph = Graph::from_edges([(0, 1), (1, 2), (2, 3)]);
    let tree = modular_decomposition(&graph).map(|tree| tree.into_digraph()).unwrap_or_default();
    println!("{:?}", Dot::with_config(&tree, &[EdgeNoLabel]));

    let mut factorizing_permutation = Vec::new();
    let root = tree.externals(Incoming).next().unwrap();
    let mut dfs = Dfs::new(&tree, root);
    while let Some(node) = dfs.next(&tree) {
        if let ModuleKind::Node(u) = tree[node] {
            factorizing_permutation.push(u);
        }
    }
    let factorizing_permutation: Vec<_> = factorizing_permutation.to_vec();
    println!("{:?}", factorizing_permutation);
}