10

グラフ表現としてnetworkxを使用して、Pythonでホップクロフトカープアルゴリズムを実装しようとしています。

現在、私はこれまでです：

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

アルゴリズムはhttp://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithmから取得されますが 、機能しません。次のテストコードを使用します

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

残念ながら、これは機能せず、無限ループに陥ります:(。誰かがエラーを見つけることができますか、私はアイデアがありません、そして私はまだアルゴリズムを完全に理解していないことを認めなければなりません、それでそれはほとんど疑似の実装ですウィキペディアのコード

4

2 に答える 2

5

この線

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

する必要があります

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

ウィキペディアページの擬似コードに従って。私が見る他の唯一の問題は、dequeをスタックとして使用していて、それをキューとして使用したいということです。これを修正するには、ポップ（右にポップ）ではなく、左にポップする必要があります。だからライン

v = self.q.pop()

する必要があります

v = self.q.popleft()

うまくいけば、他のすべてが機能します。Pythonコードがウィキペディアの擬似コードと同じように機能することを確認していたので、擬似コードが正しいことを願っています。

于 2011-01-15T04:51:41.103 に答える
1

Pythonには、このアルゴリズムのパッケージがあります。 HopcroftKarp、実装にそのパッケージを直接使用できます。

于 2017-03-16T18:40:43.440 に答える