Class MaximumWeightBipartiteMatching<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MatchingAlgorithm<V,​E>

    public class MaximumWeightBipartiteMatching<V,​E>
    extends java.lang.Object
    implements MatchingAlgorithm<V,​E>
    This class finds a maximum weight matching of a simple undirected weighted bipartite graph. The algorithm runs in O(V|E|^2). The algorithm is described in The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999. https://people.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html Note: the input graph must be bipartite with positive integer edge weights
    • Field Detail

      • partition1

        private java.util.Set<V> partition1
      • partition2

        private java.util.Set<V> partition2
      • vertexWeights

        private java.util.Map<V,​java.lang.Long> vertexWeights
      • hasVertexBeenProcessed

        private java.util.Map<V,​java.lang.Boolean> hasVertexBeenProcessed
      • isEdgeMatched

        private java.util.Map<E,​java.lang.Boolean> isEdgeMatched
      • bipartiteMatching

        private java.util.Set<E> bipartiteMatching
    • Constructor Detail

      • MaximumWeightBipartiteMatching

        public MaximumWeightBipartiteMatching​(Graph<V,​E> graph,
                                              java.util.Set<V> partition1,
                                              java.util.Set<V> partition2)
        Construct a new instance of the algorithm. Supported graphs are simple undirected weighted bipartite with positive integer edge weights.
        Parameters:
        graph - the input graph
        partition1 - the first partition of the vertex set
        partition2 - the second partition of the vertex set
        Throws:
        java.lang.IllegalArgumentException - if the graph is not undirected
    • Method Detail

      • initializeVerticesAndEdges

        private void initializeVerticesAndEdges()
      • maximumWeightOfEdgeIncidentToVertex

        private long maximumWeightOfEdgeIncidentToVertex​(V vertex)
      • isSourceVertex

        private boolean isSourceVertex​(V vertex)
      • isTargetVertex

        private boolean isTargetVertex​(V vertex)
      • vertexWeight

        private long vertexWeight​(V vertex)
      • setVertexWeight

        private void setVertexWeight​(V vertex,
                                     java.lang.Long weight)
      • reducedWeight

        private long reducedWeight​(E edge)
      • isVertexMatched

        private boolean isVertexMatched​(V vertex,
                                        java.util.Set<E> matchings)
      • addPathToMatchings

        private void addPathToMatchings​(java.util.List<E> path,
                                        java.util.Set<E> matchings)
      • adjustVertexWeights

        private void adjustVertexWeights​(java.util.Map<V,​java.util.List<E>> reachableVertices)
      • verticesReachableByTightAlternatingEdgesFromVertex

        private java.util.Map<V,​java.util.List<E>> verticesReachableByTightAlternatingEdgesFromVertex​(V vertex)
      • findPathsToVerticesFromVertices

        private void findPathsToVerticesFromVertices​(java.util.List<V> verticesToProcess,
                                                     boolean needMatchedEdge,
                                                     java.util.Map<V,​java.util.List<E>> pathsToVertices)
      • maximumWeightBipartiteMatching

        private java.util.Set<E> maximumWeightBipartiteMatching()