Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Interface with TdLib #19249

Closed
sagetrac-llarisch mannequin opened this issue Sep 19, 2015 · 100 comments
Closed

Interface with TdLib #19249

sagetrac-llarisch mannequin opened this issue Sep 19, 2015 · 100 comments

Comments

@sagetrac-llarisch
Copy link
Mannequin

sagetrac-llarisch mannequin commented Sep 19, 2015

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

@sagetrac-llarisch sagetrac-llarisch mannequin added this to the sage-6.9 milestone Sep 19, 2015
@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Sep 19, 2015

Branch: u/llarisch/interface_with_tdlib

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Sep 19, 2015

New commits:

6a6b47bInterface with TdLib, a library concerning treedecompositions

@sagetrac-llarisch

This comment has been minimized.

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Sep 19, 2015

Commit: 6a6b47b

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Sep 20, 2015

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 24, 2015

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

0beb7e2reduced functionality

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 24, 2015

Changed commit from 6a6b47b to 0beb7e2

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Oct 3, 2015

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 3, 2015

comment:7

Right, this graph clearly has width 2 O_o

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Oct 3, 2015

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 4, 2015

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

f0bfdb9small enhancements

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 4, 2015

Changed commit from 0beb7e2 to f0bfdb9

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Oct 4, 2015

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 4, 2015

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 4, 2015

comment:12

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

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Oct 4, 2015

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?

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 4, 2015

comment:14

I do not know of one.

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Oct 4, 2015

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@

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 4, 2015

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 5, 2015

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2015

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

a7aa88cnew build-system

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 29, 2015

Changed commit from f0bfdb9 to a7aa88c

@sagetrac-llarisch sagetrac-llarisch mannequin removed this from the sage-6.9 milestone Oct 29, 2015
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 17, 2015

Changed commit from 6ca60db to be9dc4a

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 17, 2015

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

ee2f75atrac #19249: Review and doc cleaning

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 17, 2015

Changed commit from be9dc4a to ee2f75a

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 17, 2015

comment:65

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 17, 2015

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

e4be4betrac #19249: Broken doctests

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 17, 2015

Changed commit from ee2f75a to e4be4be

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Nov 17, 2015

comment:67

Replying to @nathanncohen:

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 18, 2015

comment:68

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

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Nov 18, 2015

comment:69

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

@sagetrac-llarisch
Copy link
Mannequin Author

sagetrac-llarisch mannequin commented Nov 18, 2015

comment:70

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

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 18, 2015

comment:71

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

@jdemeyer
Copy link

comment:73

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

@vbraun
Copy link
Member

vbraun commented Nov 19, 2015

comment:74
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]

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 19, 2015

comment:75

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 19, 2015

Changed commit from e4be4be to 663b9a9

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 19, 2015

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

663b9a9trac #19249: Broken doctests

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 19, 2015

Changed commit from 663b9a9 to 0308199

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Nov 19, 2015

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

@jdemeyer
Copy link

comment:78

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.

@vbraun
Copy link
Member

vbraun commented Nov 21, 2015

Changed branch from public/19249 to 0308199

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants