如何在 Python 的 Metis 中构建图形

Question

我正在使用Metis for Python，一个用于 Metis（图形分区软件）的 Python 包装器。我已经安装了所有东西并且它似乎可以正常工作，但是我不明白如何构建要输入的图形。

有一个在线示例：http : //metis.readthedocs.org/en/latest/#example

>>> import networkx as nx
>>> import metis
>>> G = metis.example_networkx()
>>> (edgecuts, parts) = metis.part_graph(G, 3)
>>> colors = ['red','blue','green']
>>> for i, p in enumerate(parts):
...     G.node[i]['color'] = colors[p]
...
>>> nx.write_dot(G, 'example.dot') # Requires pydot or pygraphviz

我运行了这个例子，它工作正常。然而，在这个例子中，他们从未指定如何构建图“example_networkx()”。我试图通过 networkx 构建图表：http ://metis.readthedocs.org/en/latest/#metis.networkx_to_metis

我的代码是：

>>> A=nx.Graph()
>>> A.add_edges_from([(3,1),(2,3),(1,2),(3,4),(4,5),(5,6),(5,7),(7,6),(4,10),(10,8),(10,9),(8,9)])
>>> G = metis.networkx_to_metis(A)
>>> (edgecuts, parts) = metis.part_graph(G, 3)

我在最后一行出现错误。该错误可追溯到 Metis 内置代码中的这些行：

in part_graph(graph, nparts, tpwgts, ubvec, recursive, **opts)
    graph = adjlist_to_metis(graph, nodew, nodesz)
in adjlist_to_metis(adjlist, nodew, nodesz)
    m2 = sum(map(len, adjlist))
TypeError: object of type 'c_long' has no len()

我还尝试通过邻接列表构建图形：http : //metis.readthedocs.org/en/latest/#metis.adjlist_to_metis 但这给出了与以前相同的错误。

我想知道是否有人遇到过这个问题，或者知道我做错了什么。

我在 Centos 6.5 上使用 python 2.7

Answer 1

metis.part_graph 接受图的 networkx 和邻接列表表示。当您构建 networkx 图时，您几乎是对的。但是，您应该直接将此图传递给 part_graph 函数，而不是先将其转换为 metis 对象，因为 part_graph 函数不直接接受 metis 类型的图。给定一个Anumpy 中的邻接矩阵，一个例子可以是：

# since weights should all be integers
G = networkx.from_numpy_matrix(np.int32(A))  
# otherwise metis will not recognize you have a weighted graph
G.graph['edge_weight_attr']='weight'         
[cost, parts] = metis.part_graph(G, nparts=30, recursive=True)