Fix a bug in sort.cc and gklib.cc

[OrkoHunter]

Use of std::greater<>() for custom datatypes is not allowed. So, for them a separate comparison functor needs to be declared.

For gk_idx_t, the original sort.c compares the bare value of them,

void gk_idxsortd(size_t n, gk_idx_t *base)
{
#define idx_gt(a, b) ((*a) > (*b))
  GK_MKQSORT(gk_idx_t, base, n, idx_gt);
#undef idx_gt
}

While for others, their key attribute is compared,

void gk_ckvsorti(size_t n, gk_ckv_t *base)
{
#define ckey_lt(a, b) ((a)->key < (b)->key)
  GK_MKQSORT(gk_ckv_t, base, n, ckey_lt);
#undef ckey_lt
}

This fix is trying to do that. The build works fine for gk_idx_t but generates errors while processing other data types. Here[1] is the link of the original gist of the error.

[1] https://gist.github.com/OrkoHunter/d09271f9555ee8ac1caf

[OrkoHunter]

Don't know if it's good or bad, but the error is the same as before.

[ysitu]

Can you update your gist to show the latest error messages?

[OrkoHunter]

New gist

Old one

[OrkoHunter]

Didn't find much difference though. Let's see this warning for once cc1plus: warning: command line option ‘-Wstrict-prototypes’ is valid for C/ObjC but not for C++ [enabled by default] It seems that c and cc files should be compiled separately with gcc and then linked together with g++. I found it here.

[ysitu]

You need to define a gk_kv_t_less similar to gk_kv_t_greater and use it as appropriate.

[OrkoHunter]

I hoped std::sort() might handle the increasing order by default. Let me try that.

[ysitu]

std::sort knows how to sort but not how to compare. That is why you need to provide a comparison functor.

[OrkoHunter]

I think the problem with sort.cc is resolved. Moving on to gklib.cc.

[OrkoHunter]

Updated PR with more comparison functors. I guess we are out of any problems in sort.cc. Yet, there is a small bug in gklib.cc in the part which does not deal with the sort.

Error Gist

[ysitu]

Can you diagnose the problems?

[OrkoHunter]

Yes. I'm trying to resolve it. I'll give you the update soon.

[OrkoHunter]

The problem with the build was due to

GK_MKBLAS(i,  idx_t,  idx_t)
GK_MKBLAS(r,  real_t, real_t)

in gklib.cc. I guess it occurred because of mangling of C++ function names. I tried putting it inside and outside of extern "C" but nothing worked. So, I just commented it out and the build_lib worked successfully!

[ysitu]

You simply removed the offending functions. Are you sure that they are not used anywhere? Your gist shows three warnings/errors:

• warning: deprecated conversion from string constant to ‘char*’
• error: invalid conversion from ‘void*’ to ‘void**’
• warning: comparison between signed and unsigned integer expressions

Would it be more appropriate to address them directly?

[OrkoHunter]

I've put them on hold. I kinda believe they are not being used anywhere. If no problem occurs, we'll address the changes.

[OrkoHunter]

Making a separate gklib_sort.cc did the job. Build worked fine. I can't test it though. I'm getting many relative import errors. At one place there's a cyclic import too where _metis imports _types and then _types imports _metis back. I'm on it.

[chebee7i]

It seems like one issue with namespace packages that are required to use absolute imports is that you can't test them without installing them. All this is avoided if we let network_metis be its own package with a networkx importing it all, but I suppose pip install -e . should be sufficient.

[OrkoHunter]

What about networkx_metis being a proper package instead of a namespace package? I understand that namespace packages are more suited here but let us think about it being a proper package. The prototype can remain the same as expected earlier.

>>> import networkx as nx
>>> from networkx.addons import metis
>>> metis.partition(..,(..))

In the networkx.addons.metis module there will be a small piece of code

try:
    from networkx_metis import *
except ImportError:
    print("Please install networkx_metis to use this addon")

We can also add proper documentations here which will show up on the official networkx doc.

In both the methods, I see the difference only in the design, but less from the user point of view. Let us please talk about it. It hasn't been discussed earlier.

[ysitu]

Making networkx.addons.metis a stub forces you to distribute two packages instead of one. (We should not bundle networkx.addons.metis into NetworkX proper because that unnecessarily enforces an interface for integration.) Asking the user to install two packages to get one functionality is one package too many.

I think that the correct approach is to establish an automated testing workflow. Instead of manual build-and-run, we should have a script that installs the packages and runs tests.

[chebee7i]

@ysitu wouldn't users have to install the addon anyway? I didn't think we would be providing it in the default situation. So it's already going to be more than one package to install.

[chebee7i]

And yes, an automated test script would be simple and nice to have too.

[OrkoHunter]

We should not bundle networkx.addons.metis into NetworkX proper because that unnecessarily enforces an interface for integration

But, for namespace packaging too, there has to be a networkx.addon package with an __init__.py with a single line code in it. So, having an addon repository in the networkx proper with the least possible documentation too is more ambiguous than having some modules for addons with more informaton in it.

And anyhow, a user will have to install both the packages to use the single feature. I don't think namespace packages allow us to get away from this.

[ysitu]

What I mean by two packages is network-metis and the import stub. Adding NetworkX itself that is three packages.

The one-liner in networkx/addons/__init__.py is generic, but networkx/addons/metis.py is not. You force people to create a package networkx_metis.

[OrkoHunter]

networkx-metis would just be the name of the repository over github containing networkx_metis. User has to install networkx_metis package from pip or other way. So by the count of packages, it's still not clear how can we count three.

The point with generic one liner is valid.

[ysitu]

The import stub has to be injected into networkx.addons upon installation. So you have to distribute it separately from networkx-metis because you do not let the latter do the same thing. That makes them two separate packages.

I think that it is still too early to declare injecting into a namespace not doable. networkx-metis will not be the first package to attempt that and run into the problems that you are facing. Some more research is worth investing.

[OrkoHunter]

@ysitu Is this ready to be merged? I think we do not have any problem with the library now. I'll update the NOTICE file with the last change i.e. gklib_sort.cc.