我正在尝试使用metis 做一个简单的图形分区。目标是使用固定数量的 k 个分区来最小化图切割成本。
我设置了一个简单的小问题，所有边缘都具有高权重（不要切割），只有一个具有低权重（请在此处切割）。
在示例中，我希望唯一的切口位于节点 3 和 24 之间的边 10 上，权重为 1。
Metis 返回的结果非常糟糕，最低边缘没有被切割，而是到处切割（即使我设置了 contiguos = True）。削减成本似乎也是错误的。
我想听听比我更熟悉这类问题的人
这是我正在使用的 python 脚本：
import networkx as nx
import metis
#all edges have high weight, I expect the cut to be coming on edge 10 between node 3 an 24
edges=[(33, 34, 1000), (1, 18, 1000), (1, 17, 1000), (17, 34, 1000), (48, 49, 1000), (18, 48, 1000), (25, 50, 1000), (49, 50, 1000), (24, 25, 1000), (3, 30, 1000), (3, 24, 1), (31, 32, 1000), (30, 31, 1000), (22, 32, 1000), (3, 47, 1000), (46, 47, 1000), (0, 20, 1000), (0, 4, 1000), (4, 29, 1000), (28, 29, 1000), (28, 46, 1000), (20, 21, 1000), (2, 21, 1000), (40, 42, 1000), (2, 40, 1000), (12, 41, 1000), (41, 42, 1000), (13, 14, 1000), (12, 13, 1000), (8, 16, 1000), (8, 14, 1000), (15, 16, 1000), (6, 7, 1000), (6, 15, 1000), (5, 6, 1000), (5, 9, 1000), (10, 11, 1000), (9, 10, 1000), (0, 19, 1000), (36, 44, 1000), (26, 36, 1000), (26, 27, 1000), (4, 27, 1000), (43, 45, 1000), (44, 45, 1000), (55, 56, 1000), (37, 55, 1000), (37, 38, 1000), (38, 43, 1000), (35, 56, 1000), (37, 39, 1000), (51, 52, 1000), (39, 52, 1000), (53, 54, 1000), (1, 53, 1000), (23, 54, 1000)]
ne = len(edges)
G = nx.Graph()
G.add_weighted_edges_from(edges)
print(G.number_of_edges())
print(G.number_of_nodes())
# Add node weights to graph
for i in range(G.number_of_nodes()):
G.nodes[i]['node_value'] = 1
# tell METIS which node attribute to use for
G.graph['node_weight_attr'] = 'node_value'
G.graph['edge_weight_attr']='weight'
# Check graph attributes for weight/size labels
edgew = G.graph.get('edge_weight_attr', None)
nodew = G.graph.get('node_weight_attr', [])
nodesz = G.graph.get('node_size_attr', None)
# Get at MOST two partitions from METIS
(cutcost, parts) = metis.part_graph(G, nparts = 2, objtype="cut")
#parts [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
#cutcost 1001
#???????????????????????????????????
print(parts)
# Assuming you have PyDot installed, produce a DOT description of the graph:
colors = ['red', 'blue']
for i, part in enumerate(parts):
G.nodes[i]['color'] = colors[part]
nx.nx_pydot.write_dot(G, 'example.dot')
这里是graphiz图片：
