Opened 4 years ago

Closed 4 years ago

#19249 closed enhancement (fixed)

Interface with TdLib

Reported by: llarisch Owned by:
Priority: minor Milestone: sage-6.10
Component: packages: experimental Keywords:
Cc: dcoudert Merged in:
Authors: Lukas Larisch Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 0308199 (Commits) Commit: 030819926c0e666d6bef48674493a34dd6732b60
Dependencies: Stopgaps:

Description (last modified by llarisch)

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

Change History (80)

comment:1 Changed 4 years ago by llarisch

  • Component changed from PLEASE CHANGE to packages: experimental
  • Priority changed from major to minor
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 4 years ago by llarisch

  • Branch set to u/llarisch/interface_with_tdlib

comment:3 Changed 4 years ago by llarisch

  • Commit set to 6a6b47bd07da2a52d66439ba977ee31e832cf219
  • Description modified (diff)

New commits:

6a6b47bInterface with TdLib, a library concerning treedecompositions

comment:4 Changed 4 years ago by ncohen

  • Cc dcoudert added

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

comment:5 Changed 4 years ago by git

  • Commit changed from 6a6b47bd07da2a52d66439ba977ee31e832cf219 to 0beb7e2f63496e8a3cb3e210ed519e9445862fa5

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

0beb7e2reduced functionality

comment:6 follow-up: Changed 4 years ago by llarisch

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).

comment:7 follow-up: Changed 4 years ago by ncohen

Right, this graph clearly has width 2 O_o

comment:8 in reply to: ↑ 7 Changed 4 years ago by llarisch

Replying to ncohen:

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}.

Last edited 4 years ago by llarisch (previous) (diff)

comment:9 Changed 4 years ago by git

  • Commit changed from 0beb7e2f63496e8a3cb3e210ed519e9445862fa5 to f0bfdb9c20ce0c72b0c8143234d12c6d05cfa3bc

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

f0bfdb9small enhancements

comment:10 follow-up: Changed 4 years ago by llarisch

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)?

comment:11 in reply to: ↑ 10 Changed 4 years ago by ncohen

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

comment:12 Changed 4 years ago by ncohen

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

comment:13 Changed 4 years ago by llarisch

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?

comment:14 follow-up: Changed 4 years ago by ncohen

I do not know of one.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by llarisch

Replying to ncohen:

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@

comment:16 in reply to: ↑ 15 Changed 4 years ago by ncohen

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

comment:17 in reply to: ↑ 6 Changed 4 years ago by ncohen

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

comment:18 Changed 4 years ago by git

  • Commit changed from f0bfdb9c20ce0c72b0c8143234d12c6d05cfa3bc to a7aa88c6dba8422d3a938b712873c43b2b9a0fff

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

a7aa88cnew build-system

comment:19 Changed 4 years ago by llarisch

  • Milestone changed from sage-6.9 to sage-6.10
  • Status changed from new to needs_review

comment:20 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

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).

comment:21 Changed 4 years ago by jdemeyer

Two more details:

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

comment:22 Changed 4 years ago by jdemeyer

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

comment:23 Changed 4 years ago by ncohen

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

comment:24 Changed 4 years ago by git

  • Commit changed from a7aa88c6dba8422d3a938b712873c43b2b9a0fff to d661cb6b80fdd38506b5e52eb0a9f638ea6937ff

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

d661cb6- removed entry in the doc

comment:25 Changed 4 years ago by git

  • Commit changed from d661cb6b80fdd38506b5e52eb0a9f638ea6937ff to 140dde4d24f9cb25d227fda56abc46f0cdb3acc0

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

140dde4reduced functionality

comment:26 Changed 4 years ago by git

  • Commit changed from 140dde4d24f9cb25d227fda56abc46f0cdb3acc0 to 11f4521077b4f6cd5d2c9ec1cca8e2ccc4a8dfdc

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

11f4521updated upstream contract

comment:27 follow-up: Changed 4 years ago by llarisch

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

comment:28 in reply to: ↑ 27 Changed 4 years ago by ncohen

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

comment:29 Changed 4 years ago by git

  • Commit changed from 11f4521077b4f6cd5d2c9ec1cca8e2ccc4a8dfdc to 9bc9d3d4bc5f8490a19bb574a2861ccb31cfb5bd

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

