Hopcroft - 卡普算法在Python [英] Hopcroft–Karp algorithm in Python

问题描述

我想实现的 Hopcroft卡普算法 Python中使用networkx为图再presentation。

I am trying to implement the Hopcroft Karp algorithm in Python using networkx as graph representation.

目前我就这样的：

#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 的 但是它不工作。我用下面的测试code

The algorithm is taken from http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm However it does not work. I use the following test code

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

不幸的是，这并不工作，我结束了在一个无限循环:(。有人能找出错误，我出出主意，我必须承认，我还没有完全了解的算法，所以它主要是一个实现对维基百科的伪code

Unfortunately this does not work, I end up in an endless loop :(. Can someone spot the error, I am out of ideas and I must admit that I have not yet fully understand the algorithm, so it is mostly an implementation of the pseudo code on wikipedia

推荐答案

行

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

应

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

根据维基百科页面上的伪code。我看到的唯一问题是，你正在使用的双端队列用作堆栈，你想使用它作为一个队列。为了弥补这一点，你只需要popleft，而不是流行（会弹出右图）。因此，该行

as per the pseudo-code on the Wikipedia page. The only other problem I see is that you are using the deque as a stack and you want to use it as a queue. To remedy that, you just need to popleft rather than pop (which pops right). So the line

v = self.q.pop()

应

v = self.q.popleft()

我希望一切工作。我只是检查你的Python code相同的方式工作作为维基百科的伪code所以希望是假code是正确的。

Hopefully everything else works. I was just checking that your Python code works in the same manner as the pseudocode on Wikipedia so hopefully that pseudocode is correct.

这篇关于Hopcroft - 卡普算法在Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！