Kerpoo's blog

By Kerpoo, history, 19 months ago, In English,

I love this implementation of Edmond's Blossoms :-)

Edmond's Blossoms algorithm give a maximum matching in general graphs (non-bipartite)

CODE

thanks a lot to boleyn.su

 
 
 
 
  • Vote: I like it  
  • +53
  • Vote: I do not like it  

»
18 months ago, # |
  Vote: I like it -40 Vote: I do not like it

سلام من چند وقت پیش تو یک گروه تلگرام ACM عض بودم که شما هم اونجا ضو بودید ولی من ناخواسته لفت دادم و دیگه نتونستم عضو بشم حالا اگه شما هنوز عضو هستید لینک گروه رو بزارید ایجا تا ما هم دوباره عضو بشیم خیلی ممنون

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Thanks, now I see.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lost in translation:

      "Hi I some time ago I was a member telegram that you were a member there, but I did and I missed unwanted Left Party, let's go now if you do not already created links to our Group to become a member again thank you very much".

      Why is it so hard for people to write in english?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks brother

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone please tell me if the above code is suitable for a weighted matching?

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    No, it isn't but there is another version of this algorithm that works for weighted graphs.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the fast answer! Where do I find that version?

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Probably not useful in competitive programming, but check Kolmogorov's implementation and paper.

        Note: Python implementation that can be adapted for online contests.

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Thanks again! It's not for competition so I'm glad for any usable to implement :)

          Can you also provide something written in c++? In the second link there is in return a link for a c++ library, called lemon, including a weighted edmond algorithm. Do you have any experience with that or is there something even better? I did some search and as far as I can suggest this seems to be the best. Boost library does not support a weighted version and NetworkX/NetworkKit are also written in phython. So I assume lemon is the best way to go?

          The Blossom 5 looks very good, but to be honest, this is way over my head even I "only" have to implement it. But it looks interesting.

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I don't have experience with Lemon but I believe it can be trusted (I couldn't find anything better after a very quick search).

            I have experience with NetworkX and if you are fine will calling Python functions from a C++ problem then I suggest you use it (it is really awesome once you get used to it).

            BTW, Kolmogorov's implementation is in C++. If you're working on some project, I suggest you use a library with a nice API, but you can also use that implementation.

            • »
              »
              »
              »
              »
              »
              »
              15 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ok, thank you! Then I'll stick with lemon.

              NetworkX is interesting in general for further projects. And Kolmogorv is well documented but the assignment part is part of my thesis — and not the most important. In case I have to defend my thesis somewhen I guess I'll need several years only to understand the theory behind Kolomogorv :)

              Thanks again!

»
15 months ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

A good place to test your code.

Input format goes like:

vertex count, edge count

u, v: there's an undirected edge connecting vertex u and v. It's guaranteed that u != v, and no edge would appear twice.

Output format goes like:

The number of edges in the matching.

The vertex matched to each vertex. For unmatched vertex output 0.

Weighted matching can be tested here.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Goes into inf loop for the input :

4
4
1 2
1 3
1 4
2 4