9bc9d3drm tarball

comment:30 Changed 4 years ago by ncohen

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

Nathann

comment:31 Changed 4 years ago by git

  • Commit changed from 9bc9d3d4bc5f8490a19bb574a2861ccb31cfb5bd to f438342a8fe42f817ef8efac79b88309e9412768

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

f438342fixed copy&paste error

comment:32 Changed 4 years ago by llarisch

  • Status changed from needs_work to needs_review

comment:33 follow-up: Changed 4 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to needs_info

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/

Last edited 4 years ago by ncohen (previous) (diff)

comment:34 Changed 4 years ago by git

  • Commit changed from f438342a8fe42f817ef8efac79b88309e9412768 to e968b23aa07a1d22cd9c8e05448f2eb186328df7

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

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

comment:35 in reply to: ↑ 33 ; follow-up: Changed 4 years ago by llarisch

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, sage_tdlib_*).

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

comment:36 in reply to: ↑ 35 ; follow-up: Changed 4 years ago by ncohen

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

comment:37 Changed 4 years ago by ncohen

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]

comment:38 Changed 4 years ago by git

  • Commit changed from e968b23aa07a1d22cd9c8e05448f2eb186328df7 to 02c1abc66cbf959086b8cb63ff642bf0fd70844f

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

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

comment:39 Changed 4 years ago by git

  • Commit changed from 02c1abc66cbf959086b8cb63ff642bf0fd70844f to f27dfd1e754b1fb7c660c4a933a1770fa571b709

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

f27dfd1added vertex relabeling (any vertex labeling should be supported now)

comment:40 in reply to: ↑ 36 Changed 4 years ago by llarisch

Hello,

Replying to ncohen:

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.

In my opinion, this is the case and for that reason sage_tdlib.cpp exists. In addition, i cannot use boost_interface, since vertex properties are not covered there. As mentioned above, i need a

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

where X is some struct. Concrete (see sage_tdlib.cpp):

For the input graph

struct Vertex{
    ...
    ...
    unsigned int id;
    ...
};

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, Vertex> TD_graph_t;

And for the output treedecomposition:

struct bag{
    ...
    ...
    std::set<unsigned int> bag;
    ...
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, bag> TD_tree_dec_t;

The reason for sage_tdlib.cpp is to do the conversion

sage graph -> V,E as vectors -> boost graph

and

boost graph (tree decomposition) -> V, E, bags as vectors -> sage graph.

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

Currently, nothing sage-related (except for the build-system) is in the library.

Lukas

comment:41 follow-up: Changed 4 years ago by ncohen

Helloooooooo Lucas !

I see I see, thank you for the details. Why then do you need to copy sage_tdlib.cpp *inside* of your archive before compiling it? This is the thing that bothers me.

Nathann

comment:42 in reply to: ↑ 41 ; follow-ups: Changed 4 years ago by llarisch

Hello,

I see I see, thank you for the details. Why then do you need to copy sage_tdlib.cpp *inside* of your archive before compiling it? This is the thing that bothers me.

I meant no harm by it =), i will fix that.

Where is the right place for the automake-generated makefiles and related stuff? Currently, this files are located in the tarball, but that is misguided since they refer to sage_tdlib.*. Maybe in some directory in spkg/tdlib along with sage_tdlib?

comment:43 in reply to: ↑ 42 Changed 4 years ago by jdemeyer

Replying to llarisch:

Where is the right place for the automake-generated makefiles and related stuff?

In the official upstream tarball.

Currently, this files are located in the tarball, but that is misguided since they refer to sage_tdlib.*.

I think Nathann has been trying to tell you that the sage_tdlib files should not be in the upstream tarball, but in Sage itself. So then there is no problem.

comment:44 in reply to: ↑ 42 Changed 4 years ago by ncohen

Helloooooo,

Where is the right place for the automake-generated makefiles and related stuff? Currently, this files are located in the tarball, but that is misguided since they refer to sage_tdlib.*. Maybe in some directory in spkg/tdlib along with sage_tdlib?

Well, the automake-generated makefiles are usually in the tarball ^^;

