Linear time implementation of Modular Decomposition for Undirected Graphs

[jlokesh]

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

[dimpase]

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

[jlokesh]

New commits:

​340580e

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

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

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.

[dimpase]

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]

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

[jlokesh]

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

[git]

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

​83387cb

trac #23487: improved readability

[jlokesh]

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.

[git]

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

​0a5a504

trac #23487: added tests, examples + fixed doctests

[jlokesh]

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

[jmantysalo]

Is #13744 a duplicate of this?

[dimpase]

Replying to jmantysalo:

Is #13744 a duplicate of this?

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

[git]

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

​62e5487	Merge branch 'public/gsoc17_t23487' of trac.sagemath.org:sage into moddec
​1e6c92f	rebased over curr. beta and removed an obsolete NOTE

[dimpase]

As this is to be included in 8.1, the branch should be based on the current beta - as I just did in 1e6c92f.

[dimpase]

I will clean up the import statements from sage.*. Specifically, there is a handy import_statements() command in Sage:

sage: import_statements('Graph')
from sage.graphs.graph import Graph

importing from sage.all instead is much less efficient.

[git]

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

​646507e

fixed import and name/address in copyright

[dimpase]

Is there a function to create the quotient graph with the vertices being the max. modules?

Please also make it clear which functions are a part of the main algorithm, and which ones are only used for testing.

Please also add more TEST and EXAMPLE; e.g. the functions to compute mu certainly need tests. In general, all the functions, except 1-liners, will need tests and docs.

[dcoudert]

Some comments:

• in class Queue, method get could return a ValueError. Isn't it more appropriate to directly raise an error?
• in form_module, variable flag can be removed to use while True:
• in either_connected_or_not_connected, use graph.has_edge(u, v) instead of v in graph.neighbors(u)
• method number_subtree could be an internal method of recursively_number_cocomponents. Only used here and number_subtree is the recursive part
• in assembly: while not len(root[1]) == 1: -> while len(root[1]) != 1: ?
• in update_comp_num, instead of tree you could use child
• in get_vertex_in: improve the description since the output block gives more details than the 1 line decription. Also, you don't need a recursive method here. You could rewrite it as

  while tree[0].node_type != NORMAL:
      tree = tree[1][0]
  return tree[1][0]
  

