Opened 5 years ago

Closed 5 years ago

Last modified 3 years ago

#17950 closed enhancement (fixed)

make modular_decomposition an optional spkg

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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) Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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 architecture-dependent (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_decomposition-20100607.tar.bz2

Change History (36)

comment:1 Changed 5 years ago by ncohen

  • Branch set to public/17950
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 5f1e7a6f8a3edf93d1c6835d30dc46cce33dd487

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

5f1e7a6trac #17950: make modular_decomposition an optional spkg

comment:3 Changed 5 years ago by git

  • Commit changed from 5f1e7a6f8a3edf93d1c6835d30dc46cce33dd487 to bedbab187f3399e4231650c2d0947d8513c290b0

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

bedbab1trac #17950: make modular_decomposition an optional spkg

comment:4 follow-up: Changed 5 years ago by dcoudert

  • 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/site-packages
Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/modular_decomposition/__init__.pyc
Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/modular_decomposition/__init__.py
Cleaning up stale file: /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/modular_decomposition/modular_decomposition.so
- cleaning /Users/dcoudert/sage/local/lib/site-python
- cleaning /Users/dcoudert/sage/src/build/lib.macosx-10.9-x86_64-2.7
Cleaning up stale file: /Users/dcoudert/sage/src/build/lib.macosx-10.9-x86_64-2.7/sage/graphs/modular_decomposition/__init__.py
Cleaning up stale file: /Users/dcoudert/sage/src/build/lib.macosx-10.9-x86_64-2.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.macosx-10.9-x86_64-2.7/sage/graphs
copying sage/graphs/graph.py -> build/lib.macosx-10.9-x86_64-2.7/sage/graphs
running build_ext
building 'sage.graphs.modular_decomposition' extension
Executing 1 command (using 1 thread)
gcc -fno-strict-aliasing -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.macosx-10.9-x86_64-2.7/build/cythonized/sage/graphs/modular_decomposition.o -fno-strict-aliasing -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 5 years ago by ncohen

  • 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 5 years ago by git

  • Commit changed from bedbab187f3399e4231650c2d0947d8513c290b0 to 054df904098a3013b6b91fd3662cd00680a24511

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

054df90trac #17950: tell modules_list.py that modular_decomposition is optional

comment:7 Changed 5 years ago by dcoudert

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/site-packages/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 5 years ago by git

  • Commit changed from 054df904098a3013b6b91fd3662cd00680a24511 to 894556fe81b9031df978490c0faac643fad8991e

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

894556ftrac #17950: Removing an import

comment:9 Changed 5 years ago by ncohen

True. This bug does not happen on my computer as modular_decomposition is installed. I just fixed it.

Nathann

comment:10 Changed 5 years ago by dcoudert

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/site-packages/sage/doctest/forker.py", line 492, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/graphs/graph.py", line 6516, in is_prime
        D = self.modular_decomposition()
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/doctest/forker.py", line 492, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/graphs/graph.py", line 6516, in is_prime
        D = self.modular_decomposition()
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/doctest/forker.py", line 492, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/graphs/graph.py", line 6516, in is_prime
        D = self.modular_decomposition()
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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 5 years ago by git

  • Commit changed from 894556fe81b9031df978490c0faac643fad8991e to b2e940fcb80d9b1daa3a09d642347617b4c13277

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

b2e940ftrac #17950: Broken doctests

comment:12 Changed 5 years ago by git

  • Commit changed from b2e940fcb80d9b1daa3a09d642347617b4c13277 to c19a921b7385396cd42a12774618418373887b82

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

c19a921trac #17950: Broken doctests

comment:13 follow-up: Changed 5 years ago by dcoudert

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/sage-ipython: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 5 years ago by ncohen

Hello,

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.

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

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

comment:15 Changed 5 years ago by git

  • Commit changed from c19a921b7385396cd42a12774618418373887b82 to 0ecbf7ce7bd69bf23c215bb2c03852a29637cfcb

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

0ecbf7ctrac #17950: add a link toward sage.misc.packages.

comment:16 Changed 5 years ago by dcoudert

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: 2015-03-13                   │
│ Type "notebook()" for the browser-based 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/sage-ipython: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: 2015-03-13                   │
│ Type "notebook()" for the browser-based 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/site-packages/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: 2015-03-13                   │
│ Type "notebook()" for the browser-based 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/sage-ipython: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: 2015-03-13                   │
│ Type "notebook()" for the browser-based 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/site-packages/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: 2015-03-13                   │
│ Type "notebook()" for the browser-based 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/site-packages/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 5 years ago by ncohen

Well.. On my computer your loop with 1000 random graphs ends without any problem.

comment:18 Changed 5 years ago by dcoudert

With the loop, some times it crashes after 3 graphs, 600, or never. This is really random segfault.

comment:19 Changed 5 years ago by dcoudert

Also, have you seen that I don't always have the same answer on the Petersen?

comment:20 Changed 5 years ago by ncohen

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 5 years ago by dcoudert

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 5 years ago by git

  • Commit changed from 0ecbf7ce7bd69bf23c215bb2c03852a29637cfcb to e72ab22fddbe84da5018eaf39f546a80d2133b2a

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

e72ab22trac #17950: Use the old C code instead

comment:23 Changed 5 years ago by ncohen

  • 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

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

comment:24 follow-up: Changed 5 years ago by dcoudert

Well, now I have directly a segfault :(

What's the difference between the two versions ?

comment:25 in reply to: ↑ 24 Changed 5 years ago by ncohen

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 5 years ago by dcoudert

It's apparently working: no segfault with the big for loop.

Should we consider it is better like that?

David.

comment:27 Changed 5 years ago by ncohen

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 follow-up: Changed 5 years ago by dcoudert

  • 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 5 years ago by ncohen

Yo !

About the c code, Guillaume Ducoffe has a c++/boost implementation.

Does it compute modular decompositions of graphs?

Nathann

comment:30 Changed 5 years ago by vbraun

  • Branch changed from public/17950 to e72ab22fddbe84da5018eaf39f546a80d2133b2a
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:31 Changed 4 years ago by tmonteil

  • 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 4 years ago by ncohen

O_o

Sorryyyy.. I have no idea how that happened, however O_o

Nathann

comment:33 Changed 3 years ago by dimpase

should this be reimplemented from scratch, in cython? Unless there is correct external code somewhere that we can use?

comment:34 follow-up: Changed 3 years ago by 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/Graph-ModularDecomposition. So it is certainly better to reimplement it with sufficient comments to maintain it.

comment:35 in reply to: ↑ 34 Changed 3 years ago by dimpase

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/Graph-ModularDecomposition. 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 3 years ago by dcoudert

If we are to reimplement the modular decomposition in cython, we should certainly finish first the implementation of LexBFS #11736

Note: See TracTickets for help on using tickets.