Блог пользователя ghost016

Help in Weighted Bipartite Matching
Автор ghost016, 13 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
"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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        phew !!!!  i am really off the track now ....  any kind of help is appreciated ... Thanks
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Do you know how to solve biparate matching without weights with maxflow algorithm?
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            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 ...
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              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.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                "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 ....
                → Ответить
                • 13 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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?
                  → Ответить
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    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
                    → Ответить
                    • 13 лет назад, # ^ |
                      ← Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

                      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.
                      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      One can always flip sign of all costs to switch between max/min problem.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      sigh!!!! Finally someone did understood me ........
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Please, remove exclamation marks from the title. Do not cry.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
first two links about min cost max flow and algorithm for solving it, and third about applications (including weighted bipartite matching (assignment problem)):
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1
→ Ответить