Interface with TdLib - Githubissues

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

Interface for tdlib, a library concerning treedecompositions

Containes the glue-code for

an exact algorithms for computing a treedecomposition/the treewidth of a graph

Upstream: http://www.tdi.informatik.uni-frankfurt.de/~lukas/data/tdlib-0.3.1.tar.gz

CC: @dcoudert

Component: packages: experimental

Author: Lukas Larisch

Branch/Commit: 0308199

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19249

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

Branch: u/llarisch/interface_with_tdlib

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

New commits:

6a6b47b Interface with TdLib, a library concerning treedecompositions

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

Description changed:

--- 
+++ 
@@ -1 +1,8 @@
+    Interface for tdlib, a library concerning treedecompositions
+    
+    Containes the glue-code for
+- treewidth-lower bound algorithms
+- heuristics for computing treedecompositions
+- exact algorithms for computing a treedecomposition/the treewidth of a graph
+- the seperator-algorithm (4-approximate)

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

Commit: 6a6b47b

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:4

Hello,

This looks very nice indeed, but because I expect the review to be rather long in this case, it would probably be best to start by exposing a reduced amount of features from your library. A general function to compute the treewidth exactly, for instance, would be ideal as we would be able to compare its output with what we already have (which is slow).

For a start, I guess that some things should be done directly in your library: is it necessary to have Sage apply a patch to it? Is there a reason why what your patch does cannot already be included in your code?

Your makefile appears to be manual, and it would probably be best to have it created by autotools. I had to learn this not so long ago and I found it rather painful to learn, but the purpose is to make sure that your code will compile everywhere, so that you do not need to test every platform manually. I can probably help with that, as well as send you a pdf book that helped me a lot while learning it.

Finally, I am not sure if you are aware that you can have C instructions in a 'def' function of a cython file. I see that you have several cdef cython_<something> functions with a def <something> couterpart, and there is no technical reason to do that. If you have another reason for doing this, then consider this remark as an mistake from my part.

Is your code available on some web page? Is there a public repository for it? Are you the only author? Are there theoretical publications related to it? This kind of information would be interesting to us, and is expected to be found in a SPKG.txt file.

http://doc.sagemath.org/html/en/developer/packaging.html#the-spkg-txt-file

Regards,

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

0beb7e2 reduced functionality

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 6a6b47b to 0beb7e2

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:6

While testing my version of an exact algorithm for treewidth against the sage version, i noticed that the sage version doesnt work: it is NOT sufficient to just consider the neighbourhood of computed cut. Counterexample:

G = Graph() G.add_vertex(0) G.add_vertex(1) G.add_vertex(2) G.add_vertex(3) G.add_vertex(4) G.add_vertex(5) G.add_vertex(6) G.add_vertex(7) G.add_vertex(8) G.add_edge(0,2) G.add_edge(0,3) G.add_edge(0,5) G.add_edge(0,6) G.add_edge(1,4) G.add_edge(1,8) G.add_edge(2,8) G.add_edge(3,4) G.add_edge(4,5) G.add_edge(4,7) G.add_edge(6,8) G.add_edge(7,8) G.treewidth()

But G has treewidth 2. (you possibly have to change the vertex labeling to see the error).

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:7

Right, this graph clearly has width 2 O_o

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:8

Replying to @nathanncohen:

Right, this graph clearly has width 2 O_o

And the error can be arbitrary bad. One can construct a graph, such that a cut is not connected in a graph and has to be included in a bag of a tree decomposition. Here it is {0,4,8}.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f0bfdb9 small enhancements

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 0beb7e2 to f0bfdb9

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:10

For a start, I guess that some things should be done directly in your library: is it necessary to >have Sage apply a patch to it? Is there a reason why what your patch does cannot already be >included in your code?

I have to instantiante template functions and convert a "sage graph" to a boost graph.

Your makefile appears to be manual, and it would probably be best to have it created by autotools. >I had to learn this not so long ago and I found it rather painful to learn, but the purpose is to >make sure that your code will compile everywhere, so that you do not need to test every platform >manually. I can probably help with that, as well as send you a pdf book that helped me a lot while >learning it.

Is there a minimal example for that?

The "tdlib"-part of the documentation has failed to build (UNABLE TO IMPORT MODULE): Is there some import-statement missing? What can be the reasons (its not the content of the *.pyx-file)?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:11

I have to instantiante template functions and convert a "sage graph" to a boost graph.

