Implementation of Weisfeiler-Leman algorithm

[Keshav Kini]

Hello,

I have put together a patch which adds a module "sage.graphs.wlrefine"
and implements the Weisfeiler-Leman algorithm for coherent partition /
graph refinement, using an algorithm by Dmitrii Pasechnik and Luitpold
Babel. I have uploaded it here:

http://www1.spms.ntu.edu.sg/~krkini/temp/sage-wlrefine.patch (to be
applied to the repository in $SAGE_ROOT/devel/sage )

This code is taken from a mini-package of C code I am nominally
maintaning. The README of this package, which describes the purpose of
the algorithm, can be found here: http://www1.spms.ntu.edu.sg/~krkini/hg/hgweb.cgi/stabprogs/file/tip/README

As I'm pretty new to sage, I wonder if someone could tell me if I'm
doing everything in the proper way. In particular, when I open sage
after applying the patch, the module sage.graphs.wlrefine contains a
submodule sage.graphs.wlrefine.sage, which is bound to the root module
sage. I have tried and failed to figure out why this is occurring...

Also, is it appropriate to dump .c and .h files into $SAGE_ROOT/devel/
sage/sage/graphs as I have done, or should I have created a
subdirectory for two files? In fact, is sage.graphs even the correct
place to put this code?

There is a comment in STABIL.c which says something about line
continuation and doctests, but this should hopefully be fixed by my
patch at trac #10458 ( http://trac.sagemath.org/sage_trac/ticket/10458
).

Yours,
Keshav Kini

[Keshav Kini]

Hi Minh,

On Dec 14, 9:07 pm, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> [...]
> Your patch adds the following source files to the Sage library:
>
> * STABIL.c
> * STABIL.h
>
> both of which are explicitly licensed under the terms of GPLv3. A
> policy of the Sage project is to include only code licensed under the
> terms of the GPLv2+ in the Sage library. That means that any code that
> goes into the Sage library must be covered by the GPL version 2 or any
> later version, but not explicitly version 3. Here are some options I
> can think of to remedy the situation:
>
> (1) Relicense your C source files under the terms of the GPLv2+, after
> which you should be able to get your C source files into the Sage
> library.

That would be fine with me, but the original implementation by Dmitrii
Pasechnik and Luitpold Babel is licensed under GPLv3+, and while my
code doesn't technically use any lines from the original
implementation, it borrows heavily from the organizational structure
(after all, it uses the same algorithm), so if I understand correctly
it would be improper to relicense my own code, even if the original
authors permitted it - even the original authors cannot now relicense
their GPLv3+ code as GPLv2. (Please correct me if this understanding
is incorrect.)

> (2) Create a Sage package (also known as an spkg) and write an
> interface to your spkg. Anything in the interface that is licensed
> under GPLv2+ can be included in the Sage library. For everything else,
> you need to include them in your spkg. See this [1] from sage-devel on
> options for packaging your code so that the spkg can be distributed
> with Sage.

I actually have created an spkg as well, which works fine. However,
distributing a mere two functions consisting of less than 40 KB of
code seemed like sort of a waste, especially considering that the user
would then need to import a base-level package "wlrefine" instead of
immediately being able to use it. Or is that what you meant by
"writing an interface to" the the spkg? Just putting a .py file in
$SAGE_ROOT/devel/sage/sage/graphs/ that loads the module from the
spkg? I notice that you didn't list the .pyx file the patch also adds
(wlrefine.pyx) - I guess that could be called an "interface" to the C
code. Is that what you mean?

> > There is a comment in STABIL.c which says something about line
> > continuation and doctests, but this should hopefully be fixed by my
> > patch at trac #10458 (http://trac.sagemath.org/sage_trac/ticket/10458
> > ).
>

> See the following sage-devel thread for discussion on this matter:
>
> https://groups.google.com/group/sage-devel/browse_thread/thread/d6125...

Yes, thanks for publicizing my trac ticket! :)

Yours,
Keshav

[Dima Pasechnik]

certainly, I can relicense whatever was under v3 to v2, if needed.
Dima

[Dima Pasechnik]

On Dec 14, 10:10 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
> certainly, I can relicense whatever was under v3 to v2, if needed.

the original is now under GPLv2.
So you can go ahead and put your code under v2, as well.

[Jason Grout]

On 12/15/10 3:09 AM, Dima Pasechnik wrote:
>
>
> On Dec 14, 10:10 pm, Dima Pasechnik<dimp...@gmail.com> wrote:
>> certainly, I can relicense whatever was under v3 to v2, if needed.
>
> the original is now under GPLv2.
> So you can go ahead and put your code under v2, as well.

GPLv2, or GPLv2+ (version 2 or later)? It would need to be GPLv2+ to be

included in the Sage library.

Thanks,

Jason

[Dima Pasechnik]

v2 or later.
and yes, Sage code should also go under v2 or later.

[Keshav Kini]

Thanks, Dima!

I have done so. I've also added a feature, a bugfix for it, and a
doctest for it. Here is the new patch:

http://www1.spms.ntu.edu.sg/~krkini/temp/sage-wlrefine.patch

Same URL, new file. If you would like to see the old patch, stick a
".old" on the end of the URL. Is this patch about ready to be posted
to a trac ticket?

Thanks,
Keshav