We don't consider those to be sage-specific. Makefiles are very common in the open-source world, as those things make sure that the code compiles on any platform. So usually, the tarballs we get come with those things in it, and spkg-install is some variation of 'configure && make && make install'.

Somehow, your none of the files contained in your tarball (including the makefiles) should mention this sage_tdlib file.

Nathann

comment:45 Changed 4 years ago by llarisch

The thing is that the library itself only consist of template functions, such that a makefile does not make sense, since external use of some library functions is supposed to generate the needed functions -> building a shared library out of the original tarball would not generate the necessary code. The code for the exact algorithm is generated by the call

treedec::exact_decomposition_cutset(G, T, lb);

with

typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Vertex> TD_graph_t;

TD_graph_t G;

in sage_tdlib.cpp.

comment:46 Changed 4 years ago by ncohen

HMmmmm.... O_o

Well, then I guess all you need is to copy all you hpp files to SAGE_INCLUDE/tdlib/, and that's it?...

Nathann

comment:47 Changed 4 years ago by jdemeyer

Please fill in your author name on this ticket.

comment:48 Changed 4 years ago by jdemeyer

  • Description modified (diff)

comment:49 Changed 4 years ago by jdemeyer

Please remove this line from SPKG.txt:

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

comment:50 Changed 4 years ago by git

  • Commit changed from f27dfd1e754b1fb7c660c4a933a1770fa571b709 to 78d4ea8090cc9feca35ad9ac34d87758942b6aa8

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

78d4ea8changes in SPKG.txt

comment:51 Changed 4 years ago by git

  • Commit changed from 78d4ea8090cc9feca35ad9ac34d87758942b6aa8 to 8fd0847ec7c733bb7f1f5f88e43541a74276d125

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

8fd0847new upstream build-system, changed spkg-install concerning this matter (./sage -i tdlib will copy the needful to SAGELOCAL/include/tdlib), glue code will made by distutils, added a call, that makes a tree decomposition small

comment:52 Changed 4 years ago by llarisch

  • Authors set to llarisch

comment:53 Changed 4 years ago by llarisch

Current state:

-Since tdlib is a template library, an installation just copies the headers to SAGELOCAL/include/tdlib

-The sage-distutils build-system will build a shared library out of sage_tdlib.cpp and the headers in /include/tdlib

-sage_tdlib.cpp is necessary until /base/boost_graph supportes vertex properties (especially std::set). currently, edge properties are supported and vertex properties are pre-defined by some vertex ids

-Even if /base/boost_graph is updated, s.t. vertex properties are supported, some c-code layer is necessary for instanciating the library code with the needed type -> in each case, a c-code layer is necessary.

Lukas

comment:54 Changed 4 years ago by llarisch

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:55 Changed 4 years ago by ncohen

Helloooooooo Lukas,

I read and changed a couple of things in your code (mostly cleaning). I am trying to find a way to avoid this .cpp file. I added my two commits at u/ncohen/19249, which you can add atop of this branch if you agree with them.

Thanks,

Nathann

comment:56 Changed 4 years ago by git

  • Commit changed from 8fd0847ec7c733bb7f1f5f88e43541a74276d125 to fa2bf315807198f1c5f31f2984f9b0588fb62316

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

648f0a8trac #19249: Merged with 6.10.beta3
0f1d488trac #19249: Documentation cleaning
fa2bf31trac #19249: remove functions not called anywhere

comment:57 Changed 4 years ago by ncohen

Hellooooooooooo Lukas !

Okay, I give up :-)

I tried to shortcut your .cpp file but I wasn't able to, and even though I may have gotten 'close' my solutions were very awkward and would probably be a shot in our feet if we ever need something more generic. Let it stay as it is.

What would you think of modifying Graph.treewidth right now in order to make it call your library when it is installed?

The way we do it is (see Graph.automorphism_group) to have an 'algorithm' selector set to None by default (which means 'use the best routine available'), which can also be defined manually if one wants to call Sage's algorithm or yours, explicitly.

This also lets us write doctests to check that both algorithms return the same value.

Either way this ticket will soon be merged in Sage. Thanks,

Nathann

comment:58 Changed 4 years ago by git

  • Commit changed from fa2bf315807198f1c5f31f2984f9b0588fb62316 to ff1ca3ebeeeec0be3d255d5129f1cf7f114ac06c

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

ff1ca3echanges in Graph.treewidth(): optional parameter 'algorithm'

comment:59 follow-up: Changed 4 years ago by ncohen

Hellooooooooo,

There were a couple of problems with error management and documentation. I pused a commit at public/19249. If you agree with it, then I guess this can go.

Nathann

comment:60 in reply to: ↑ 59 Changed 4 years ago by llarisch

Replying to ncohen:

Hellooooooooo,

There were a couple of problems with error management and documentation. I pused a commit at public/19249. If you agree with it, then I guess this can go.

Nathann

I agree =)

Currently, the tdlib-algorithm computes the treewidth in each case and k is a lower bound on the resulting width. I will add some code to support the version 'treewidth < k?' soon.

Thanks for your review!

Lukas

comment:61 Changed 4 years ago by ncohen

  • Authors changed from llarisch to Lukas Larisch

comment:62 Changed 4 years ago by ncohen

  • Branch changed from u/llarisch/interface_with_tdlib to public/19249
  • Commit changed from ff1ca3ebeeeec0be3d255d5129f1cf7f114ac06c to 6ca60dbce626f50b31b1b1b256a8d76ad93fd9cc

New commits:

ef54a76trac #19591: Zoom+move a Graph d3js representation
5878c9btrac #19249: Merged with representation
6ca60dbtrac #19249: Review and doc cleaning

comment:63 Changed 4 years ago by git

  • Commit changed from 6ca60dbce626f50b31b1b1b256a8d76ad93fd9cc to be9dc4a8ce12e298ed5eedbbc4b16a979af928d4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

58dc598trac #19249: Merged with beta4
be9dc4atrac #19249: Review and doc cleaning

comment:64 Changed 4 years ago by git

  • Commit changed from be9dc4a8ce12e298ed5eedbbc4b16a979af928d4 to ee2f75ab849a0fcc4156589c7d56c907af38effe

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ee2f75atrac #19249: Review and doc cleaning

comment:65 follow-up: Changed 4 years ago by ncohen

Err.. Sorry with the mess with the git branch. It should now be in a correct state, with just a merging operation atop of your branch and a commit meant to clean the doc/code.

If you still have no problem with it, please change the ticket's status to needs_review on my behalf.

Thanks,

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:66 Changed 4 years ago by git

  • Commit changed from ee2f75ab849a0fcc4156589c7d56c907af38effe to e4be4beca56646e3284ec1ef25dded29a92e1f48

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

e4be4betrac #19249: Broken doctests

comment:67 in reply to: ↑ 65 Changed 4 years ago by llarisch

Replying to ncohen:

Err.. Sorry with the mess with the git branch. It should now be in a correct state, with just a merging operation atop of your branch and a commit meant to clean the doc/code.

If you still have no problem with it, please change the ticket's status to needs_review on my behalf.

Thanks,

Nathann

The current state is already needs_review ?!

comment:68 Changed 4 years ago by ncohen

That's only because I am an idiot. I meant 'positive_review'.

Last edited 4 years ago by ncohen (previous) (diff)

comment:69 Changed 4 years ago by llarisch

In build/pkgs/tdlib/type, the package type is set to optional. Is this correct?

comment:70 Changed 4 years ago by llarisch

There are still some problems with the trivial cases in the sage algorithm for treewidth:

sage: G = Graph()
sage: G.treewidth() #should be -1
0
sage: G.add_vertex(1)
sage: G.treewidth() #should be 0
1

comment:71 Changed 4 years ago by ncohen

I think I fixed the second case in the commit I added here. The empty graph may also return 1, however. It has to be fixed but not necessarily in this ticket, so we can merge it anyway and fix that elsewhere.

Nathann

comment:72 Changed 4 years ago by llarisch

  • Status changed from needs_review to positive_review

comment:73 Changed 4 years ago by jdemeyer

I think you should have removed the whitespace changes to module_list.py (see 21) but I guess it's too late now.

comment:74 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long src/sage/graphs/graph.py
**********************************************************************
File "src/sage/graphs/graph.py", line 2345, in sage.graphs.graph.Graph.treewidth
Failed example:
    Graph(1).treewidth()
