Skip to content
This repository has been archived by the owner on May 1, 2024. It is now read-only.

Multigraph support #62

Open
Lamaun opened this issue Oct 31, 2019 · 2 comments
Open

Multigraph support #62

Lamaun opened this issue Oct 31, 2019 · 2 comments

Comments

@Lamaun
Copy link
Contributor

Lamaun commented Oct 31, 2019

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
Copy link
Contributor Author

Lamaun commented Oct 31, 2019

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

@Lamaun
Copy link
Contributor Author

Lamaun commented Nov 3, 2019

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.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Development

No branches or pull requests

1 participant