I still believe that you can do it without patching your code. Let your code deal with boost graphs only, and let Sage only call it on Boost instances (see sage/graphs/base/boost_graph.pyx). This issue should not be a reason to patch your library.

Your makefile appears to be manual, and it would probably be best to have it created by autotools. >I had to learn this not so long ago and I found it rather painful to learn, but the purpose is to >make sure that your code will compile everywhere, so that you do not need to test every platform >manually. I can probably help with that, as well as send you a pdf book that helped me a lot while >learning it.

Is there a minimal example for that?

All over internet. One that was done recently for Sage is there: https://github.com/graph-algorithms/edge-addition-planarity-suite

The "tdlib"-part of the documentation has failed to build (UNABLE TO IMPORT MODULE): Is there some import-statement missing? What can be the reasons (its not the content of the *.pyx-file)?

Probably something like that: http://doc.sagemath.org/html/en/developer/sage_manuals.html#adding-a-new-file

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:12

Or, otherwise, because you should import your module like others, as it is done in all.py?

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:13

Is there a way to generate a boost graph with an appended struct? I've seen that

ctypedef BoostGraph[vecS, vecS, undirectedS, vecS, EdgeWeight] BoostVecWeightedGraph

exists, but I would need:

ctypedef BoostGraph[vecS, vecS, undirectedS, vecS, X] BG,

such that X is a vertex property. Is there a (not too complicated) way to realize this?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:14

I do not know of one.

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:15

Replying to @nathanncohen:

I do not know of one.

In this case, the patches are inevitable (treedecompositions are boost graphs with a set as a vertex property). I could merely displace some graph conversion stuff into the library..

Does automake cp & rm files automatically? If this is the case: which flags have to be passed to autoconfig on the sage side in spkg-install? So far:

AC_INIT(tdlib, larisch@informatik.uni-frankfurt.de)
AM_INIT_AUTOMAKE([subdir-objects] [foreign])

# The version of the libtool library is of the form current:revision:age
#
# See http://www.gnu.org/software/libtool/manual/html_node/Updating-version-info.html
#
# When doing a release, they should be updated like this:
# 1. If no interfaces changed, only implementations: just increment
# revision.
# 2. If interfaces were added, none removed: increment current, set
# revision to zero and increment age.
# 3. If interfaces were removed (breaks backward compatibility): increment
# current, and set both revision and age to zero.
LT_CURRENT=0
LT_REVISION=0
LT_AGE=0
AC_SUBST(LT_CURRENT)
AC_SUBST(LT_REVISION)
AC_SUBST(LT_AGE)

AC_PROG_CXX
AC_PROG_LIBTOOL
AC_PROG_INSTALL

CXXFLAGS="-O3"

AC_OUTPUT(Makefile)

lib_LTLIBRARIES = libtd.la

libtd_la_SOURCES = sage_tdlib.cpp
libtd_la_LDFLAGS = $(AM_LDFLAGS) -version-info @LT_CURRENT@:@LT_REVISION@:@LT_AGE@

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:16

In this case, the patches are inevitable (treedecompositions are boost graphs with a set as a vertex property). I could merely displace some graph conversion stuff into the library..

Yes. Your library has no reason to be able to handle Sage graph, so just write Sage code to call it with the kind of graph that it expects.

Does automake cp & rm files automatically? If this is the case: which flags have to be passed to autoconfig on the sage side in spkg-install? So far:

I do not understand this question.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:17

Hello,,

While testing my version of an exact algorithm for treewidth against the sage version, i noticed that the sage version doesnt work: it is NOT sufficient to just consider the neighbourhood of computed cut. Counterexample:

Thank you very much for this bug report. It has been fixed in #19358 (needs_review).

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a7aa88c new build-system

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from f0bfdb9 to a7aa88c

jdemeyer commented 8 years ago

comment:20

Some technical points: the source tarball is not meant to be committed, you should just provide a link on this ticket (or attach it to this ticket).

Second, can you write to upstream about the autotools-based build system? Ideally, it should be added to upstream instead of Sage.

Third, autotools is not part of Sage: you must not run autogen.sh in spkg-install. If upstream does not want autotools, then you should put the autotools-based build system in the source tarball directly (both the autotools source files and the generated files).

jdemeyer commented 8 years ago

comment:21

Two more details:

Unfortunately you cannot add the tdlib module to the documentation, since we currently do not support "optional" documentation.
Please undo the added whitespace to module_list.py.

jdemeyer commented 8 years ago

comment:22

