Package org.jgrapht.alg.decomposition

Class DulmageMendelsohnDecomposition<V,E>

java.lang.Object

org.jgrapht.alg.decomposition.DulmageMendelsohnDecomposition<V,E>

Type Parameters:

V - Vertex type

E - Edge type

public class DulmageMendelsohnDecomposition<V,E>
extends Object

This class computes a Dulmage-Mendelsohn Decomposition of a bipartite graph. A Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. This particular implementation is capable of computing both a coarse and a fine Dulmage-Mendelsohn Decomposition.

The Dulmage-Mendelsohn Decomposition is based on a maximum-matching of the graph $G$. This implementation uses the Hopcroft-Karp maximum matching algorithm by default.

A coarse Dulmage-Mendelsohn Decomposition is a partitioning into three subsets. Where $D$ is the set of vertices in G that are not matched in the maximum matching of $G$, these subsets are:

• The vertices in $D \cap U$ and their neighbors
• The vertices in $D \cap V$ and their neighbors
• The remaining vertices

A fine Dulmage-Mendelsohn Decomposition further partitions the remaining vertices into strongly-connected sets. This implementation uses Kosaraju's algorithm for the strong-connectivity analysis.

The Dulmage-Mendelsohn Decomposition was introduced in:
Dulmage, A.L., Mendelsohn, N.S. Coverings of bipartitegraphs, Canadian J. Math., 10, 517-534, 1958.

The implementation of this class is based on:
Bunus P., Fritzson P., Methods for Structural Analysis and Debugging of Modelica Models, 2nd International Modelica Conference 2002

The runtime complexity of this class is $O(V + E)$.

Author:

Peter Harman

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DulmageMendelsohnDecomposition.Decomposition<V,E>	The output of a decomposition operation

Constructor Summary

Constructors

Constructor	Description
DulmageMendelsohnDecomposition(Graph<V,E> graph, Set<V> partition1, Set<V> partition2)	Construct the algorithm for a given bipartite graph $G=(V_1,V_2,E)$ and it's partitions $V_1$ and $V_2$, where $V_1\cap V_2=\emptyset$.

Method Summary

Modifier and Type	Method	Description
DulmageMendelsohnDecomposition.Decomposition<V,E>	decompose(MatchingAlgorithm.Matching<V,E> matching, boolean fine)	Perform the decomposition, using a pre-calculated bipartite matching
DulmageMendelsohnDecomposition.Decomposition<V,E>	getDecomposition(boolean fine)	Perform the decomposition, using the Hopcroft-Karp maximum-cardinality matching algorithm to perform the matching.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DulmageMendelsohnDecomposition

public DulmageMendelsohnDecomposition(Graph<V,E> graph,
                                      Set<V> partition1,
                                      Set<V> partition2)

Construct the algorithm for a given bipartite graph $G=(V_1,V_2,E)$ and it's partitions $V_1$ and $V_2$, where $V_1\cap V_2=\emptyset$.

Parameters:

graph - bipartite graph

partition1 - the first partition, $V_1$, of vertices in the bipartite graph

partition2 - the second partition, $V_2$, of vertices in the bipartite graph

Method Detail

getDecomposition

public DulmageMendelsohnDecomposition.Decomposition<V,E> getDecomposition(boolean fine)

Perform the decomposition, using the Hopcroft-Karp maximum-cardinality matching algorithm to perform the matching.

Parameters:

fine - true if the fine decomposition is required, false if the coarse decomposition is required

Returns:

the DulmageMendelsohnDecomposition.Decomposition

decompose

public DulmageMendelsohnDecomposition.Decomposition<V,E> decompose(MatchingAlgorithm.Matching<V,E> matching,
                                                                         boolean fine)

Perform the decomposition, using a pre-calculated bipartite matching

Parameters:

matching - the matching from a MatchingAlgorithm

fine - true if the fine decomposition is required

Returns:

the DulmageMendelsohnDecomposition.Decomposition