#17950 closed enhancement (fixed)
make modular_decomposition an optional spkg
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  graph theory  Keywords:  
Cc:  dcoudert, jdemeyer  Merged in:  
Authors:  Nathann Cohen  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  e72ab22 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
The code on which Sage relies to compute modular decompositions has been displaying a stopgap for a while. It seems that the problem has been fixed with an update, but it seems to be architecturedependent (see #13744).
This branch puts some distance between Sage and this code: its source code had been copy/pasted into Sage's source code (I did that), and this is far from being clean. Thus, we turn this into an optional spkg.
An interesting consequence of this move is that we will (at least) be able to use the updated version of the code on platforms for which it work. It will also make it easier to install and test on other architectures. It also means that we stop shipping in our own source code a program which has proved to be unreliable at times.
Nathann
the package: http://www.steinertriples.fr/ncohen/modular_decomposition20100607.tar.bz2
Change History (36)
comment:1 Changed 6 years ago by
 Branch set to public/17950
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 5f1e7a6f8a3edf93d1c6835d30dc46cce33dd487
comment:3 Changed 6 years ago by
 Commit changed from 5f1e7a6f8a3edf93d1c6835d30dc46cce33dd487 to bedbab187f3399e4231650c2d0947d8513c290b0
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
bedbab1  trac #17950: make modular_decomposition an optional spkg

comment:4 followup: ↓ 5 Changed 6 years ago by
 Status changed from needs_review to needs_info
What should I do to compile it?
confetti:sage dcoudert$ git trac checkout 17950 Loading ticket #17950... Checking out Trac #17950 remote branch public/17950 > local branch t/17950/public/17950... confetti:sage dcoudert$ ./sage b scons: `install' is up to date. Updating Cython code.... Enabling Cython debugging support Compiling sage/graphs/modular_decomposition.pyx because it changed. Cythonizing sage/graphs/modular_decomposition.pyx Finished Cythonizing, time: 4.56 seconds. Discovering Python source code.... Discovered Python source, time: 0.03 seconds. Cleaning up stale installed files....  cleaning /Users/dcoudert/sage/local/lib/python2.7/sitepackages Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/modular_decomposition/__init__.pyc Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/modular_decomposition/__init__.py Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/modular_decomposition/modular_decomposition.so  cleaning /Users/dcoudert/sage/local/lib/sitepython  cleaning /Users/dcoudert/sage/src/build/lib.macosx10.9x86_642.7 Cleaning up stale file: /Users/dcoudert/sage/src/build/lib.macosx10.9x86_642.7/sage/graphs/modular_decomposition/__init__.py Cleaning up stale file: /Users/dcoudert/sage/src/build/lib.macosx10.9x86_642.7/sage/graphs/modular_decomposition/modular_decomposition.so Finished cleaning, time: 0.11 seconds. running install running build running build_py copying sage/graphs/all.py > build/lib.macosx10.9x86_642.7/sage/graphs copying sage/graphs/graph.py > build/lib.macosx10.9x86_642.7/sage/graphs running build_ext building 'sage.graphs.modular_decomposition' extension Executing 1 command (using 1 thread) gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall I/Users/dcoudert/sage/local/include I/Users/dcoudert/sage/src I/Users/dcoudert/sage/src/c_lib/include I/Users/dcoudert/sage/src/sage/ext I/Users/dcoudert/sage/local/include/python2.7 c build/cythonized/sage/graphs/modular_decomposition.c o build/temp.macosx10.9x86_642.7/build/cythonized/sage/graphs/modular_decomposition.o fnostrictaliasing w build/cythonized/sage/graphs/modular_decomposition.c:289:35: fatal error: modular_decomposition.h: No such file or directory #include "modular_decomposition.h" ^ compilation terminated. error: command 'gcc' failed with exit status 1
comment:5 in reply to: ↑ 4 Changed 6 years ago by
 Status changed from needs_info to needs_review
What should I do to compile it?
My mistake. There is something I forgot to do, and unless I do it one cannot compile Sage without installing the new package. I just added a commit.
With this commit, should compile correctly. You will *not* be able to call .modular_decomposition
as it should ask you to install a package first.
In order to install the package, copy the .tar.bz2 file (whose link appears in this ticket's description) into your upstream/ folder. Then, you will be able to run sage i modular_decomposition
and everything should be alright.
Nathann
comment:6 Changed 6 years ago by
 Commit changed from bedbab187f3399e4231650c2d0947d8513c290b0 to 054df904098a3013b6b91fd3662cd00680a24511
Branch pushed to git repo; I updated commit sha1. New commits:
054df90  trac #17950: tell modules_list.py that modular_decomposition is optional

comment:7 Changed 6 years ago by
That's apparently not enough.
Oops, Sage crashed. We do our best to make it stable, but...
and at the end of the Sage_crash_report.txt
we have:
/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/all.py in <module>() 5 lazy_import("sage.graphs.hypergraph_generators", "hypergraphs") 6 from graph_database import GraphDatabase, GenericGraphQuery, GraphQuery 7 from graph import Graph 8 from digraph import DiGraph 9 from bipartite_graph import BipartiteGraph 10 from graph_bundle import GraphBundle 11 import weakly_chordal 12 import graph_list as graphs_list 13 import sage.graphs.generic_graph_pyx 14 import sage.graphs.generic_graph 15 import sage.graphs.graph_decompositions 16 import sage.graphs.graph 17 import sage.graphs.digraph 18 lazy_import("sage.graphs", "graph_coloring") 19 import sage.graphs.graph_decompositions > 20 import sage.graphs.modular_decomposition global sage.graphs.modular_decomposition = undefined 21 import sage.graphs.comparability 22 from sage.graphs.cliquer import * 23 from graph_database import graph_db_info 24 lazy_import("sage.graphs.graph_editor", "graph_editor") 25 26 import sage.graphs.isgci 27 from sage.graphs.isgci import graph_classes 28 import sage.graphs.distances_all_pairs 29 import sage.graphs.trees 30 import sage.graphs.graph_latex ImportError: No module named modular_decomposition *************************************************************************** History of session input: *** Last line of input (may not be in above history):
comment:8 Changed 6 years ago by
 Commit changed from 054df904098a3013b6b91fd3662cd00680a24511 to 894556fe81b9031df978490c0faac643fad8991e
Branch pushed to git repo; I updated commit sha1. New commits:
894556f  trac #17950: Removing an import

comment:9 Changed 6 years ago by
True. This bug does not happen on my computer as modular_decomposition
is installed. I just fixed it.
Nathann
comment:10 Changed 6 years ago by
I can now start sage. We are making progress ;)
But, before trying to install the package, I did:
./sage t src/sage/graphs/graph.py ********************************************************************** File "src/sage/graphs/graph.py", line 6505, in sage.graphs.graph.Graph.is_prime Failed example: graphs.PetersenGraph().is_prime() Exception raised: Traceback (most recent call last): File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 492, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 854, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.graph.Graph.is_prime[0]>", line 1, in <module> graphs.PetersenGraph().is_prime() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6516, in is_prime D = self.modular_decomposition() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6480, in modular_decomposition raise RuntimeError("In order to use this method you must " RuntimeError: In order to use this method you must install the modular_decomposition package ********************************************************************** File "src/sage/graphs/graph.py", line 6507, in sage.graphs.graph.Graph.is_prime Failed example: graphs.BullGraph().is_prime() Exception raised: Traceback (most recent call last): File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 492, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 854, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.graph.Graph.is_prime[1]>", line 1, in <module> graphs.BullGraph().is_prime() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6516, in is_prime D = self.modular_decomposition() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6480, in modular_decomposition raise RuntimeError("In order to use this method you must " RuntimeError: In order to use this method you must install the modular_decomposition package ********************************************************************** File "src/sage/graphs/graph.py", line 6512, in sage.graphs.graph.Graph.is_prime Failed example: (graphs.PetersenGraph() + graphs.BullGraph()).is_prime() Exception raised: Traceback (most recent call last): File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 492, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 854, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.graph.Graph.is_prime[2]>", line 1, in <module> (graphs.PetersenGraph() + graphs.BullGraph()).is_prime() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6516, in is_prime D = self.modular_decomposition() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py", line 6480, in modular_decomposition raise RuntimeError("In order to use this method you must " RuntimeError: In order to use this method you must install the modular_decomposition package ********************************************************************** 1 item had failures: 3 of 4 in sage.graphs.graph.Graph.is_prime [657 tests, 3 failures, 13.19 s]  sage t src/sage/graphs/graph.py # 3 doctests failed  Total time for all tests: 13.5 seconds cpu time: 9.7 seconds cumulative wall time: 13.2 seconds
comment:11 Changed 6 years ago by
 Commit changed from 894556fe81b9031df978490c0faac643fad8991e to b2e940fcb80d9b1daa3a09d642347617b4c13277
Branch pushed to git repo; I updated commit sha1. New commits:
b2e940f  trac #17950: Broken doctests

comment:12 Changed 6 years ago by
 Commit changed from b2e940fcb80d9b1daa3a09d642347617b4c13277 to c19a921b7385396cd42a12774618418373887b82
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c19a921  trac #17950: Broken doctests

comment:13 followup: ↓ 14 Changed 6 years ago by
As I told you, we are making progress! I can now compile, start sage, pass all tests, etc. without installing the spkg.
In the online doc of the modular_decomposition
method. After Note: In order to use this method you must install the "modular_decomposition" optional package.
you could add a see blah blah blah
.
I'm now trying to install the spkg. I'm able to compile but:
sage: G = graphs.PetersenGraph() sage: G.modular_decomposition() /Users/dcoudert/sage/src/bin/sageipython:1: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ******************************************************************************** ('Prime', [2, 6, 3, 9, 7, 8, 0, 1, 5, 4]) sage: G.is_prime() True sage: G.modular_decomposition()  Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). Sage will now terminate.  ./sage: line 134: 17334 Segmentation fault: 11 "$SAGE_ROOT/src/bin/sage" "$@"
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Hello,
In the online doc of the
modular_decomposition
method. AfterNote: In order to use this method you must install the "modular_decomposition" optional package.
you could add asee blah blah blah
.
Done.
I'm now trying to install the spkg. I'm able to compile but:
I cannot reproduce this bug with your commands. Is it deterministic on your computer ?
This may be related to the reports from #13744. The original code itself seems to have problems, and my repeated reports changed nothing. This is part of the reason why I am trying to move this code away from Sage. Are you using a Mac computer ?
Nathann
comment:15 Changed 6 years ago by
 Commit changed from c19a921b7385396cd42a12774618418373887b82 to 0ecbf7ce7bd69bf23c215bb2c03852a29637cfcb
Branch pushed to git repo; I updated commit sha1. New commits:
0ecbf7c  trac #17950: add a link toward sage.misc.packages.

comment:16 Changed 6 years ago by
Yes I'm using a mac.
I can reproduce the bug, but it's kind of random. Sometimes its working, sometimes not.
confetti:sage dcoudert$ ./sage ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 6.6.beta5, Release Date: 20150313 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: G = graphs.PetersenGraph() sage: G.modular_decomposition() /Users/dcoudert/sage/src/bin/sageipython:1: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ********************************************************************************  Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). Sage will now terminate.  ./sage: line 134: 17513 Segmentation fault: 11 "$SAGE_ROOT/src/bin/sage" "$@" confetti:sage dcoudert$ ./sage ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 6.6.beta5, Release Date: 20150313 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: G = graphs.PetersenGraph() sage: G.is_prime() /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:6524: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ******************************************************************************** True sage: G.modular_decomposition() ('Prime', [('Prime', [2, 6, 3, 9]), 7, 8, 0, 1, 5, 4]) sage: G = graphs.PetersenGraph() sage: G.modular_decomposition() ('Prime', [2, 6, 3, 9, 7, 8, 0, 1, 5, 4]) sage: G.is_prime() False sage: G.modular_decomposition() ('Prime', [('Parallel', [2, 6]), 3, 9, 7, 8, 0, 1, 5, 4]) sage: Exiting Sage (CPU time 0m0.08s, Wall time 0m23.56s). confetti:sage dcoudert$ ./sage ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 6.6.beta5, Release Date: 20150313 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: G = graphs.PetersenGraph() sage: G.modular_decomposition() /Users/dcoudert/sage/src/bin/sageipython:1: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ********************************************************************************  Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). Sage will now terminate.  ./sage: line 134: 17606 Segmentation fault: 11 "$SAGE_ROOT/src/bin/sage" "$@" ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 6.6.beta5, Release Date: 20150313 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: G = graphs.PetersenGraph() sage: G.is_prime() /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:6524: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ******************************************************************************** True sage: for i in range(1000): ....: G = graphs.RandomBarabasiAlbert(1000,2) ....: _ = G.modular_decomposition() ....:  Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). Sage will now terminate.  ./sage: line 134: 17655 Segmentation fault: 11 "$SAGE_ROOT/src/bin/sage" "$@" ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 6.6.beta5, Release Date: 20150313 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: G = graphs.PetersenGraph() sage: G.is_prime() /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:6524: ******************************************************************************** Graph.modular_decomposition is known to return wrong results This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744. ********************************************************************************  Unhandled SIGSEGV: A segmentation fault occurred in Sage. This probably occurred because a *compiled* component of Sage has a bug in it and is not properly wrapped with sig_on(), sig_off(). Sage will now terminate.  ./sage: line 134: 17703 Segmentation fault: 11 "$SAGE_ROOT/src/bin/sage" "$@"
comment:17 Changed 6 years ago by
Well.. On my computer your loop with 1000 random graphs ends without any problem.
comment:18 Changed 6 years ago by
With the loop, some times it crashes after 3 graphs, 600, or never. This is really random segfault.
comment:19 Changed 6 years ago by
Also, have you seen that I don't always have the same answer on the Petersen?
comment:20 Changed 6 years ago by
It is very likely that this segfault comes from the code itself. Do you think that this should stop us from turning it into a module ?
What we currently ship in Sage returns wrong results, and this new version of the code fixes it. Though we have segfaults. Could you try to run this code with the old version of Sage, see if it works ?
I could build a package with the old version of the code, if it does not segfault. It would still return wrong results, though.
Also, have you seen that I don't always have the same answer on the Petersen?
Yesyes. I cannot reproduce that on my computer either, but it was apparently reported in #13744.
Nathann
comment:21 Changed 6 years ago by
I don't have problems with the previous version (branch develop): no segfault with the long loop. I don't know what is the best to do. D.
comment:22 Changed 6 years ago by
 Commit changed from 0ecbf7ce7bd69bf23c215bb2c03852a29637cfcb to e72ab22fddbe84da5018eaf39f546a80d2133b2a
