Contiguous option doesn't seem to work.

[filloax]

Describe the bug Passing the contiguous option in create_parts, either via the argument in the method or passing an Options object with contig set to True, doesn't seem to actually return contiguous partitions.

To Reproduce Run metis part with the contig option in one of these ways:

metis_opts = Options()
metis_opts.contig = True
edgecuts, parts = part_graph(
    numparts, xadj=xadj, adjncy=adjncy,
    options=metis_opts,
)

edgecuts, parts = part_graph(
    numparts, xadj=xadj, adjncy=adjncy,
    contiguous=True,
)

Expected behavior The resulting partitions should be contiguous.

Environment (please complete the following information):

• OS: Windows (with Anaconda)
  • Python version: 3.10
  • pymetis version: 2023.1.1

Additional context Image of the resulting partitions from a street map graph (each color = different partition):

[inducer]

@nhartland, as the person who contributed the functionality to expose the "contiguous" flag in #20, could you comment?

[nhartland]

It's a bit hard to tell but it looks from your figure like you have disconnected components in your graph? IIRC when given a disconnected graph METIS will silently ignore the continuous flag.

[Nalaka1693]

Hi It seems like contig=1 or contiguous=True do not force continuous partitions in a connected graph. Please see the example below to reproduce and visualize the partitions.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import random
import pymetis

random.seed(0)

adjacency_list = np.array(
    [
        [2, 3, 4],
        [2, 4, 5],
        [0, 1, 3],
        [0, 2, 5, 6],
        [0, 1, 6],
        [1, 3, 6],
        [3, 4, 5],
    ],
    dtype=object,
)

adj_list = {idx: l for idx, l in enumerate(adjacency_list)}
g = nx.Graph(adj_list)

edge_weights = [2, 10, 1, 1, 1, 1, 1, 1, 10, 1, 1]
attrs = {edge: {"weight": edge_weights[idx]} for idx, edge in enumerate(g.edges())}
nx.set_edge_attributes(g, attrs)

layout = nx.spring_layout(g)
sizes = [100] * 7

metis_edge_weights = []
for u in g.nodes():
    for v in list(nx.neighbors(g, u)):
        try:
            metis_edge_weights.append(attrs[(u, v)]["weight"])
        except KeyError:
            metis_edge_weights.append(attrs[(v, u)]["weight"])

f = plt.figure(1)
nx.draw(g, layout, with_labels=True, node_size=sizes, node_color="r", arrows=True)
labels = nx.get_edge_attributes(g, "weight")
nx.draw_networkx_edge_labels(g, pos=layout, edge_labels=labels)

parts = 3

metis_opts = pymetis.Options(seed=0, ccorder=1, minconn=0, contig=1)
n_cuts, membership = pymetis.part_graph(
    parts,
    adjacency=adjacency_list,
    vweights=sizes,
    eweights=metis_edge_weights,
    options=metis_opts,
)

for p in range(parts):
    nodes = np.argwhere(np.array(membership) == p).ravel()
    print(nodes)
    f = plt.figure(p + 2)
    h = g.subgraph(nodes)
    hlayout = nx.spring_layout(h)
    nx.draw(h, hlayout, with_labels=True)
    labels = nx.get_edge_attributes(h, "weight")
    nx.draw_networkx_edge_labels(g, pos=hlayout, edge_labels=labels)

plt.show()

Output

[1 4]
[0 3 6]
[2 5] -> unconnected

[qy090]

Describe the bug Passing the contiguous option in create_parts, either via the argument in the method or passing an Options object with contig set to True, doesn't seem to actually return contiguous partitions.

To Reproduce Run metis part with the contig option in one of these ways:

metis_opts = Options()
metis_opts.contig = True
edgecuts, parts = part_graph(
    numparts, xadj=xadj, adjncy=adjncy,
    options=metis_opts,
)

edgecuts, parts = part_graph(
    numparts, xadj=xadj, adjncy=adjncy,
    contiguous=True,
)

Expected behavior The resulting partitions should be contiguous.

Environment (please complete the following information):

• OS: Windows (with Anaconda)
• Python version: 3.10
• pymetis version: 2023.1.1

Additional context Image of the resulting partitions from a street map graph (each color = different partition):

Can I ask you some questions?I would like to ask you about the segmentation of the road network. If possible, tell me,here is my email address.qiyou132@gmail.com。 I would be very grateful.

[nhartland]

The last time I checked* it was working fine for my application (partitions were contiguous when the flag was set, discontiguous when not). So at least the passing of the flag to METIS seemed to be working. Beyond that, what METIS does with the flag (and I am aware of at least the one case of it being silently ignored, see above) I can't offer support for.

*That being said, I've changed job in the meantime so no longer have access to the code to double-check.