Opened 4 years ago
Closed 4 years ago
#19249 closed enhancement (fixed)
Interface with TdLib
Reported by:  llarisch  Owned by:  

Priority:  minor  Milestone:  sage6.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 )
Interface for tdlib, a library concerning treedecompositions
Containes the gluecode for
 an exact algorithms for computing a treedecomposition/the treewidth of a graph
Upstream: http://www.tdi.informatik.unifrankfurt.de/~lukas/data/tdlib0.3.1.tar.gz
Change History (80)
comment:1 Changed 4 years ago by
 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
 Branch set to u/llarisch/interface_with_tdlib
comment:3 Changed 4 years ago by
 Commit set to 6a6b47bd07da2a52d66439ba977ee31e832cf219
 Description modified (diff)
comment:4 Changed 4 years ago by
 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#thespkgtxtfile
Regards,
Nathann
comment:5 Changed 4 years ago by
 Commit changed from 6a6b47bd07da2a52d66439ba977ee31e832cf219 to 0beb7e2f63496e8a3cb3e210ed519e9445862fa5
Branch pushed to git repo; I updated commit sha1. New commits:
0beb7e2  reduced functionality

comment:6 followup: ↓ 17 Changed 4 years ago by
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 followup: ↓ 8 Changed 4 years ago by
Right, this graph clearly has width 2 O_o
comment:8 in reply to: ↑ 7 Changed 4 years ago by
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}.
comment:9 Changed 4 years ago by
 Commit changed from 0beb7e2f63496e8a3cb3e210ed519e9445862fa5 to f0bfdb9c20ce0c72b0c8143234d12c6d05cfa3bc
Branch pushed to git repo; I updated commit sha1. New commits:
f0bfdb9  small enhancements

comment:10 followup: ↓ 11 Changed 4 years ago by
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 importstatement missing? What can be the reasons (its not the content of the *.pyxfile)?
comment:11 in reply to: ↑ 10 Changed 4 years ago by
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/graphalgorithms/edgeadditionplanaritysuite
The "tdlib"part of the documentation has failed to build (UNABLE TO IMPORT MODULE): Is there some importstatement missing? What can be the reasons (its not the content of the *.pyxfile)?
Probably something like that: http://doc.sagemath.org/html/en/developer/sage_manuals.html#addinganewfile
Nathann
comment:12 Changed 4 years ago by
Or, otherwise, because you should import your module like others, as it is done in all.py?
comment:13 Changed 4 years ago by
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 followup: ↓ 15 Changed 4 years ago by
I do not know of one.
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 4 years ago by
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 spkginstall? So far:
AC_INIT(tdlib, larisch@informatik.unifrankfurt.de) AM_INIT_AUTOMAKE([subdirobjects] [foreign]) # The version of the libtool library is of the form current:revision:age # # See http://www.gnu.org/software/libtool/manual/html_node/Updatingversioninfo.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) versioninfo @LT_CURRENT@:@LT_REVISION@:@LT_AGE@
comment:16 in reply to: ↑ 15 Changed 4 years ago by
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 spkginstall? So far:
I do not understand this question.
Nathann
comment:17 in reply to: ↑ 6 Changed 4 years ago by
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
 Commit changed from f0bfdb9c20ce0c72b0c8143234d12c6d05cfa3bc to a7aa88c6dba8422d3a938b712873c43b2b9a0fff
Branch pushed to git repo; I updated commit sha1. New commits:
a7aa88c  new buildsystem

comment:19 Changed 4 years ago by
 Milestone changed from sage6.9 to sage6.10
 Status changed from new to needs_review
comment:20 Changed 4 years ago by
 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 autotoolsbased 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 spkginstall
