I am trying to do what I though was a simple graph partition using metis. The objective is to minimize graph cut cost with fixed number of k partitions.
I set up a small simple problem with all edges having high weight (don't cut), and only one having low weight (please cut here).
In the example I would expect the only cut is on edge 10 between node 3 and 24 having weight 1.
Metis is returning very bad results with the lowest edge not being cut but cuts all over the place (even if I set contiguos = True). The cutcost also seems to be wrong.
I would like to hear from someone that is more familiar than me with this class of problems
This is the python script I am using:
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')
and here the graphiz picture:
