Opened 9 years ago

Closed 9 years ago

#9111 closed enhancement (fixed)

modular decomposition

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.5.2
Component: graph theory Keywords:
Cc: Merged in: sage-4.5.2.alpha0
Authors: Nathann Cohen, Thierry de Montgolfier Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Using the C code written by Thierry de Montgolfier and available there : http://www.liafa.jussieu.fr/~fm/algos/index.html

We now have a Graph.modular_decomposition function available in Sage !

Nathann

Attachments (3)

trac_9111-doc-edits.patch (2.9 KB) - added by rlm 9 years ago.
trac_9111-doc_addition.patch (4.6 KB) - added by ncohen 9 years ago.
trac_9111.patch (57.2 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 9 years ago by mhansen

From that webpage, it says that the code is only available for non-commercial use.

comment:2 Changed 9 years ago by ncohen

yesyesyes, it should be licensed under the GPL very soon :-)

Fabrice de Montgolfer is away for something like a week, and then it should be done :-)

Nathann

comment:3 Changed 9 years ago by jason

  • Status changed from new to needs_work

A couple of comments:

  1. Why is modular_decomposition.c included in the patch?
  1. The comment at the top of modular_decomposition.pyx indicates it is a copy of code, but is it rather a Cython interface to C code?
  1. It wouldn't hurt to give a very brief explanation of what a modular decomposition of a graph is in the docstrings

comment:4 Changed 9 years ago by jason

And 4. This functionality is cool!

comment:5 follow-up: Changed 9 years ago by ncohen

Hello !

  1. Because I wasn't paying attention
  1. I mean by this that the lines of the code building the graph according to the format used in the .c file, along with the ones reading the decomposition once it is computed, can be found in the .c files too. I copied those and Cythonized them, but the "real" code is still contained in the .c file.
  1. Indeed.
  1. I think so, too ! Especially in C, and in mlog(n) :-)

I will update the patch once the software is "officially" GPL2, which could mean next week.

Nathann

comment:6 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is ! With a brand-new GPL2 licence, thanks to Fabien de Montgolfier ! :-)

Nathann

Changed 9 years ago by rlm

comment:7 in reply to: ↑ 5 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen, Thierry de Montgolfier
  • Reviewers set to Robert Miller, ?

Replying to ncohen:

  1. I mean by this that the lines of the code building the graph according to the format used in the .c file, along with the ones reading the decomposition once it is computed, can be found in the .c files too. I copied those and Cythonized them, but the "real" code is still contained in the .c file.

Can you make this a bit more clear in the documentation? (Please, in a new patch on top of attachment:trac_9111-doc-edits.patch to avoid conflict with the other patch.)

It seems like there should be more thorough documentation of the idea of modular decomposition. Perhaps a chapter, or at least a chunk, for the reference manual, or a guided tour or something? I don't want to block this from getting merged because of this, but maybe in a future ticket?

I'm happy with this patch in that it passes its tests and the docs look good, but I'd be much more comfortable with a second reviewer, since I'm not very familiar with modular decompositions. I can certainly offer half of a positive review, though.

comment:8 Changed 9 years ago by ncohen

Here is a bit more of documentation, if it pleases you :-)

I also added a reference to a freely-downloadable survey, just in case !

Nathann

Changed 9 years ago by ncohen

comment:9 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work
  • Work issues set to tabs in source code
sage -t -long sage/graphs/modular_decomposition/modular_decomposition.pyx
**********************************************************************
Error: TAB character found.

	 [4.5 s]

comment:10 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is !! The "tab" characters were not at the beginning but at the end of some lines... some unlucky copy/paste :-)

Nathann

Changed 9 years ago by ncohen

comment:11 Changed 9 years ago by rlm

  • Reviewers changed from Robert Miller, ? to Robert Miller
  • Status changed from needs_review to positive_review

Apply in the following order:


trac_9111.patch
trac_9111-doc-edits.patch
trac_9111-doc_addition.patch

comment:12 Changed 9 years ago by ncohen

Great !! Thank youuuuuu ! :-)

Nathann

comment:13 Changed 9 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
  • Work issues tabs in source code deleted
Note: See TracTickets for help on using tickets.