Linear time implementation of Modular Decomposition for Undirected Graphs #23487

lokeshj1703 · 2017-07-20T06:02:37Z

This is aimed at providing linear time implementation for finding modular decomposition of undirected graphs, fixing the currently broken Sage's graph modular decomposition.

CC: @dimpase @dcoudert

Component: graph theory

Keywords: modular decomposition, gsoc2017

Author: Lokesh Jain

Branch: 6688bac

Reviewer: David Coudert, Dima Pasechnik

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

The text was updated successfully, but these errors were encountered:

dimpase · 2017-07-20T09:45:39Z

Changed keywords from modular decomposition to modular decomposition, GSOC 2017

dimpase · 2017-07-20T09:45:39Z

comment:1

It will use the implementation from https://github.com/lokeshj1703/Undirected-Modular-Decomposition

dimpase · 2017-07-20T09:46:22Z

Changed keywords from modular decomposition, GSOC 2017 to modular decomposition, gsoc2017

lokeshj1703 · 2017-07-25T19:06:18Z

Branch: u/jlokesh/23487

lokeshj1703 · 2017-07-25T19:06:18Z

New commits:

`340580e`	`trac #23487: added modular decomposition module + removed old one`

lokeshj1703 · 2017-07-25T19:06:18Z

Commit: 340580e

dcoudert · 2017-07-26T09:17:56Z

comment:4

Dear Lokesh,

why have you removed file modular_decomposition.pyx ? You should put it back for the moment. There are dependencies and so I'm unable to compile sage with your patch.

Many improvements are needed in your code that we will slowly address. Dima is certainly more expert than me in this. For instance:

Comments must be in 80 column mode. Some editors like emacs ease the formatting.
Prefer # Nested module to #Nested module to improve readability
You can also insert some empty lines in some code blocks to improve readability
Returns True if ... -> Return True if ...
You will also have to insert some TESTS: and EXAMPLES: blocks to illustrate the behavior of the methods, in particular for modular_decomposition, and for testing cases that could lead to errors.

dcoudert · 2017-07-26T09:17:56Z

Reviewer: David Coudert, Dmitrii Pasechnik

dimpase · 2017-07-26T09:25:46Z

comment:5

Replying to @dcoudert:

Dear Lokesh,

why have you removed file modular_decomposition.pyx ? You should put it back for the moment. There are dependencies and so I'm unable to compile sage with your patch.

this should be trivial to fix. Let's remove it now for good.

dimpase · 2017-07-26T10:17:08Z

Changed commit from 340580e to dd540d6

dimpase · 2017-07-26T10:17:08Z

comment:6

this is the updates needed for Sage to build and run. modular_decomposition doctests in graph.py fail due to some format incompatibility of output of the new implementation.
I'll leave it to Lokesh to fix, as well as the David's comments, naturally.

New commits:

`dd540d6`	`updates to allow sage build. doctests in graph.py still fail`

dimpase · 2017-07-26T10:17:08Z

Changed branch from u/jlokesh/23487 to public/gsoc17_t23487

lokeshj1703 · 2017-07-28T18:33:21Z

comment:7

Sorry for the late reply. I have started working on the updates. I will push the commit shortly.

sagetrac-git · 2017-07-29T10:20:20Z

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

`83387cb`	`trac #23487: improved readability`

sagetrac-git · 2017-07-29T10:20:20Z

Changed commit from dd540d6 to 83387cb

lokeshj1703 · 2017-07-29T10:24:09Z

comment:9

I have added a commit for improved readability in the code. This commit addresses first four issues pointed out by David. I will soon add a commit for including examples, test cases and for handling failure of doctests.

sagetrac-git · 2017-07-30T17:37:34Z

Changed commit from 83387cb to 0a5a504

sagetrac-git · 2017-07-30T17:37:34Z

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

`0a5a504`	`trac #23487: added tests, examples + fixed doctests`

lokeshj1703 · 2017-07-30T17:48:53Z

comment:11

I have added the commit for fixing the doctests and added the Tests and Examples for modular_decomposition function. Should I add the examples for other functions as well? Because most of the functions are called from modular_decomposition itself.

For the tests for modular_decomposition I have added the graph from Marc Tedder research paper and an example from the wikipedia modular decomposition page. Further I have added a series graph (Tetrahedral Graph).

jm58660 · 2017-08-07T17:35:24Z

comment:13

Is #13744 a duplicate of this?

dimpase · 2017-08-10T10:11:05Z

comment:14

Replying to @jm58660:

Is #13744 a duplicate of this?

Yes, the latter can be closed as won't fix, with the fixing done here.

sagetrac-git · 2017-08-11T07:19:28Z

Changed commit from 0a5a504 to 1e6c92f