• if left_index - 1 >= 0: -> if left_index >= 1: ?
• in is_component_connected, you don't need to convert explicitly neighbor to set. The isdisjoint accepts a list as input.
• method recurse_component should be an internal method of get_vertices
• in method refine: for e in graph.edges_incident(v): -> for u in graph.neighbor_iterator(v): seems more appropriate. In fact, you can directly build the set x as x = {u for u in graph.neighbor_iterator(v) if vertex_dist[u] != vertex_dist[v]}. You will then have to update the definition of x in the inputs of maximal_subtrees_with_leaves_in_x`
• in maximal_subtrees_with_leaves_in_x, instead of using root[1][-1][0] and root[1][-2][1], why not creating first node a, filling it, add it to root[1], then creating node b, filling it and adding it to root[1] ?
• Add one line description to methods create_prime_node, etc.
• the test methods (test_modular_decomposition, etc.) should be move at the end of the file after a separator like #=====================...

The writing style in sagemath is to start methods with a 1 line description of the functionality, then a blank line, then a longer description of the functionality if needed. So

def recursively_number_cocomponents(tree, cocomp_num, by_type):
    """
    Recursively number the nodes in the (co)components.

    If the tree node_type is same as by_type then cocomp_num is incremented
    before assigning to the subtree else entire tree is numbered by cocomp_num.

    INPUTS:
    """

It's a long patch to review...

[jlokesh]

Replying to dimpase:

Is there a function to create the quotient graph with the vertices being the max. modules?

Currently there is no function which creates a quotient graph with the vertices being the maximal modules. I can create such a function though?

Please also make it clear which functions are a part of the main algorithm, and which ones are only used for testing.

David has asked me to move the test functions at the end after a separator, it will solve this problem.

Please also add more TEST and EXAMPLE; e.g. the functions to compute mu certainly need tests. In general, all the functions, except 1-liners, will need tests and docs.

I will definitely add more TESTS and EXAMPLES. It might take some time as each function requires some arguments mostly a tree or a module. I will need to input that manually.

Thanks for fixing the import and copyright!

[jlokesh]

Replying to dcoudert:

Thanks for reviewing the patch! I will make the changes and add a commit soon.

[git]

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

​433ee5e

trac #23487: improved code + documentation

[dcoudert]

It is much better now. Some more comments.

• on the left hand side, you don't need to write [a,b] = [1,2]. You can directly write a,b = [1,2]

• You can permute variables without intermediate variable as a,b = b,a

• in method __str__, you don't need variable string. You can directly return the result.

• in the EXAMPLES block of modular_decomposition, you must put :: at the end of the sub blocks instead of :. This is for the html documentation.

• Some of the examples in the TESTS block of modular_decomposition could be in the EXAMPLES block. Also, can you add sub blocks with indication on the origin of the tested graphs ?

• Then, can you have tests for bad inputs in modular_decomposition, like directed graph, etc. i.e., the raise error stuff

• I have an identation issue with the """ before the code

• in compute_mu_for_co_component: You don't need the intermediate variable mu_for_co_component.

• in compute_mu_for_component: why not using range(source_index-1, -1, -1) and returning the first found value ?

• method recursive_print_md_tree could be an internal method of print_md_tree. Also, instead of using level, you could directly pass a string as parameter, recursive_print_md_tree(tree, level + " "). Last, use print("{}{}".format(level,str(root[0]))) for Python 3 compatibility.

[jlokesh]

Replying to dcoudert:

• I have an identation issue with the """ before the code

I could not understand which """ you are talking about? Is it the one in the beginning? Is the indentation issue in the doc build?

• in compute_mu_for_component: why not using range(source_index-1, -1, -1) and returning the first found value ?

  if mu_for_component == root[1][index] and \

Suppose [c01, c02, c03, source, c1, c2, c3] is the forest. If mu value for c2 is c03 then c01 and c02 must be connected to c2. Therefore the iteration from 0 is required.

I have incorporated the other changes and will add a commit for it.

[git]

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

​72d87e8

improvements in the code and documentation

[dcoudert]

Replying to jlokesh:

Replying to dcoudert:

• I have an identation issue with the """ before the code

I could not understand which """ you are talking about? Is it the one in the beginning? Is the indentation issue in the doc build?

The one before if graph._directed. Note that it is better to use if graph.is_directed() ;)

[dcoudert]

When you add a link to a wikipedia page, the nice way to do it is: :wikipedia:`Modular_decomposition`.

[jlokesh]

Replying to dcoudert:

The one before if graph._directed. Note that it is better to use if graph.is_directed() ;)

Found it. :) I will include these changes in the next commit along with TESTS and EXAMPLES for other functions.

[git]

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

​6f7af1e

trac #23487: added TESTS and EXAMPLES

[ylchapuy]

Out of curiosity, have you considered using collections.dequeue instead of making your own (inefficient) Queue class?

​https://wiki.python.org/moin/TimeComplexity

[dcoudert]

I was not aware of this data structure. It's certainly what we need here.

[git]

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

​92c1de0	Merge branch 'develop' into moddec
​1ff6668	Merge branch 'public/gsoc17_t23487' of trac.sagemath.org:sage into moddec
​ab14394	removed "print " from tests/examples

[git]

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

​caedc65

trac #23487: Used colloection.deque instead of Queue

[git]

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]

@Dima: 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]

Replying to dcoudert:

@Dima: 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).

[ylchapuy]

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

[jlokesh]

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?

[jlokesh]

Replying to 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]

I agree. It would be cleaner.

Replying to jlokesh:

Replying to 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]

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.

[jlokesh]

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.

[git]

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

​7ebb0ab

trac #23487: Improved code structure

[jlokesh]

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]

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.

[jlokesh]

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]

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

[dimpase]

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.

[jlokesh]

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]

Replying to jlokesh:

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]

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

[dcoudert]

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

[jlokesh]

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.

[jlokesh]

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.

[git]

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

​eeed64c

documentation changes + small fixes

[jlokesh]

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

[git]

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

[dimpase]

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

[git]

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

​fd26fff

correct docstrings syntax

[dimpase]

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

[jlokesh]

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]

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

[git]

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

​6688bac

trac #23487: added examples

[dimpase]

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

Looks good to me.