search

networkx / networkx-metis

NetworkX Addon to allow graph partitioning with METIS
Other
79 stars 21 forks source link

Multigraph support #62

Open Lamaun opened 4 years ago

Lamaun commented 4 years ago

As the https://pypi.org/project/metis/ project supports networkx multigraphs, it should be possible. That project however doesn't support vertex cuts and its bitbucket was taken down.

Lamaun commented 4 years ago

I will be starting this weekend if no one had the time to do it until then.

Lamaun commented 4 years ago

Sadly the code in the other library seems to be faulty.

My testing Graph is

G=networkx.MultiGraph() G.add_edge(0,1) G.add_edge(2,1) G.add_edge(2,1) G.add_edge(2,1) G.add_edge(2,3)

Both libraries suggest to cut (2,1) and pretend its only one cut.

In the case of the vertex separator however, I think the current approach to throw an exception in the case of a MultiGraph isn't really necessary. I don't know much about how powerful metis is here, but as the cost of a vertex separator in the normal case is the number of vertices (or the sum of their weights) we should just take the MultiGraph, ignore multi edges and continue.

I removed the @nx.utils.not_implemented_for('multigraph') and that was enough for my current task. If you know some task where metis needs multi edge information for a vertex separator that would be nice to know.