ghost016's blog

Help in Weighted Bipartite Matching
By ghost016, 13 years ago, In English

Hello all,

i have learned that for converting Bipartite graph to Maxflow, i need to introduce two vertices, super-source and super-sink and each edge will be assigned a capacity of "1" from the super-source to the vertices in one partition and to the super-sink from the vertices of another partition, and then apply the maxflow algorithm, where the maxflow is the max-matching. My question however is that is this system can be applied to the weighted bipartite graph, for finding the maximum weight of the graph ?? if not then is there any other method how i can reduce the weighted bipartite graph to maxflow problem. Hope to get some reply.

Thanking You
Ghost016

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
"finding the maximum weight of the graph"
Did you mean maximum (or minimum) weight of the maximum matching?
Yes, you can make similar transform on a weighted graph, but along with capacities give edges costs. Cost of edge between partitions will be the weight of this edge in original graph. All other edges (i.e edges incident to sink or source) will have cost 0. Using min cost max flow algorithm you can find a maximal (i.e. with the max number of edges) matching with minimal weight.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks for the reply and
    yes!!! i meant maximum weight of the maximum matching , btw please point out whether i am wrong,

    1. "    capacities give edges costs"  --> that means, the weight of the edge from a vertex in one set of partition to another vertex in another set forms the capacity of that edge.

    2. "    All other edges (i.e edges incident to sink or source) will have cost 0 " --> but i read in many articles that i have to assign a cost of 1 i.e the capacity should be 1 to/from the vertices from/to the source/sink node.

    3. "    Using min cost max flow algorithm you can find a maximal (i.e. with the max number of edges) matching with minimal weight"  --> I asked for the maximum weight .....

    Hope i did make my points clear.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. No, all capacities are still 1. What I meant with ""along with capacities give edges costs" was that each edge has two values: capacity and cost.
      2. Capacity != cost. Capacity of each edge is 1. Cost is 0 for edges from/to the source/sink. Cost is weight (from original graph) for edges between partitions.
      3. Weights can be negative. You can change signs of the weights to turn minimum into maximum.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        phew !!!!  i am really off the track now ....  any kind of help is appreciated ... Thanks
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Do you know how to solve biparate matching without weights with maxflow algorithm?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            No ... I dont, i am studying the bipartite thing recently... just implemented the hungarian algorithm, thats all .... but it seems little harder, so i thought of doing it using maxflow-mincut .. which i  found bit easier to understand ...
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              For me maxflow is easier, for you it might be hungarian. Anyway , maxflow is more useful, there are many problems that can be solved by it.
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                "For me maxflow is easier, for you it might be hungarian" ... for me maxflow i feel more comfortable .... thats why i want to learn bipartite matching with maxflow implementation rather then hungarian ....
                → Reply
                • 13 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  So you know maxflow algorithm.
                  1. Find the path
                  2. Increase flow through it
                  3. Repeat

                  For a weighted graph:
                  1. Find the SHORTEST path
                  ...

                  Don't forget about back edges - they have negative weight.

                  Is there a problem with understanding how to solve biparate a matching without weights using maxflow?
                  → Reply
                  • 13 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    Thanks for the reply...

                    please tell my whether the steps are correct.

                    1. first i will take the inputs
                       nodes(x, y) along with their weight(w).
                       p.s: i dnt have to bother whether it is bipartite graph, because i assumed it is a bipartite graph.

                    2. Please tell me then how should i add capacity to all the edge's, also the super-sink and super source, and also what will be the value of the added capacities.

                    3. in maxflow, the implementation is based on the capacity of the edges, for finding the augmenting path, so what should i do with the weight's that has been added to each edge during input?? shall i just add them up later for those edges forms the maximum matching ??

                    4. For this method of maxflow, i.e  maximum weighted matching in the bipartite graph, what is the runtime ?? is there any other way to decrease the runtime for maximum matching using maxflow.

                    Hope i could made my things clear, and sorry for the poor english.

                    Thanks
                    → Reply
                    • 13 years ago, # ^ |
                      ← Rev. 2   Vote: I like it -11 Vote: I do not like it

                      Do not ask questions more, at first you must read "Minimum Cost-Maximum Flow Algorithm". There is two values on each edge: it's cost and the capacity, as I understand do you not understand this thing at this moment, and asks "stupid" questions. Read about algorithm, and read all comments from these post again. Also you can ask me in private messages. I dont' undestand your previous question.
                      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I thought he was asking about a matching with maximum total weight, but it seems that all other coders here are talking about minimum cost maximum flow, which may confuse him.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      One can always flip sign of all costs to switch between max/min problem.
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      sigh!!!! Finally someone did understood me ........
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You don't understand what you need. The "assignment problem" can be solved using hungarian algorithm, but it also can be solved using MinCostMaxFlow. In your private messages you can find more info.
        → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Please, remove exclamation marks from the title. Do not cry.
→ Reply