Linear time implementation of Modular Decomposition for Undirected Graphs

[lokeshj1703]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

12f3f15

trac #23487: Used collections.deque instead of Queue

[dcoudert]

comment:36

@dimpase: in the output of modular_decomposition we have PRIME, PARALLEL, SERIES, etc. wouldn't be better to have strings as before ?

@Lokesh: how difficult would it be to build the graph of the modular decomposition? I mean a graph in which for instance would keep a single vertex instead of twins.

[dimpase]

comment:37

Replying to @dcoudert:

@dimpase: in the output of modular_decomposition we have PRIME, PARALLEL, SERIES, etc. wouldn't be better to have strings as before ?

It's a good idea to document what these PRIME, etc., stand for from Python point of view. Are they some kind of constants?

@Lokesh: how difficult would it be to build the graph of the modular decomposition? I mean a graph in which for instance would keep a single vertex instead of twins.

IMHO it's a question of constructing the induced subgraph, with vertices taken to be a transversal of the corresponding modules. (Thus it's easy, but should be provided, perhaps on a followup ticket).

[2c00b582-cfe9-43b9-8124-fec470060704]

comment:38

Another remark about the implementation. I find it strange that you create a NodeInfo class but don't go all the way creating a structure for your modular decomposition.

I would just add a member NodeInfo.children beeing a list of NodeInfos and rename this NodeInfo into something catchier. This would e.g. change

for tree in root[1]:
    if tree[0].node_type == NORMAL and tree[1][0] in vertex_status
    ...

into the more expressive

for node in root.children:
    if node.node_type == NORMAL and node.children[0] in vertex_status
    ...

[lokeshj1703]

comment:39

Replying to @dimpase:

It's a good idea to document what these PRIME, etc., stand for from Python point of view. Are they some kind of constants?

Yes, these are constants. I have documented them in the NodeInfo class under the data attribute node_type where they are mostly used. I can even convert them into an enum which can have proper documentation?

[lokeshj1703]

comment:40

Replying to @sagetrac-ylchapuy:

I agree with you. It makes much more sense like that. If Dima and David agree I can work on that as well? It might take a lot of time as it requires a lot of changes.

[dcoudert]

comment:41

I agree. It would be cleaner.

Replying to @lokeshj1703:

Replying to @sagetrac-ylchapuy:

I agree with you. It makes much more sense like that. If Dima and David agree I can work on that as well? It might take a lot of time as it requires a lot of changes.

[dcoudert]

comment:42

Can you check the result for a graph with a single vertex.

sage: print G.modular_decomposition()
()
sage: G = Graph(2)
sage: print G.modular_decomposition()
(PARALLEL, [0, 1])
sage: G = Graph(1)
sage: print G.modular_decomposition()
0

Also, unify "Series" / "SERIES", etc. in the documentation of the modular decomposition method in graph.py.

[lokeshj1703]

comment:43

Replying to @dcoudert:

Can you check the result for a graph with a single vertex.

For a single vertex it returns the vertex itself.

Also, unify "Series" / "SERIES", etc. in the documentation of the modular decomposition method in graph.py.

I will handle it in the next commit.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7ebb0ab

trac #23487: Improved code structure

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 12f3f15 to 7ebb0ab

[lokeshj1703]

comment:45

I have changed the NodeInfo class to Node class in this commit and introduced a children field in this class. The constants like PARALLEL, LEFT_SPLIT... defined in the file have been added in an enumeration class. Further as pointed out by David the singleton should be treated as PRIME module. Therefore I have made the appropriate changes in the modular_decomposition and is_prime function of graph.py.

There are changes required in the Algorithm and References section of the modular_decomposition function of the graph.py. I will make those along with the revisions.

[dcoudert]

comment:46

That's much better now.

One question: how difficult is it to build a graph from the modular decomposition ? In such graph, twins are merged into a single node with as label the Set of merged nodes (see e.g., the result of treewidth).

There is no need to do it in this ticket. It could be postpone to a future ticket.

[lokeshj1703]

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]

comment:48

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

[dimpase]

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]

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]

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]

comment:52

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

[dcoudert]

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]

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]

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7ebb0ab to eeed64c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

eeed64c

documentation changes + small fixes

[lokeshj1703]

comment:57

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from eeed64c to c9af7d6

[dimpase]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

fd26fff

correct docstrings syntax

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c9af7d6 to fd26fff

[dimpase]

comment:61

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

[lokeshj1703]

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]

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...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fd26fff to 6688bac

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6688bac

trac #23487: added examples

[dimpase]

comment:65

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

Looks good to me.

[vbraun]

Changed branch from public/gsoc17_t23487 to 6688bac

[jdemeyer]

Changed commit from 6688bac to none

[jdemeyer]

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