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.

[mingloo]

Hey @filloax

Not sure if you're able to fix this issue or NOT but I would like to share some my experiences when using pymetis.

The original METIS has contig parameter applies ONLY when k-way partitioning is called. Please see manual for details.

-contig (applies only when -ptype=kway)
Specifies that the partitioning routines should try to produce partitions that are contiguous. Note that
if the input graph is not connected this option is ignored.

In pymetis implementation, the recursive is set to None by default. The partitioning method (kway or recursive) we used is determined by how many partitions would like to do. Once recursive method is applied (nparts <=8), we cannot force contig parameter any more.

def part_graph(nparts, adjacency=None, xadj=None, adjncy=None,
        vweights=None, eweights=None, recursive=None, contiguous=None, options=None):
...
    if recursive is None:
        recursive = nparts <= 8
...

@filloax So in your situation, maybe you can set recursive=False and contiguous=True and rerun your case to see if you can get your expected partition results.

Hey @inducer @nhartland
Do you know why we prefer recursive partition method if nparts<8?