jueves, 24 de mayo de 2012

Spotify - Bilateral Projects: Final Puzzle solution

Ok, I finally created a correct solution for the Bilateral puzzle of Spotify.
I wrote a previously article about this:
    http://alonso-vidales.blogspot.com.es/2012/03/spotify-bilateral-projects-puzzle.html


The problem is that the previous solution first calculates the max-cardinality, but to calculate the max vertex cover I used a permutation to calculate all the possibilities.
I spent a bit more time reading about bipartitie graphs, and how to find the min vertex coverage with the smallest complexity, and I found the "König's theorem":

    http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory)


This theorem can be combined with the Hopcroft-Karp to solve the problem in the smallest complexity.
The problem is that I didn't find any implementation of the König's algorithm that I can use, and I decided to read the Algorithm definition, and create one. Is really simple to do it after understand how the algorithm works.
And at the end....




You can find the solution code here:

No hay comentarios:

Publicar un comentario