algorithme Hopcroft-Karp en Python

Question

Je suis en train de mettre en œuvre le Hopcroft Karp algorithme en utilisant Python NetworkX comme représentation graphique.

Actuellement, je suis aussi loin que cela:

#Algorithms for bipartite graphs

import networkx as nx
import collections

class HopcroftKarp(object):
    INFINITY = -1

    def __init__(self, G):
        self.G = G

    def match(self):
        self.N1, self.N2 = self.partition()
        self.pair = {}
        self.dist = {}
        self.q = collections.deque()

        #init
        for v in self.G:
            self.pair[v] = None
            self.dist[v] = HopcroftKarp.INFINITY

        matching = 0

        while self.bfs():
            for v in self.N1:
                if self.pair[v] and self.dfs(v):
                    matching = matching + 1

        return matching

    def dfs(self, v):
        if v != None:
            for u in self.G.neighbors_iter(v):
                if self.dist[ self.pair[u] ] == self.dist[v] + 1 and self.dfs(self.pair[u]):
                    self.pair[u] = v
                    self.pair[v] = u

                    return True

            self.dist[v] = HopcroftKarp.INFINITY
            return False

        return True

    def bfs(self):
        for v in self.N1:
            if self.pair[v] == None:
                self.dist[v] = 0
                self.q.append(v)
            else:
                self.dist[v] = HopcroftKarp.INFINITY

        self.dist[None] = HopcroftKarp.INFINITY

        while len(self.q) > 0:
            v = self.q.pop()
            if v != None:
                for u in self.G.neighbors_iter(v):
                    if self.dist[ self.pair[u] ] == HopcroftKarp.INFINITY:
                        self.dist[ self.pair[u] ] = self.dist[v] + 1
                        self.q.append(self.pair[u])

        return self.dist[None] != HopcroftKarp.INFINITY


    def partition(self):
        return nx.bipartite_sets(self.G)

L'algorithme est tiré de http://en.wikipedia.org/wiki / Hopcroft% E2% 80% 93Karp_algorithm Cependant, il ne fonctionne pas. J'utilise le code de test suivant

G = nx.Graph([
(1,"a"), (1,"c"),
(2,"a"), (2,"b"),
(3,"a"), (3,"c"),
(4,"d"), (4,"e"),(4,"f"),(4,"g"),
(5,"b"), (5,"c"),
(6,"c"), (6,"d")
])

matching = HopcroftKarp(G).match()

print matching

Malheureusement, cela ne fonctionne pas, je finis dans une boucle sans fin :(. Quelqu'un peut-il repérer l'erreur, je suis d'idées et je dois admettre que je comprends pas encore tout à fait l'algorithme, il est donc essentiellement une mise en œuvre du code de pseudo sur wikipedia

Answer 1

La ligne

if self.pair[v] and self.dfs(v):

doit être

if self.pair[v] is None and self.dfs(v):

selon le pseudo-code sur la page Wikipedia. Le seul autre problème que je vois est que vous utilisez la deque comme une pile et que vous voulez l'utiliser comme une file d'attente. Pour remédier à cela, il vous suffit de popleft plutôt que pop (qui apparaît à droite). Ainsi, la ligne

v = self.q.pop()

doit être

v = self.q.popleft()

Si tout va bien tout le reste fonctionne. Je voulais simplement vérifier que votre code Python fonctionne de la même manière que le pseudocode sur Wikipédia si nous espérons que pseudocode est correct.

Answer 2

En python il y a un paquet pour cet algorithme. HopcroftKarp , vous pouvez utiliser directement ce package pour votre mise en œuvre.