Graph partitioning with METIS

[ysitu]

I wonder if there is interest in integrating METIS and the how if so.

[hagberg]

METIS is truly awesome software. There are some Python wrappers already available but I haven't tried them. Is the idea to connect to one of those? If by 'integrating' you mean to include the C source or other non-Python wrappers then I think it would be better as a separate package.

[chebee7i]

Maybe in the form of readers to/from the METIS format? Possibly some callers that then bring the output back into Python?

[ysitu]

How about managing it as a Git submodule hosted at a separate repository and referencing it from setup.py as an optional component? I think that people who want METIS will find it convenient to have a simple mechanism to pull everything together.

[chebee7i]

Yeah, I could see that. NetworkX could probably host that repository too, which might make them formally a bit more coupled then if it associated with another github account. We could always experiment with the submodules and optional components.

[ysitu]

In general, a networkx.addons namespace can be created to house stuff that may or may not exist or be written in pure Python.

[jtorrents]

The git submodule approach (and hosting the repo under networkx github account) sounds good to me. The idea of a namespace with optional addons or wrappers to specific tools has been around for a long time, and I think it would be very useful. However I'm not sure how much will increase the complexity of installing/developing/maintaining NetworkX. I think this is important. Maybe we can experiment with this approach with the METIS wrappers. We've discussed the addons or nxtools namespace approach several times in different places and context, so it will be useful beyond METIS.

By the way @ysitu, I see that you have already been working on this: https://github.com/ysitu/networkx/tree/metis . On a first sight, it seems that changes in METIS source code are necessary (I don't know how important are they). Do you think that we could pass those changes upstream? Having a wrapper would be very useful, but maintaining a fork could be painful.

[ysitu]

@jtorrents My experiment with METIS largely consists of three parts. The first part is METIS itself, a Cython wrapper and some other helper classes that live in networkx.external.metis. They provide a thinnest abstraction of METIS. To break out of NetworkX's dependence hell, this part is totally self-contained. The second part is some glue code added to NetworkX that interfaces between NetworkX objects and bare lists/arrays expected by the first part. This includes everything in networkx.algorithms.partition, a new decorator in networkx.utils and some extra code to put some functions into the top-level namespace. The last part is a modified setup.py that handles installation-related issues including skipping the new parts when Cython is not available.

I believe that some modifications in NetworkX itself are necessary in order to accommodate optional components (at the least you need to declare the components in setup.py for installation). The question is how. My approach with METIS is intrusive. But it can certainly be made less so. For example, we can define a networkx.addons.AddOn class which each add-on should subclass in a specific way. Then a more OOP-friendly setup.py can then reference the subclasses of AddOn to modify its installation configuration. Ultimately, the idea is to provide an interface so that add-ons can be cleanly added and removed (ideally, it should be as simple as adding and deleting subdirectories under networkx/addons/).

[chebee7i]

Related:

https://pypi.python.org/pypi/metis (pure Python)
https://pypi.python.org/pypi/PyMetis (Boost.Python)

PyMetis doesn't seem like it fits as nicely (b/c it seems not to interop with NetworkX), but metis does. @ysitu is your code mostly the same as metis in terms of functionality but implemented in Cython?

[chebee7i]

For AddOn...so one example would be Metis(AddOn) which configures a Cython Extension class and then setup.py grabs it and adds it? Seems reasonable.

Btw, I saw how you currently modified setup.py. From what I've seen, that's a pretty standard way to optionally add Cython support...so that's good. One thing that might be helpful is to provide a way to turn off Cython extensions, even when Cython is available. I've done something hackish and checked for a --nocython flag.

The other route---and its one to take if we want to keep NetworkX and its installs primarily pure Python---is that no Cython extensions are setup unless: 1) it was explicitly requested via a flag as in:

python setup.py install --cython
pip install networkx --install-option="--cython"

and 2) Cython is actually available [with a hard failure if 1) is true and 2) is not true].

---

Also, what is your thought on the completely separate route. E.g.:

pip install cymetis
pip install networkx

Then in networkx/algorithms/__init__.py:

    from .partition import *

where networkx/algorithms/partition/__init__.py does:

__all__ = []
try:
    import cymetis
except ImportError:
    pass
else:
    from cymetis.nxapi import *
    __all__.extend(cymetis.nxapi.__all__)

This keeps nearly all metis-related code together and requires only the simplest code in NetworkX. I'm wondering if this scale better to many different optional packages. Curious to hear others thoughts. If we went this route, I think the NetworkX documentation would need a dedicated page highlighting support packages that, when installed, provide additional functionality.

