问题描述
限时送ChatGPT账号..我正在尝试使用 Python 在 Python 中实现 Hopcroft Karp 算法networkx 作为图形表示.
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/wiki/Hopcroft%E2%80%93Karp_algorithm但是它不起作用.我使用以下测试代码
The algorithm is taken from http://en.wikipedia/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
不幸的是这不起作用,我最终陷入了一个无限循环:(.有人能发现错误吗,我没有想法,我必须承认我还没有完全理解算法,所以它主要是一个实现维基百科上的伪代码
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):
根据维基百科页面上的伪代码.我看到的唯一另一个问题是您将双端队列用作堆栈,并且想将其用作队列.为了解决这个问题,你只需要 popleft 而不是 pop (它向右弹出).所以这条线
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 代码是否与维基百科上的伪代码以相同的方式工作,因此希望伪代码是正确的.
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.
这篇关于Python中的Hopcroft-Karp算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
更多推荐
[db:关键词]
发布评论