Struct MDTree

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

A modular decomposition tree.

The tree is non-empty and rooted.

A node in the tree is a strong module of the original graph. The modules have a type: Prime, Series, or Parallel for inner nodes and Node(_) for leaf nodes.

The nodes at the leaves are exactly the nodes of the original graph.

The leaves of a subtree rooted at a module are the set of nodes of the original graph that are a strong module. They can be obtained by MDTree::nodes.

Implementations

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

pub fn is_cograph(&self) -> bool

Returns whether the original graph is a cograph.

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

pub fn twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_

Returns an iterator for the set of nodes of the original graph that are twins.

Two nodes are twins when they have the same neighborhood excluding themselves, i.e. N(u) \ {v} = N(v) \ {u}.

Twins are either true or false twins. See MDTree::true_twins and MDTree::false_twins.

use petgraph::graph::{NodeIndex, UnGraph};
use modular_decomposition::modular_decomposition;

// a K_2 + 2 K_1
let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
let md = modular_decomposition(&graph)?;

let mut twins: Vec<_> = md.twins().collect();
twins.iter_mut().for_each(|nodes| nodes.sort());
twins.sort();
assert_eq!(twins, [[NodeIndex::new(0), NodeIndex::new(1)], [NodeIndex::new(2), NodeIndex::new(3)]]);

pub fn true_twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_

Returns an iterator for the set of nodes of the original graph that are true twins.

Two nodes are true twins when they have the same closed neighborhood, i.e. N(u) = N(v).

use petgraph::graph::{NodeIndex, UnGraph};
use modular_decomposition::modular_decomposition;

// a K_2 + 2 K_1
let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
let md = modular_decomposition(&graph)?;

let mut twins: Vec<_> = md.true_twins().collect();
twins.iter_mut().for_each(|nodes| nodes.sort());
twins.sort();
assert_eq!(twins, [[NodeIndex::new(2), NodeIndex::new(3)]]);

pub fn false_twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_

Returns an iterator for the set of nodes of the original graph that false twins.

Two nodes are false twins when they have the same open neighborhood, i.e. N(u) u {u} = N(v) u {v}.

use petgraph::graph::{NodeIndex, UnGraph};
use modular_decomposition::modular_decomposition;

// a K_2 + 2 K_1
let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
let md = modular_decomposition(&graph)?;

let mut twins: Vec<_> = md.false_twins().collect();
twins.iter_mut().for_each(|nodes| nodes.sort());
twins.sort();
assert_eq!(twins, [[NodeIndex::new(0), NodeIndex::new(1)]]);

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

pub fn strong_module_count(&self) -> usize

Return the number of strong modules in the modular decomposition tree.

These are all the nodes of the tree.

pub fn root(&self) -> ModuleIndex

Return the root module index.

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

Access the ModuleKind of a module.

If the module does not exist, return None.

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

Return an iterator yielding references to ModuleKinds for all modules.

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

Return an iterator for the children of a module.

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

Return the nodes of a module.

The nodes represent nodes of the original graph and not modules of the MDTree. These are the leaves of the subtree rooted at module in the MDTree.

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);
}

Trait Implementations

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

fn clone(&self) -> MDTree<NodeId>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

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

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.