Also, is there any reason that you have the file sage_tdlib.hpp twice? Surely, one time is enough. I even think that zero times is enough if you move the .cpp file to the Sage library and use http://docs.cython.org/src/userguide/external_C_code.html#implementing-functions-in-c

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:23

Could you remove the compiled libraries from the hidden directory .lib of your archive?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

d661cb6 - removed entry in the doc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from a7aa88c to d661cb6

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

140dde4 reduced functionality

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from d661cb6 to 140dde4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

11f4521 updated upstream contract

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 140dde4 to 11f4521

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:27

Just to be sure: The upstream tarballs are just copies of "original tarballs" and will be downloaded from sage mirrors?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:28

Just to be sure: The upstream tarballs are just copies of "original tarballs" and will be downloaded from sage mirrors?

Indeed. And when the original (aka 'upstream') tarball is updated (and if we want this update to be reflected in Sage) then we must open a ticket to update it. That's the workflow nowadays.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

9bc9d3d rm tarball

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 11f4521 to 9bc9d3d

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:30

(please don't forget to set the ticket's status to 'needs_review' when you will be done with your modifications)

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f438342 fixed copy&paste error

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 9bc9d3d to f438342

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

Reviewer: Nathann Cohen

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:33

Helloooooooooo Lukas,

Here is another review:

From the url at which you placed your tarball I found your website, and this page [1] really looks like "TdLib's official page". Could you add this url at the end of the 'description' section of the SPKG.txt file?
It would be cool if your tarball contained a 'license' (or 'copying') file asserting that it is licensed under the GPL2.
I do not understand why you need to copy/paste sage_tdlib.cpp into your tarball if you want it to compile. Could you please explain me? In no other package do we need to do such a thing. Usually the tarball works by itself, and we have in Sage some interface code that is linked with it.
One such instance is the interface with boost. You will find it in the following files:

