Class DulmageMendelsohnDecomposition<V,E>
- java.lang.Object
-
- org.jgrapht.alg.decomposition.DulmageMendelsohnDecomposition<V,E>
-
- Type Parameters:
V
- Vertex typeE
- Edge type
public class DulmageMendelsohnDecomposition<V,E> extends java.lang.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 2002The 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, java.util.Set<V> partition1, java.util.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
All Methods Instance Methods Concrete Methods 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 matchingDulmageMendelsohnDecomposition.Decomposition<V,E>
getDecomposition(boolean fine)
Perform the decomposition, using the Hopcroft-Karp maximum-cardinality matching algorithm to perform the matching.
-
-
-
Constructor Detail
-
DulmageMendelsohnDecomposition
public DulmageMendelsohnDecomposition(Graph<V,E> graph, java.util.Set<V> partition1, java.util.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 graphpartition1
- the first partition, $V_1$, of vertices in the bipartite graphpartition2
- 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 aMatchingAlgorithm
fine
- true if the fine decomposition is required- Returns:
- the
DulmageMendelsohnDecomposition.Decomposition
-
-