Hopcroft-Karp-Algorithmus in Python

Question

Ich versuche, die Hopcroft Karp Algorithmus in Python zu implementieren mit NetworkX als Grafik-Darstellung.

Zur Zeit bin ich so weit wie folgt aus:

#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)

Der Algorithmus wird genommen von http://en.wikipedia.org/wiki / Hopcroft% E2% 80% 93Karp_algorithm Allerdings funktioniert es nicht. Ich verwende den folgenden Testcode

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

Leider funktioniert das nicht, ich in einer Endlosschleife am Ende :(. Kann jemand den Fehler entdecken, ich bin von Ideen, und ich muss zugeben, dass ich noch nicht vollständig den Algorithmus verstehen, so dass es meist ist eine Implementierung der Pseudo-Code auf wikipedia

Answer 1

Die Zeile

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

sollte

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

gemäß dem Pseudo-Code auf der Wikipedia-Seite. Das einzige andere Problem, das ich sehe, ist, dass Sie die deque als Stapel verwenden und Sie wollen es als eine Warteschlange verwenden. Um dem abzuhelfen, dass, Sie müssen nur eher popleft als Pop (das erscheint rechts). So die Zeile

v = self.q.pop()

sollte

v = self.q.popleft()

Hoffentlich alles andere funktioniert. Ich hatte nur überprüfen, ob Ihr Python-Code funktioniert auf die gleiche Weise wie der Pseudo-Code auf Wikipedia so hoffentlich, dass Pseudo-Code korrekt ist.

Answer 2

In Python gibt es ein Paket für diesen Algorithmus. HopcroftKarp Sie direkt das Paket für Ihre Implementierung verwenden können.