V
 Vertex typeE
 Edge typepublic class DulmageMendelsohnDecomposition<V,E> extends Object
This class computes a DulmageMendelsohn 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 DulmageMendelsohn Decomposition.
The DulmageMendelsohn Decomposition is based on a maximummatching of the graph $G$. This implementation uses the HopcroftKarp maximum matching algorithm by default.
A coarse DulmageMendelsohn 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:
A fine DulmageMendelsohn Decomposition further partitions the remaining vertices into stronglyconnected sets. This implementation uses Kosaraju's algorithm for the strongconnectivity analysis.
The DulmageMendelsohn Decomposition was introduced in:
Dulmage, A.L., Mendelsohn, N.S. Coverings of bipartitegraphs, Canadian J. Math., 10, 517534,
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)$.
Modifier and Type  Class and Description 

static class 
DulmageMendelsohnDecomposition.Decomposition<V,E>
The output of a decomposition operation

Constructor and 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$.

Modifier and Type  Method and Description 

DulmageMendelsohnDecomposition.Decomposition<V,E> 
decompose(MatchingAlgorithm.Matching<V,E> matching,
boolean fine)
Perform the decomposition, using a precalculated bipartite matching

DulmageMendelsohnDecomposition.Decomposition<V,E> 
getDecomposition(boolean fine)
Perform the decomposition, using the HopcroftKarp maximumcardinality matching algorithm to
perform the matching.

public DulmageMendelsohnDecomposition(Graph<V,E> graph, Set<V> partition1, Set<V> partition2)
graph
 bipartite graphpartition1
 the first partition, $V_1$, of vertices in the bipartite graphpartition2
 the second partition, $V_2$, of vertices in the bipartite graphpublic DulmageMendelsohnDecomposition.Decomposition<V,E> getDecomposition(boolean fine)
fine
 true if the fine decomposition is required, false if the coarse decomposition is
requiredDulmageMendelsohnDecomposition.Decomposition
public DulmageMendelsohnDecomposition.Decomposition<V,E> decompose(MatchingAlgorithm.Matching<V,E> matching, boolean fine)
matching
 the matching from a MatchingAlgorithm
fine
 true if the fine decomposition is requiredDulmageMendelsohnDecomposition.Decomposition
Copyright © 2018. All rights reserved.