search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.35k stars 460 forks source link

try to upgrade tdlib #30813

Closed dimpase closed 3 months ago

dimpase commented 3 years ago

tdlib appears in development, at https://github.com/freetdi/tdlib - now at version 0.9.

Not sure whether it it easy to upgrade, but one should try.

CC: @dcoudert @sagetrac-llarisch

Component: packages: optional

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

dcoudert commented 3 years ago
comment:2

It's in my todo list since several months now... but I don't know how to do that.

We should also expose other algorithms from this library (heuristics, cuset, etc.). I plan to move the treewidth method into a new tree_decomposition.pyx file and add an exact algorithm for treelength (I have one). But one step at a time.

mkoeppe commented 3 years ago
comment:3

Note that Cython code that uses tdlib should remain in its own module and not be mixed with other Cython code - this is important for the modularization effort (#29864)

dimpase commented 3 years ago
comment:4

I opened https://github.com/freetdi/tdlib/issues/34

it principle, all the C++ headers as in the current package are still there, whether they are compatible is another question. I asked the upstream to make a release.

mkoeppe commented 3 years ago
comment:5

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

fchapoton commented 3 years ago
comment:6

now on gitlab, and with a new name

https://gitlab.com/freetdi/treedec/-/releases

dimpase commented 3 years ago
comment:7

and a new release: https://gitlab.com/freetdi/treedec/-/releases

sheerluck commented 3 years ago
comment:8

Replying to @dimpase:

and a new release: https://gitlab.com/freetdi/treedec/-/releases

--- a/src/sage/graphs/graph_decompositions/sage_tdlib.cpp
+++ b/src/sage/graphs/graph_decompositions/sage_tdlib.cpp
@@ -2,8 +2,9 @@
 #include <map>

 #include <boost/graph/adjacency_list.hpp>
-#include "tdlib/TD_combinations.hpp"
-#include "tdlib/TD_misc.hpp"
+#include <treedec/combinations.hpp>
+#include <treedec/misc.hpp>
+#include <treedec/treedec.hpp>

 #ifndef TD_STRUCT_VERTEX
 #define TD_STRUCT_VERTEX
@@ -20,7 +21,6 @@ struct bag{
     std::set<unsigned int> bag;
 };

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

 void make_tdlib_graph(TD_graph_t &G, std::vector<unsigned int> &V, std::vector<unsigned int> &E){
mkoeppe commented 3 months ago
mkoeppe commented 3 months ago
felix-salfelder commented 3 months ago

There's some unfinished work on new python bindings for treedec. The goal is to replace the "tdlib" cython code by ordinary c++, with a more pythonic interface. And there is an experimental but stand-alone setup.py.

See the python_build branch in the git source repo and https://www.algok.uni-bamberg.de/freetdi.html for possible future work.

mkoeppe commented 3 months ago

@felix-salfelder Thanks for the pointer. Note we are packaging https://pypi.org/project/sagemath-tdlib/ (you may have already seen that)

antonio-rojas commented 3 months ago

Patch credit goes to Fedora, TBF.

antonio-rojas commented 3 months ago

@felix-salfelder hi, is there a reason why there is no 0.9.2 tag? Last commit being "Release 0.9.2" suggests that it's done.

felix-salfelder commented 3 months ago

On Fri, Jun 07, 2024 at 12:13:01AM -0700, Antonio Rojas wrote:

@felix-salfelder hi, is there a reason why there is no 0.9.2 tag? Last commit being "Release 0.9.2" suggests that it's done.

Not sure where it went. Perhaps I forgot to push it... I have just updated git tags and tarballs [1]. The migration from git**b remains in limbo for now.

[1] https://www.algok.uni-bamberg.de/freetdi.html