Expected:
    0
Got:
    1
**********************************************************************
File "src/sage/graphs/graph.py", line 2355, in sage.graphs.graph.Graph.treewidth
Failed example:
    graphs.PetersenGraph().treewidth(k=3,certificate=True)
Expected:
    Tree decomposition: Graph on 6 vertices
Got:
    False
**********************************************************************
1 item had failures:
   2 of  30 in sage.graphs.graph.Graph.treewidth
    [717 tests, 2 failures, 16.17 s]
sage -t --long src/sage/graphs/graph_decompositions/tdlib.pyx
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 126, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    import sage.graphs.graph_decompositions.tdlib as tdlib
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[0]>", line 1, in <module>
        import sage.graphs.graph_decompositions.tdlib as tdlib
    ImportError: No module named tdlib
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 128, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    T = tdlib.treedecomposition_exact(G)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[2]>", line 1, in <module>
        T = tdlib.treedecomposition_exact(G)
    NameError: name 'tdlib' is not defined
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 129, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    T.show(vertex_size=2000)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[3]>", line 1, in <module>
        T.show(vertex_size=Integer(2000))
    NameError: name 'T' is not defined
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 133, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    import sage.graphs.graph_decompositions.tdlib as tdlib
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[4]>", line 1, in <module>
        import sage.graphs.graph_decompositions.tdlib as tdlib
    ImportError: No module named tdlib
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 135, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    T = tdlib.treedecomposition_exact(G)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[6]>", line 1, in <module>
        T = tdlib.treedecomposition_exact(G)
    NameError: name 'tdlib' is not defined
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 137, in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
Failed example:
    T = tdlib.treedecomposition_exact(G)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.treedecomposition_exact[8]>", line 1, in <module>
        T = tdlib.treedecomposition_exact(G)
    NameError: name 'tdlib' is not defined
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 173, in sage.graphs.graph_decompositions.tdlib.get_width
Failed example:
    import sage.graphs.graph_decompositions.tdlib as tdlib
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.get_width[0]>", line 1, in <module>
        import sage.graphs.graph_decompositions.tdlib as tdlib
    ImportError: No module named tdlib
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 175, in sage.graphs.graph_decompositions.tdlib.get_width
Failed example:
    T = tdlib.treedecomposition_exact(G)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.get_width[2]>", line 1, in <module>
        T = tdlib.treedecomposition_exact(G)
    NameError: name 'tdlib' is not defined
**********************************************************************
File "src/sage/graphs/graph_decompositions/tdlib.pyx", line 176, in sage.graphs.graph_decompositions.tdlib.get_width
Failed example:
    tdlib.get_width(T)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/highperf/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_decompositions.tdlib.get_width[3]>", line 1, in <module>
        tdlib.get_width(T)
    NameError: name 'tdlib' is not defined
**********************************************************************
2 items had failures:
   3 of   5 in sage.graphs.graph_decompositions.tdlib.get_width
   6 of  10 in sage.graphs.graph_decompositions.tdlib.treedecomposition_exact
    [13 tests, 9 failures, 0.01 s]

comment:75 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

Sorry, I was careless. 'optional' flags were missing in the second file, and the behaviour was sometimes wrong in the first one.

Lukas, as previously could you double check my last commit and change this ticket's status if you agree with it?

Nathann

comment:76 Changed 4 years ago by git

  • Commit changed from e4be4beca56646e3284ec1ef25dded29a92e1f48 to 663b9a9aa6a88904499877740913031fe791432a

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

663b9a9trac #19249: Broken doctests

comment:77 Changed 4 years ago by git

  • Commit changed from 663b9a9aa6a88904499877740913031fe791432a to 030819926c0e666d6bef48674493a34dd6732b60

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a6bbdcfInterface with TdLib, a library concerning treedecompositions
0308199trac #19249: Broken doctests

comment:78 Changed 4 years ago by jdemeyer

I rebased and squashed the commits which were previously positively reviewed, removing the whitespace changes in src/module_list.py. Nathann's commit still needs review.

comment:79 Changed 4 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:80 Changed 4 years ago by vbraun

  • Branch changed from public/19249 to 030819926c0e666d6bef48674493a34dd6732b60
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.