我正在尝试设计一个采用全局定位数据的项目，例如城市和州名称以及纬度和位置。我还将计算每对城市之间的距离。我想用所有这些信息制作一个图表，并操纵它来执行一些图表算法。我决定拥有包含每个位置数据的城市对象。现在我应该有一个散列函数来区分对象吗？我应该如何处理结合节点和删除边缘的图形算法？
def minCut(self):
"""Returns the lowest-cost set of edges that will disconnect a graph"""
smcut = (float('infinity'), None)
cities = self.__selectedcities[:]
edges = self.__selectededges[:]
g = self.__makeGRAPH(cities, edges)
if not nx.is_connected(g):
print("The graph is already diconnected!")
return
while len(g.nodes()) >1:
stphasecut = self.mincutphase(g)
if stphasecut[2] < smcut:
smcut = (stphasecut[2], None)
self.__merge(g, stphasecut[0], stphasecut[1])
print("Weight of the min-cut: "+str(smcut[1]))
它的状态真的很糟糕。我正在重写我的原始程序，但这是我从以前的版本中采用的方法。
请您参考如下方法:
根据您安装的 networkx 版本，可以使用内置的 min_cut 实现。
我安装了 1.0RC1 包，但它不可用..但我升级到 1.4 并且 min_cut 在那里。
这是一个(愚蠢的)例子:
import networkx as nx
g = nx.DiGraph()
g.add_nodes_from(['London', 'Boston', 'NY', 'Dallas'])
g.add_edge('NY', 'Boston', capacity)
g.add_edge('Dallas', 'Boston')
g.add_edge('Dallas', 'London')
# add capacity to existing edge
g.edge['Dallas']['London']['capacity'] = 2
# create edge with capacity attribute
g.add_edge('NY', 'London', capacity=3)
print nx.min_cut(g, 'NY', 'London')
