Add METIS addon for NetworkX

[OrkoHunter]

This adds the source files and license of METIS

[ysitu]

Is the top-level networkx_metis directory necessary? I understand that this is a practice taken from the NetworkX core, which enables in-source tree testing (you can run nosetests without installing). But in this case, I do not see how you can test without installing. So the networkx_metis directory is probably not needed.

[OrkoHunter]

It is not necessary though I thought it's a cleaner way and we cannot import a module named networkx-metis because - is not allowed for module names. Also, the repository's name expresses its meaning NetworkX-Metis. I had no other arguments for this.

[ysitu]

setup.py is going to install the stuff into networkx.addons.metis (see https://pythonhosted.org/setuptools/setuptools.html#namespace-packages). So your module will not be named networkx-metis anyway.

[OrkoHunter]

@ysitu That's clear now. Earlier I was thinking of the alternative of installing the add-on as proper package and calling it from the respective namespace from networkx.addons as

>>> from networkx.<addon> import *

I'll look into namespace packages and how it works.

[OrkoHunter]

Just removed the top level networkx_metis directory from all three PRs.

[ysitu]

Is there any particular order in which your PRs should be merged?

[OrkoHunter]

1 , #2 and then #3 after changes in __init__.py (To suit the namespace package installation).

Later on #4 have pending works. Files like MANIFEST.in have to be added if required (I think it is) and setup.py needs changes too.

Edit : #6 should get in before #4.

[OrkoHunter]

I did some work in #4. @ysitu Please have a look. And kindly give notes in setup.py.

[ysitu]

Apparently I cannot merge PRs here. @hagberg Can you make me a collaborator of this repository?

[hagberg]

I added the networkx-dev team.

[ysitu]

Please amend the commit to give it a better description. At the least you need to mention that it is the METIS source code that is being added.

[OrkoHunter]

@ysitu Ping.

[ysitu]

Let's move ahead with the effort to remove the LGPL bits. Out of the six LGPL files named in #6, all but sort.c can be simply removed. We do not need to handle command line options or regular expressions in this project. sort.c can be replaced by a sort.cc written in C++. Make sure that you export the functions with a correct ABI (extern "C" is your friend), and setup.py knows how to build it.

[OrkoHunter]

I'll get on it. Thanks for the extern "C" thing. It's really helpful.

[OrkoHunter]

@ysitu We are good to go. metis.partition works on my system. I can add some more comments in sort.c, sort.h or sort.cpp if you think so.

[ysitu]

Can you squash the last two commits so that those files do not appear in the commit history?

[OrkoHunter]

@ysitu Ping. You meant about those four files only, right?

[ysitu]

I meant that you should squash all commits so that all the six original files do not appear in the commit history.

[OrkoHunter]

Done.

[ysitu]

I don't understand. Your previous implementation using stuff from <functional> was good. Why did you remove that? There is no need for the C macro hackery now that you use C++.

[OrkoHunter]

Using <functional> I was able to replace all the interiors of GKlib/sort.c. That was fine. But in libmetis/gklib.c, there are some functions in which the sorting order is not merely based on increasing or decreasing value. One example is this. There are many more.

/* Sorts based both on key and val */
void ikvsortii(size_t n, ikv_t *base)
{
#define ikeyval_lt(a, b) ((a)->key < (b)->key || ((a)->key == (b)->key && (a)->val < (b)->val))
  GK_MKQSORT(ikv_t, base, n, ikeyval_lt);
#undef ikeyval_lt
}

So, I kind of felt the need of using function-like macros to pass the CMPR operator.

There might be another way but I don't see it.

[ysitu]

You can define a comparison functor:

// Use an anonymous namespace so that ikv_t_less cannot be accessed from another file.
namespace {

struct ikv_t_less {
    bool operator()(const ikv_t &lhs, const ikv_t &rhs) const {
        return std::make_pair(lhs.key, ls.val) < std::make_pair(rhs.key, rhs.val);
    }
};

}  // anonymous namespace

/* Sorts based both on key and val */
extern "C" void ikvsortii(size_t n, ikv_t *base)
{
    std::sort(base, base + n, ikv_t_less());
}

A C++11 lambda is also a solution. But because currently not all compilers enable C++11 by default, I think that it is better to use a functor class.

[OrkoHunter]

The problem earlier was that we cannot change gklib.c. So, all the changes we are going to make is in sort.h and sort.cpp. So, the comparison functor method can be implemented in sort.cpp and sort.h as well?

[ysitu]

Why can't you change gklib.c? I think that you can change to it gklib.cc if necessary.

[OrkoHunter]

That was weird actually. As soon as I rename it, building errors like libmetis__rpqSeeTopVal not defined started generating. Even if these are already defined in gklib_rename.h as

#define rpqSeeTopVal libmetis__rpqSeeTopVal

In the same file, there is a line

/* gklib.c - generated from the .o files using the ./utils/listundescapedsumbols.csh */

which might suggest something that gklib.c has to remain the same.

Apart from this, I also think redirecting GK_MKQSORT() is a good way in which we are not changing much of the existing code rather implementing our own.

[ysitu]

Did you wrap the #include's in extern "C" { }?

[OrkoHunter]

No, I just wrapped the functions. That was the problem, wasn't it?

[ysitu]

You need to put the #include's in your renamed gklib.cc in extern "C" { } because the declared functions are C functions.

[OrkoHunter]

In that case, I don't think sort.h and sort.cpp is required. Let me make those changes.

[OrkoHunter]

Change log: gklib.c -> gklib.cc sort.c -> sort.cc sort.h and sort.cpp are not needed anymore.

[ysitu]

I am merging this. Please document your changes to METIS as required by the Apache License in a follow-up PR.