Class DulmageMendelsohnDecomposition<V,​E>

  • Type Parameters:
    V - Vertex type
    E - 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 2002

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

    Peter Harman
    • 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$.
        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