我应该如何创建对象以使其与networkx良好兼容？

Question

我正在设计一个项目，这个项目需要处理全球定位数据，比如城市和州的名称，还有它们的经纬度。我还会有每对城市之间的距离。我想把这些信息做成一个图形，并对它进行一些图形算法的操作。我决定创建城市对象，每个对象包含一个地点的数据。那么，我是否需要一个哈希函数来区分这些对象呢？我应该如何处理结合节点和移除边的图形算法呢？

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

现在情况很糟糕。我正在重写我最初的程序，但这是我从之前版本中采取的方法。

Answer 1

当你合并节点的时候，可以创建新的节点，并把这些新节点的值和已经合并的城市列表关联起来。比如，在上面的代码中，你可以把新节点命名为 len(g)，然后把它的值和 stphasecut[0] 加上 stphasecut[1] 关联起来，假设 stphasecut[1] 和 stphasecut[2] 是列表。

Answer 2

你不需要为城市对象创建哈希函数，可以直接把城市对象传给Networkx。根据教程的说法，“节点可以是任何可哈希的对象，比如文本字符串、图片、XML对象、另一个图、或者自定义的节点对象等等。”

你可以遍历城市列表，把它们添加为节点，然后再遍历距离信息来制作图形。

你看过教程吗？ http://networkx.lanl.gov/tutorial/tutorial.html

Answer 3

根据你安装的networkx版本，里面有一个内置的最小割（min_cut）功能。

我之前安装的是1.0RC1版本，这个功能没有。不过我升级到了1.4版本，发现最小割功能就有了。

下面是一个（简单的）例子：

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