Modular Decomposition

[GoogleCodeExporter]

  Modular decomposition refers to the process of building a modular 
decomposition tree. These can yield very interesting properties about 
graphs (directed, undirected, and hypergraphs alike). More info can be 
found here:

http://en.wikipedia.org/wiki/Modular_decomposition

  In short, a 'module' is a set of nodes M that is indistinguishable from 
the rest of the graph (call it N\M), where indistinguishable indicates that 
if an edge exists from u in N\M to some node v in M, then an edge /must/ 
exist from u to all nodes in M. The intuition behind this is that if you 
only had the information of what the nodes inside M were connected to 
outside of M, you wouldn't see any difference between them.

  An important notion that surrounds this is a Co-graph (we'll consider 
only undirected graphs for now). It's definition is recursive:
- A single node is a cograph.
- The complement of a cograph is a cograph.
- The union of two cographs is a cograph, where the union of graphs G1 and 
G2, G1_G2 is defined as N(G1_G2) = N(G1) + N(G2) and E(G1_G2) = E(G1) + 
E(G2)

  A modular decomposition tree (MDT) is a (unique) representation of a 
graph. The tree has three types of nodes -- series, parallel, and prime. 
The children of each node represent modules. Children of parallel nodes 
have 0 edges between them. Children of series nodes have all edges between 
them. Children of prime nodes have edges between them as defined by a 
'prime graph' associated with the prime node parent. (* while this may 
sound complicated, pictures make things loads easier, and a better 
explanation is attached *)

  Some other things to note / motivate:
- Any graph has a unique modular decomposition tree.
- Many graph algorithms are simple on cographs.
- If a graph's MDT has only series / parallel nodes, then it is a cograph.

  I propose to implement:
- A recently published approach for a linear time modular decomp of 
undirected graphs.
- A divide-and-conquer algorithm algorithm (I think n log n) for directed 
graphs that is conceptually easy.
- An n^2 algorithm for hypergraphs that is currently the best known 
approach.

  Attached is a flash video explaining the linear time MD of undirected 
graphs.

Original issue reported on code.google.com by christian.muise on 17 Nov 2009 at 2:21

Attachments:

• MDTalk.swf

[GoogleCodeExporter]

Original comment by pmatiello on 17 Nov 2009 at 11:49

• Added labels: Milestone-1.8.0

[GoogleCodeExporter]

Original comment by pmatiello on 20 Mar 2010 at 10:22

• Removed labels: Milestone-1.8.0

[GoogleCodeExporter]

Hi, I have been able to finally put a test function for a graph being a module 
of the 
given root graph or not. Am attaching the file, can somebody please validate it 
for 
me?. I believe this should also work for digraphs and hypergraphs. Hoping to 
complete 
the algorithm in a week's time.

Original comment by anand.ib...@gmail.com on 23 May 2010 at 9:56

Attachments:

• unittests-module.py

[GoogleCodeExporter]

    def test_is_sub_graph(rootgr,subgr):    
        for each in modulegr.nodes():
            assert each not in rootgr.nodes()

        for each in modulegr.edges():
            assert each not in rootgr.edges()
        return True

- Should you be asserting that it isn't or that it is in the rootgr? Subgraph 
means 
that all of the nodes and edges must be in the rootgr
- I think you meant subgr and not modulegr (two locations).

----

neighbors[each] = rootgr.neighbors(each)

- You probably should wrap this in a set, otherwise there are a few spots that 
bugs 
could arise here. So:

neighbors[each] = set(rootgr.neighbors(each))

----

for i in len(neighbors):
    for j in len(neighbors)-1:
        neighbors[i] = neighbors[j]

- Since neighbors is a dict, this won't work. You should have:

for set1 in neighbors.values():
    for set2 in neighbors.values():
        assert set1 == set2

----

  With all the fixes, this will only work with undirected graphs. Cheers

Original comment by christian.muise on 24 May 2010 at 10:35

[GoogleCodeExporter]

//Should you be asserting that it isn't or that it is in the rootgr? Subgraph 
means 
that all of the nodes and edges must be in the rootgr
//- I think you meant subgr and not modulegr (two locations).

My apologies, that was sloppy editing.

//neighbors[each] = set(rootgr.neighbors(each))
The only reason i can think of is set returns a unique list, and some cases are 
buggy 
to return duplicate nodes for neighbors. Did you have anything else in mind??

// Since neighbors is a dict, this won't work. 
You are right. I should have tested a snippet first. Forgot that i am still a 
python 
newbie.:)

//With all the fixes, this will only work with undirected graphs.

Yep, you are right. I had assumed it would work for digraphs to based on a 
misconception of how neighbors() work. Which raised a new question, i put it as 
a new 
issue here. Issue 76 http://code.google.com/p/python-graph/issues/detail?id=76

Original comment by anand.jeyahar on 25 May 2010 at 9:44

[GoogleCodeExporter]

Sets:

  Well if you just return a list of neighbors, then the order of elements in each
list could be different and comparing them may fail.

----

Neighbor Naming:

  So if you check out the interface to graph and digraph, 'neighbors' refers to
things that a node connects to, and 'incidents' refers to things connected to 
the
node. So I'm not sure there is anything to change for issue 76 other than 
possibly a
better name (but this would change an integral part of the API).

  Either way, checking for modularity should be done in two phases for digraphs --
one for incidents and one for neighbors. And for hypergraphs you could probably 
just
use the 'hyperedges' method, but it will require quite a bit more care. You can
safely ignore hypergraph modular decomp for now since it is a tricky thing to 
do, and
requires a solid implementation of mod decomp for simple graphs first.

  Cheers

Original comment by christian.muise on 25 May 2010 at 3:17

[GoogleCodeExporter]

An implementation of the modular decomposition algorithm by Tedder et al. (in 
Java) is available at http://www.cs.utoronto.ca/~mtedder/. It may be a useful 
complement to the paper if someone want to (re)implement this.

Original comment by a3nma...@gmail.com on 25 Jul 2012 at 8:28