sage/graphs/base/boost_graph.pyx sage/graphs/base/boost_graph.pxd sage/graphs/base/boost_interface.cpp
Your 'spkg-install' file copies files that you removed from your tarball (i.e. ./.libs/*)

I do not understand what exactly this warning means. Could you tell me? ^^;

+#!!!!!!   NOTICE   !!!!!!!!
+#Sage vertices have to be named by unsigned integers
+#Sage bags of decompositions have to be lists of unsigned integers
+#!!!!!!!!!!!!!!!!!!!!!!!!!!

Could you strip 'cython_' from the beginning of the functions you define?
The code of get_width can be replaced by:
```
return max(len(x) for x in T)-1
```
It is slightly incorrect to have your class TreeDecomposition inherit from Graph, while having a function like get_width rely on the vertices' labels (you assume that they are sets). Indeed, the vertices of a graph can be relabeled, which would break this function. I don't think that you need this class, to be honest.

We have something like for(auto i: something) in python. You can rewrite

+    V_python = G.vertices()
+    for i in range(0, len(V_python)):
+        V.push_back(V_python[i])

As

+    for v in G:
+        V.push_back(v)

(it occurs several times in your code)

Similarly (don't scream -- I know it can hurt when you see it for the first time) you can write this in Python:
```
a,b = 1,2
```
Which means that this also works
```
for u,v,l in G.edges():
  E.push_back(u)
  E.push_back(v)
```
Note that if you don't need the labels, then this also works:
```
for u,v in G.edges(labels=False):
  E.push_back(u)
  E.push_back(v)
```
Some of your 'TEST' and 'EXAMPLE' tags are not indented as they should (4 spaces).

Nathann

[1] http://www.tdi.informatik.uni-frankfurt.de/~lukas/

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from f438342 to e968b23

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

e968b23 url in SPKG.txt, added LICENCE.txt (upstream), stripped cython_, replaced get_width, simplified some code (for auto i: ..), updated tests and examples

68b0b521-a811-4f89-aec0-938c69d78a44 commented 8 years ago

comment:35

Thanks for the hints!

I do not understand why you need to copy/paste sage_tdlib.cpp into your tarball if you want it to compile. Could you please explain me? In no other package do we need to do such a thing. Usually the tarball works by itself, and we have in Sage some interface code that is linked with it.

One such instance is the interface with boost. You will find it in the following files:

sage/graphs/base/boost_graph.pyx sage/graphs/base/boost_graph.pxd sage/graphs/base/boost_interface.cpp

Since there is no cython-way to generate a boost graph with an appended struct for the vertices (boost_graph.pyx only supports appended structs for edges), a boost graph has to be generated manually (make_tdlib_graph in .pyx, sagetdlib).

If there would exist a cython-interface for the required graphs, one could build the .so by instantiating the exact algorithm, which would require to copy a .cpp file (that only containes a line that instantiates the exact algorithm) and a makefile into the tarball.

Do you have a idea for this?

Your 'spkg-install' file copies files that you removed from your tarball (i.e. ./.libs/*)

./libs is generated by make (automake creates a .libs by default) -> ./libs should exist

I do not understand what exactly this warning means. Could you tell me? ^^;

+#!!!!!!   NOTICE   !!!!!!!!
+#Sage vertices have to be named by unsigned integers
+#Sage bags of decompositions have to be lists of unsigned integers
+#!!!!!!!!!!!!!!!!!!!!!!!!!!

G.vertices() should return a list of unsigned integers, e.g. treedecomposition_exact() does not work with TutteGraph(), since TutteGraph().vertices() returnes a list of tuples

It is slightly incorrect to have your class TreeDecomposition inherit from Graph, while having a function like get_width rely on the vertices' labels (you assume that they are sets). Indeed, the vertices of a graph can be relabeled, which would break this function. I don't think that you need this class, to be honest.

Ok, i just thought something like that would be nice:

sage: T = tdlib.treedecomposition_exact(G) tree decomposition of width 4 computed sage: T Treedecomposition of width 4 on 15 vertices <--

Would it be better to use g.name("tree decompostion") for this purposes?

Lukas

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:36

Hellooooooooooooooo,

If there would exist a cython-interface for the required graphs, one could build the .so by instantiating the exact algorithm, which would require to copy a .cpp file (that only containes a line that instantiates the exact algorithm) and a makefile into the tarball.

Do you have a idea for this?

I'm still not understand exactly what you explain. I may be missing something obvious, but we will probably understand each other eventually:

I understand from what you tell me that the graph data structure that is used in your library is not exactly a boost graph, but 'a boost graph plus something'.

If this 'something' is about a list of labels for vertices, then it probably means that boost_interface should be updated to handle it. If it is something more specific to tree-decompositions, then it should belong to the files you create.

Here is how I see the situation (tell me if -- for some reason -- it does not apply):

1) You have a library that take a data X as input, and returns a data Y as output. To us that is "upstream's design decision", and we usually have no control over X nor over Y.

2) We have some Cython code that takes a graph, and converts it into format X. We call the library's functions on the data it expects, and get some data Y as a result, which we convert back into Cython/Python before handing it back to the user

3) If, because of some limitation of Cython, we cannot directly convert Python into X (or turn Y into Python) then we can have another layer in the middle, i.e. a c++ file, which is what happens with boost_interface.

This way we adapt to whatever the library expect, and there is no need to have anything sage-related in the library.

Your 'spkg-install' file copies files that you removed from your tarball (i.e. ./.libs/*)

./libs is generated by make (automake creates a .libs by default) -> ./libs should exist

Oh, I see. Usually the copying of the files produced by a 'make' is performed by 'make install'. Is there a reason why you don't use it?

G.vertices() should return a list of unsigned integers, e.g. treedecomposition_exact() does not work with TutteGraph(), since TutteGraph().vertices() returnes a list of tuples

I see. That happens very often with any kind of 'efficient' code, as handling labels really is a hassle (trust me :-/). That shouldn't be a constraint on the user, however, but on ourselves. In those cases, we usually call the library's function on a relabelled copy of the graph (so that the vertices are integers), and apply the inverse treatment on its output so that the user gets what (s)he expects (and in particular so that (s)he can call the function on any kind of graph).

Ok, i just thought something like that would be nice:

sage: T = tdlib.treedecomposition_exact(G) tree decomposition of width 4 computed sage: T Treedecomposition of width 4 on 15 vertices <--

Would it be better to use g.name("tree decompostion") for this purposes?

Definitely :-)

Thanks,

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago

comment:37

I forgot to add an example of this relabelling. What I do here may be sufficient for you, but you can look at the doc of 'relabel' (which handles more stuff)

g = graphs.KneserGraph(5,2)
V = g.vertices()
g_int = g.relabel(inplace=False) # uses the ordering of g.vertices() (see the doc)
S_int = g_int.independent_set()
S = [V[i] for i in S_int]

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

02c1abc updated spkg-install (make -> make install), removed class Treedecomposition (-> g.name())

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from e968b23 to 02c1abc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 02c1abc to f27dfd1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f27dfd1 added vertex relabeling (any vertex labeling should be supported now)

sagemath / sage

Interface with TdLib #19249