. If upstream does not want autotools, then you should put the autotoolsbased build system in the source tarball directly (both the autotools source files and the generated files).
comment:21 Changed 4 years ago by
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
.
comment:22 Changed 4 years ago by
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#implementingfunctionsinc
comment:23 Changed 4 years ago by
Could you remove the compiled libraries from the hidden directory .lib of your archive?
comment:24 Changed 4 years ago by
 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
 Commit changed from d661cb6b80fdd38506b5e52eb0a9f638ea6937ff to 140dde4d24f9cb25d227fda56abc46f0cdb3acc0
Branch pushed to git repo; I updated commit sha1. New commits:
140dde4  reduced functionality

comment:26 Changed 4 years ago by
 Commit changed from 140dde4d24f9cb25d227fda56abc46f0cdb3acc0 to 11f4521077b4f6cd5d2c9ec1cca8e2ccc4a8dfdc
Branch pushed to git repo; I updated commit sha1. New commits:
11f4521  updated upstream contract

comment:27 followup: ↓ 28 Changed 4 years ago by
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
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
 Commit changed from 11f4521077b4f6cd5d2c9ec1cca8e2ccc4a8dfdc to 9bc9d3d4bc5f8490a19bb574a2861ccb31cfb5bd
Branch pushed to git repo; I updated commit sha1. New commits:
9bc9d3d  rm tarball

