Class MaximumWeightBipartiteMatching<V,​E>

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

    @Deprecated
    public class MaximumWeightBipartiteMatching<V,​E>
    extends java.lang.Object
    implements WeightedMatchingAlgorithm<V,​E>
    Deprecated.
    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 final java.util.Set<V> partition1
        Deprecated.
      • partition2

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

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

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

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

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

      • MaximumWeightBipartiteMatching

        public MaximumWeightBipartiteMatching​(WeightedGraph<V,​E> graph,
                                              java.util.Set<V> vertexPartition1,
                                              java.util.Set<V> vertexPartition2)
        Deprecated.
        Creates a new MaximumWeightBipartiteMatching algorithm instance. The union of vertexPartition1 and vertexParition2 should be equal to the vertex set of the graph Every edge in the graph must connect a vertex in vertexPartition1 with a vertex in vertexPartition2
        Parameters:
        graph - simple undirected weighted bipartite graph to find matching in, with positive integer edge weights
        vertexPartition1 - first vertex partition of the bipartite graph, disjoint from vertexPartition2
        vertexPartition2 - second vertex partition of the bipartite graph, disjoint from vertexPartition1
    • Method Detail

      • getMatching

        public java.util.Set<E> getMatching()
        Deprecated.
        Description copied from interface: MatchingAlgorithm
        Returns set of edges making up the matching
        Specified by:
        getMatching in interface MatchingAlgorithm<V,​E>
        Returns:
        a matching
      • initializeVerticesAndEdges

        private void initializeVerticesAndEdges()
        Deprecated.
      • maximumWeightOfEdgeIncidentToVertex

        private long maximumWeightOfEdgeIncidentToVertex​(V vertex)
        Deprecated.
      • isSourceVertex

        private boolean isSourceVertex​(V vertex)
        Deprecated.
      • isTargetVertex

        private boolean isTargetVertex​(V vertex)
        Deprecated.
      • vertexWeight

        private long vertexWeight​(V vertex)
        Deprecated.
      • setVertexWeight

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

        private long reducedWeight​(E edge)
        Deprecated.
      • isVertexMatched

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

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

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

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

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

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