[ysitu]

@chebee7i Interop with NetworkX is largely a nonissue. The biggest problem with PyMetis is that it is basically unmaintained. Also, relying on Boost.Python will make your life tricky when you have Python 2/3 coexisting. But I consider metis to be an even worse solution. Requiring the user to specify the width of a typedef through an environment variable is a nonstarter. METIS also has its own quirks that need to be worked around (crashing on self-loops, sending error messages to stdout, etc.).

Regarding my code, you have to consider that experimental. If add-ons are to be supported, modifying setup.py for every single one of them will inflate the file very quickly. My preferred model is what I mentioned above. setup.py should inspect and load configurations from networkx.addons and let the add-ons decide if they can be installed. No names need to be pulled out of the networkx.addons namespace.

[chebee7i]

Ok yeah, I can see that. So then the addons are completely distinct (just shipped with NetworkX, possibly via submodules, for added convenience). The idea then would be that Networkx proper should never look inside networkx.addons at all. But things in networkx.addons will certainly look into NetworkX.

[ysitu]

@chebee7i Yes, NetworkX proper should not assume that an add-on will reliably exist, otherwise, that add-on should really become an integrated part of NetworkX.

[hagberg]

What is the advantage of "optional components" vs a completely separate and compatible package?

[ysitu]

@hagberg First, it facilitates distribution. Consider the scenario of providing a METIS wrapper for Windows. For those who just want to use Python, it is a big hassle to install Visual Studio/Windows SDK/MinGW/Cygwin to get a compiler for pip. So you want to use prebuilt packages. There are people out there who maintain those for Windows. But by no means can or will they cover all packages, especially new or lesser-known ones. Bringing the wrapper and alike under the umbrella of NetworkX increases the chance that they are picked up by these maintainers.

Second, while discussion in some previous comments seemingly suggests drawing a clean line between NetworkX proper and the optional components, I think that a blurrier line is more useful. Through a properly designed interface, NetworkX can be allowed to replace some built-in bits with code from the optional components. Consider #1134. If you happen to have PARDISO, you may want to inject it as a replacement for CHOLMOD and SuperLU. Without NetworkX defining a protocol, such patch work can be hackish and unreliable. Another important use case is to enable native implementations of algorithms, especially those with superquadratic time complexities. For example, as I mentioned in #1082, NetworkX runs slower on a recent Xeon server than native code did in 1995. If you have an alternative preflow–push implementation that is practical for hundreds of thousands if not millions of nodes, you want nx.maximum_flow to just become fast instead of having to scour your code base to find the places to add the flow_func arguments (and you have to thank #1102 for being able to do so at all).

[chebee7i]

Sounds interesting. Would love to see how this might (or might not) work.

[jtorrents]

Good points @ysitu. I also think that, having some "optional components" under the NetworkX umbrella, will also make these components easier to maintain and to contribute to (we already have a workflow in place, and a small team of people that will look at things if they do not work). In general, I think it will decrease the likelihood that those optional packages become unmaintained. A lot of packages out there depend on only one or very few maintainers. This also means that we should be careful on what we consider "official optional component", we have to be sure that we (or someone we trust) will be able to maintain it in the future.

Regarding the more technical aspects, I cannot comment much because I'm not competent in low level languages/details (my background is in the Social Sciences, and I can only program in python and R). But having a solid and standardized way of being able to replace some NetworkX functions for alternative implementations, sounds very useful and a powerful mechanism of customizing NetworkX.

[OrkoHunter]

Hi,
This idea seems great to me! I would like to work on it.

[OrkoHunter]

In the project, Metis seems to be very recommended. I would like to know whether we are planning to add Boost Graph and Lemon both or just one of them? Please tell. That will confine my area of interest.

[ysitu]

@OrkoHunter AFAIK, your proposal is to work on an add-on system instead of merely integrating METIS. Then the important part is the add-on system itself. This can be nontrivial. Requiring inclusion of at least two add-ons aims to show three things: 1) that your add-on system works; 2) that your system is general-purpose, not tailored to just one use case; 3) how others can create add-ons using your system.

[OrkoHunter]

@ysitu @hagberg @chebee7i @jtorrents
For a while, I've been working on my proposal. Now I think it's ready for a review.
Please have a look and give suggestions.

https://github.com/networkx/networkx/wiki/GSoC-2015-Application-Himanshu-Mishra-:-Add-On-System-for-Networkx

I still have to work on the prototype.

[ysitu]

I am preparing an initial review.

[OrkoHunter]

@ysitu Thanks!

[MridulS]

I think this can be closed now.