Branch pushed to git repo; I updated commit sha1. New commits:
e72ab22  trac #17950: Use the old C code instead

comment:23 Changed 6 years ago by
 Description modified (diff)
I changed the branch and the package's name (please remove the previous one from your copy of Sage). It ships the .c files that are currently contained in Sage (and return wrong results too). You should not experience anything that does not already happen, however.
Nathann
comment:24 followup: ↓ 25 Changed 6 years ago by
Well, now I have directly a segfault :(
What's the difference between the two versions ?
comment:25 in reply to: ↑ 24 Changed 6 years ago by
What's the difference between the two versions ?
I had one at some point. Now that you have installed the package I just built, could you 'touch' modular_decomposition.pyx
and run sage b
?
Nathann
comment:26 Changed 6 years ago by
It's apparently working: no segfault with the big for loop.
Should we consider it is better like that?
David.
comment:27 Changed 6 years ago by
Well technically it is better, as the code is a bit further from Sage's source code, as it should have been from the beginning. Plus it is optional. Plus those .c files have never been reviewed anyway, and they are in french :P
And it will make it easier to test for bugs later, as we will only have to install the new files. And I hope that this will get solved someday T_T
Nathann
comment:28 followup: ↓ 29 Changed 6 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
Since the patch is working and improves upon previous situation, I set it to positive review.
About the c code, Guillaume Ducoffe has a c++/boost implementation. It could be an interesting alternative to the current c code which is apparently no longer maintained by its author. But I don't know if we can use boost (portability).
David.
comment:29 in reply to: ↑ 28 Changed 6 years ago by
Yo !
About the c code, Guillaume Ducoffe has a c++/boost implementation.
Does it compute modular decompositions of graphs?
Nathann
comment:30 Changed 6 years ago by
 Branch changed from public/17950 to e72ab22fddbe84da5018eaf39f546a80d2133b2a
 Resolution set to fixed
 Status changed from positive_review to closed
comment:31 Changed 6 years ago by
 Commit e72ab22fddbe84da5018eaf39f546a80d2133b2a deleted
This ticket modified the unrelated build/pkgs/latte_int/checksums.ini
, see #18139. Now i know why git commit a
is a bad workflow :P
comment:32 Changed 6 years ago by
O_o
Sorryyyy.. I have no idea how that happened, however O_o
Nathann
comment:33 Changed 4 years ago by
should this be reimplemented from scratch, in cython? Unless there is correct external code somewhere that we can use?
comment:34 followup: ↓ 35 Changed 4 years ago by
The original code that we use is no longer maintained. Guillaume Ducoffe has not finalized his code in c++/boost yet. So I'm not aware of external code in c that can be used. We can find implementations in java http://www.cs.utoronto.ca/~mtedder/ or in perl https://metacpan.org/release/GraphModularDecomposition. So it is certainly better to reimplement it with sufficient comments to maintain it.
comment:35 in reply to: ↑ 34 Changed 4 years ago by
Replying to dcoudert:
The original code that we use is no longer maintained. Guillaume Ducoffe has not finalized his code in c++/boost yet. So I'm not aware of external code in c that can be used. We can find implementations in java http://www.cs.utoronto.ca/~mtedder/ or in perl https://metacpan.org/release/GraphModularDecomposition. So it is certainly better to reimplement it with sufficient comments to maintain it.
The perl implementation is for digraphs, so that's a different story all together. (we probably can interface perl with Sage, although it's probably a bit too much trouble).
comment:36 Changed 4 years ago by
If we are to reimplement the modular decomposition in cython, we should certainly finish first the implementation of LexBFS
#11736
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17950: make modular_decomposition an optional spkg