lokeshj1703 · 2017-09-05T18:08:19Z

comment:47

I am not able to find any resource on building graphs from modular decomposition. I am assuming we are trying to build a graph given a modular decomposition. Please correct me if I am wrong. If so I have a doubt about it being possible. If we consider this example-:

    g = Graph(5)
    g.add_edge(0,1)
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(4,3)
    g.add_edge(1,3)
    g.modular_decomposition()

(PRIME, [1, 0, 2, 3, 4])

and if we remove the edge (1,3) from it and then find the modular decomposition. Then also the result is same.

dcoudert · 2017-09-06T09:13:08Z

comment:48

You are right, a proper definition is needed and I don't know any. So nothing to do.

dimpase · 2017-09-06T13:56:57Z

comment:49

I thin you can define a graph on the immediate descendants of the module of all the vertices; these are the proper maximal strong modules of the graph. As as example from Wikipedia, see

here the original graph is at top left corner, and the graph I am talking about is shown on the right from the root note [1,...,11] of the modular decomposition tree at the bottom left part.

lokeshj1703 · 2017-09-07T07:14:14Z

comment:50

Parallel module is easy to build into a graph. Series and Prime module are formed if the induced subgraph is connected but they can not tell how this graph is connected or what edges are there and what are not. As illustrated by example in comment 47.

dimpase · 2017-09-07T08:15:05Z

comment:51

Replying to @lokeshj1703:

Parallel module is easy to build into a graph. Series and Prime module are formed if the induced subgraph is connected but they can not tell how this graph is connected or what edges are there and what are not. As illustrated by example in comment 47.

It is irrelevant what happens inside each module, for the vertices of each module used to construct the new graph will be merged into one. What's important is how modules are connected among each other. In the example in comment 47 the graph in question will have just one vertex (or perhaps it should be empty graph, but that's a very minor issue).

dimpase · 2017-09-07T08:52:12Z

comment:52

to clarify: I am talking about the quotient graph I started talking in comment 19, and you mentioned in comment 21.

dcoudert · 2017-09-07T09:31:32Z

comment:53

In graph.py:

if self.order() == 0 or self.order() == 1: -> if self.order() <= 1:

In modular_decomposition.py:

Why are you defining the string representation of class NodeType ? I think it is not used and self.name is not assigned here. And why not for class NodeSplit.
I the test Graph from wikipedia link :wikipedia:`Modular_decomposition`::`, you must change sage: g = Graph(d) to sage: g = Graph(d2).

lokeshj1703 · 2017-09-07T18:57:53Z

comment:54

Replying to @dimpase:

to clarify: I am talking about the quotient graph I started talking in comment 19, and you mentioned in comment 21.

That is not a problem then. Only thing to discuss would be the structure of quotient graph. Should the children have a pointer to quotient graphs they represent(the maximal modules). In such a case the structure would be same as the one on the top right portion of the image you shared.

lokeshj1703 · 2017-09-07T19:05:17Z

comment:55

Replying to @dcoudert:

Why are you defining the string representation of class NodeType ? I think it is not used and self.name is not assigned here. And why not for class NodeSplit.

It is used in graph.py for printing the module type.

relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]

Here x.node_type is an object of NodeType class. For NodeType.PARALLEL it would be PARALLEL.

sagetrac-git · 2017-09-18T18:32:07Z

Changed commit from 7ebb0ab to eeed64c

sagetrac-git · 2017-09-18T18:32:07Z

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

`eeed64c`	`documentation changes + small fixes`

lokeshj1703 · 2017-09-18T18:34:54Z

comment:57

I have made some changes to the documentation of modular_decomposition function in graph.py. Please review it.

sagetrac-git · 2017-09-18T21:25:43Z

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

`32ff8db`	`Merge branch 'public/gsoc17_t23487' of trac.sagemath.org:sage into modde`
`c9af7d6`	`putting HabPau10 back in; docs build now`

sagetrac-git · 2017-09-18T21:25:43Z

Changed commit from eeed64c to c9af7d6

dimpase · 2017-09-18T21:25:59Z

comment:59

You have removed the reference HabPau10. It should stay, as it is a recent
survey paper on the topic, in fact, newer than TedCorHabPaul08.
Also, note that this reference is still used in the text, and as a result docs don't build any more.

Perhaps it's time that you should check docs for building, before pushing in changes to them :-)

Anyhow, I'm putting the reference back.

New commits:

`32ff8db`	`Merge branch 'public/gsoc17_t23487' of trac.sagemath.org:sage into modde`
`c9af7d6`	`putting HabPau10 back in; docs build now`

New commits:

`32ff8db`	`Merge branch 'public/gsoc17_t23487' of trac.sagemath.org:sage into modde`
`c9af7d6`	`putting HabPau10 back in; docs build now`

sagetrac-git · 2017-09-18T21:59:40Z

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

`fd26fff`	`correct docstrings syntax`

sagetrac-git · 2017-09-18T21:59:40Z

Changed commit from c9af7d6 to fd26fff

dimpase · 2017-09-18T23:46:32Z

comment:61

as you can see from patchbot's output, about 20 functions miss doctests.

lokeshj1703 · 2017-09-19T18:09:06Z

comment:62

Replying to @dimpase:

Perhaps it's time that you should check docs for building, before pushing in changes to them :-)

Thanks for fixing it. Will check it next time :-)

dimpase · 2017-09-24T19:58:05Z

comment:63

So, how about adding missing tests?
It's basically just adding temporary print() statements into functions with missing doctests, recoding the results of printing for an example run, and converting these into
doctests.

If you are too busy now, I can do this, I don't want to sit on this ticket for too long...

sagetrac-git · 2017-09-28T17:46:34Z

Changed commit from fd26fff to 6688bac

sagetrac-git · 2017-09-28T17:46:34Z

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

`6688bac`	`trac #23487: added examples`