comment:30 Changed 4 years ago by
(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
 Commit changed from 9bc9d3d4bc5f8490a19bb574a2861ccb31cfb5bd to f438342a8fe42f817ef8efac79b88309e9412768
Branch pushed to git repo; I updated commit sha1. New commits:
f438342  fixed copy&paste error

comment:32 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:33 followup: ↓ 35 Changed 4 years ago by
 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 'spkginstall' 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 fromGraph
, while having a function likeget_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 worksfor 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
comment:34 Changed 4 years ago by
 Commit changed from f438342a8fe42f817ef8efac79b88309e9412768 to e968b23aa07a1d22cd9c8e05448f2eb186328df7
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

comment:35 in reply to: ↑ 33 ; followup: ↓ 36 Changed 4 years ago by
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 cythonway 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 cythoninterface 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 'spkginstall' 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 fromGraph
, while having a function likeget_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 ; followup: ↓ 40 Changed 4 years ago by
Hellooooooooooooooo,
If there would exist a cythoninterface 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 treedecompositions, 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 sagerelated in the library.
 Your 'spkginstall' 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
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
 Commit changed from e968b23aa07a1d22cd9c8e05448f2eb186328df7 to 02c1abc66cbf959086b8cb63ff642bf0fd70844f
Branch pushed to git repo; I updated commit sha1. New commits:
02c1abc  updated spkginstall (make > make install), removed class Treedecomposition (> g.name())

comment:39 Changed 4 years ago by
 Commit changed from 02c1abc66cbf959086b8cb63ff642bf0fd70844f to f27dfd1e754b1fb7c660c4a933a1770fa571b709
Branch pushed to git repo; I updated commit sha1. New commits:
f27dfd1  added vertex relabeling (any vertex labeling should be supported now)

comment:40 in reply to: ↑ 36 Changed 4 years ago by
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 sagerelated in the library.
Currently, nothing sagerelated (except for the buildsystem) is in the library.
Lukas
comment:41 followup: ↓ 42 Changed 4 years ago by
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 ; followups: ↓ 43 ↓ 44 Changed 4 years ago by
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 automakegenerated 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
Replying to llarisch:
Where is the right place for the automakegenerated 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
Helloooooo,
Where is the right place for the automakegenerated 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 automakegenerated makefiles are usually in the tarball ^^;
We don't consider those to be sagespecific. Makefiles are very common in the opensource 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 spkginstall 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
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
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
Please fill in your author name on this ticket.
comment:48 Changed 4 years ago by
 Description modified (diff)
comment:49 Changed 4 years ago by
Please remove this line from SPKG.txt
:
tarball: http://www.tdi.informatik.unifrankfurt.de/~lukas/data/tdlib0.3.1.tar.bz2
comment:50 Changed 4 years ago by
 Commit changed from f27dfd1e754b1fb7c660c4a933a1770fa571b709 to 78d4ea8090cc9feca35ad9ac34d87758942b6aa8
Branch pushed to git repo; I updated commit sha1. New commits:
78d4ea8  changes in SPKG.txt

comment:51 Changed 4 years ago by
 Commit changed from 78d4ea8090cc9feca35ad9ac34d87758942b6aa8 to 8fd0847ec7c733bb7f1f5f88e43541a74276d125
Branch pushed to git repo; I updated commit sha1. New commits:
8fd0847  new upstream buildsystem, changed spkginstall 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
comment:53 Changed 4 years ago by
Current state:
Since tdlib is a template library, an installation just copies the headers to SAGELOCAL/include/tdlib
The sagedistutils buildsystem 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 predefined by some vertex ids
Even if /base/boost_graph is updated, s.t. vertex properties are supported, some ccode layer is necessary for instanciating the library code with the needed type > in each case, a ccode layer is necessary.
Lukas
comment:54 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_info to needs_review
comment:55 Changed 4 years ago by
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
 Commit changed from 8fd0847ec7c733bb7f1f5f88e43541a74276d125 to fa2bf315807198f1c5f31f2984f9b0588fb62316
comment:57 Changed 4 years ago by
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
 Commit changed from fa2bf315807198f1c5f31f2984f9b0588fb62316 to ff1ca3ebeeeec0be3d255d5129f1cf7f114ac06c
Branch pushed to git repo; I updated commit sha1. New commits:
ff1ca3e  changes in Graph.treewidth(): optional parameter 'algorithm'

comment:59 followup: ↓ 60 Changed 4 years ago by
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
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 tdlibalgorithm 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
comment:62 Changed 4 years ago by
 Branch changed from u/llarisch/interface_with_tdlib to public/19249
 Commit changed from ff1ca3ebeeeec0be3d255d5129f1cf7f114ac06c to 6ca60dbce626f50b31b1b1b256a8d76ad93fd9cc
comment:63 Changed 4 years ago by
 Commit changed from 6ca60dbce626f50b31b1b1b256a8d76ad93fd9cc to be9dc4a8ce12e298ed5eedbbc4b16a979af928d4
comment:64 Changed 4 years ago by
 Commit changed from be9dc4a8ce12e298ed5eedbbc4b16a979af928d4 to ee2f75ab849a0fcc4156589c7d56c907af38effe
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ee2f75a  trac #19249: Review and doc cleaning

comment:65 followup: ↓ 67 Changed 4 years ago by
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
comment:66 Changed 4 years ago by
 Commit changed from ee2f75ab849a0fcc4156589c7d56c907af38effe to e4be4beca56646e3284ec1ef25dded29a92e1f48
Branch pushed to git repo; I updated commit sha1. New commits:
e4be4be  trac #19249: Broken doctests

comment:67 in reply to: ↑ 65 Changed 4 years ago by
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
That's only because I am an idiot. I meant 'positive_review'.
comment:69 Changed 4 years ago by
In build/pkgs/tdlib/type, the package type is set to optional
. Is this correct?
comment:70 Changed 4 years ago by
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
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
 Status changed from needs_review to positive_review
comment:73 Changed 4 years ago by
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
 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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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
 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
 Commit changed from e4be4beca56646e3284ec1ef25dded29a92e1f48 to 663b9a9aa6a88904499877740913031fe791432a
Branch pushed to git repo; I updated commit sha1. New commits:
663b9a9  trac #19249: Broken doctests

comment:77 Changed 4 years ago by
 Commit changed from 663b9a9aa6a88904499877740913031fe791432a to 030819926c0e666d6bef48674493a34dd6732b60
comment:78 Changed 4 years ago by
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
 Status changed from needs_review to positive_review
comment:80 Changed 4 years ago by
 Branch changed from public/19249 to 030819926c0e666d6bef48674493a34dd6732b60
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Interface with TdLib, a library concerning treedecompositions