dimpase · 2017-10-15T21:11:19Z

comment:65

I missed that update - only comments are emailed to me, no commit notifications.

Looks good to me.

vbraun · 2017-10-20T09:15:29Z

Changed branch from public/gsoc17_t23487 to 6688bac

jdemeyer · 2017-12-08T14:56:23Z

Changed commit from 6688bac to none

jdemeyer · 2017-12-08T14:56:23Z

Changed reviewer from David Coudert, Dmitrii Pasechnik to David Coudert, Dima Pasechnik

lokeshj1703 added this to the sage-8.1 milestone Jul 20, 2017

lokeshj1703 added c: graph theory labels Jul 20, 2017

This comment has been minimized.

Sign in to view

dimpase added t: bug and removed c: modular forms labels Jul 20, 2017

lokeshj1703 added the s: needs review label Aug 7, 2017

dimpase added s: positive review and removed s: needs review labels Oct 15, 2017

vbraun removed the s: positive review label Oct 20, 2017

vbraun closed this as completed in 5e511a3 Oct 20, 2017

Linear time implementation of Modular Decomposition for Undirected Graphs #23487

Linear time implementation of Modular Decomposition for Undirected Graphs #23487

Comments

lokeshj1703 commented Jul 20, 2017

dimpase commented Jul 20, 2017

dimpase commented Jul 20, 2017

This comment has been minimized.

dimpase commented Jul 20, 2017

lokeshj1703 commented Jul 25, 2017

lokeshj1703 commented Jul 25, 2017

lokeshj1703 commented Jul 25, 2017

dcoudert commented Jul 26, 2017

dcoudert commented Jul 26, 2017

dimpase commented Jul 26, 2017

dimpase commented Jul 26, 2017

dimpase commented Jul 26, 2017

dimpase commented Jul 26, 2017

lokeshj1703 commented Jul 28, 2017

sagetrac-git mannequin commented Jul 29, 2017

sagetrac-git mannequin commented Jul 29, 2017

lokeshj1703 commented Jul 29, 2017

sagetrac-git mannequin commented Jul 30, 2017

sagetrac-git mannequin commented Jul 30, 2017

lokeshj1703 commented Jul 30, 2017

jm58660 mannequin commented Aug 7, 2017

dimpase commented Aug 10, 2017

sagetrac-git mannequin commented Aug 11, 2017

lokeshj1703 commented Sep 5, 2017

dcoudert commented Sep 6, 2017

dimpase commented Sep 6, 2017

lokeshj1703 commented Sep 7, 2017

dimpase commented Sep 7, 2017

dimpase commented Sep 7, 2017

dcoudert commented Sep 7, 2017

lokeshj1703 commented Sep 7, 2017

lokeshj1703 commented Sep 7, 2017

sagetrac-git mannequin commented Sep 18, 2017

sagetrac-git mannequin commented Sep 18, 2017

lokeshj1703 commented Sep 18, 2017

sagetrac-git mannequin commented Sep 18, 2017

sagetrac-git mannequin commented Sep 18, 2017

dimpase commented Sep 18, 2017

sagetrac-git mannequin commented Sep 18, 2017

sagetrac-git mannequin commented Sep 18, 2017

dimpase commented Sep 18, 2017

lokeshj1703 commented Sep 19, 2017

dimpase commented Sep 24, 2017

sagetrac-git mannequin commented Sep 28, 2017

sagetrac-git mannequin commented Sep 28, 2017

dimpase commented Oct 15, 2017

vbraun commented Oct 20, 2017

jdemeyer commented Dec 8, 2017

jdemeyer commented Dec 8, 2017