Add the Habib Maurer algorithm for modular decomposition to graphs

[deinst]

Experience has shown that the modern modular decomposition linear algorithms are extremely tricky to implement correctly. Adding an implementation of the much more straightforward O(n³)algorithm from Habib and Maurer "On the X-Join decomposition for undirected graphs" would give us a baseline to test against.

Also move modular decomposition into the graph decompositions directory.

[deinst]

The code should now be functional. I need to fix up the documentation and add a bunch of tests.

---

New commits:

​534ba95	Moved modular_decomposition.
​6722b32	Fix is_prime
​8e57c73	Added Habib-Maurer algorithm to Graph.modular_decomposition

[git]

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

​d00dcbe

Added some randomized tests.

[dcoudert]

Some comments:

• instead of inner function vertex_set, use:

  from itertools import chain
  frozenset(chain.from_iterable(loe))
  

• Do you really need to sort vertices ? For instance, the gamma function returns a dictionary keyed by tuples of sorted vertices. Can't you instead use frozensets as keys ? similarly, you could keyed dictionary components by frozensets to avoid e = tuple(sorted((v1, v))). Sinc ewe are working on the transition to Python3 that forbid comparison of objects of different types, it is better to avoid sorting when not needed. Also, sorting takes some time.
• When you do components[old_edge] = components[e] wouldn't it be more efficient to use union-find (DisjointSet) ? If I understand well, you merge groups of edges, right ?
• what is either_connected_or_not_connected ?

[deinst]

Thanks for looking at this.

Your first three points are accurate, and I will fix things accordingly (I'll also change the other places where I use sorted tuples to identify subtrees). I wasn't aware of DisjointSet, it's very cool.

either_connected_or_disconnected is a part of the existing modular decomposition infrastructure. It tests if a given vertex is either connected to all the vertices in the module or is disconnected from all the vertices in the module.

[git]

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

​a81f2d2

Added code for random test of modular decomposition from reconstruction

[deinst]

I also added a bunch of other stuff in that commit, replaced the sorted lists with frozen sets, added itertools.chain and DisjointSet to the Gamma class code. I apologize for doing too many things at once. All that has to be done is to clean the code up a bit and write some human comprehensible documentation.

[git]

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

​314ada6	Minor documentation changes.
​abe1365	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
​ff7c910	Fixed up docstrings.

[deinst]

Most of the new code is to support the random tests.

[git]

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

​65ed276

Fixed errors the patchbot was complaining about

[dcoudert]

A few comments:

• use iterator over vertices and edges when there is no need to create a list

  - pieces = DisjointSet([frozenset(e) for e in graph.edges(labels=False, sort=False)])
  - for v in graph.vertices():
  + pieces = DisjointSet(frozenset(e) for e in graph.edge_iterator(labels=False))
  + for v in graph:
  

• Testing if something is 0 or empty can be done like that

  - if graph.order() == 0:
  + if not graph.order():
  

• - elif not graph.complement().is_connected():
  -    root = create_series_node()
  -    root.children = [habib_maurer_algorithm(graph.subgraph(vertices=sg), g_classes)
  -             for sg in graph.complement().connected_components()]
  -    return root
  + g_comp = graph.complement()
  + if g_comp.is_connected():
  +     root = create_series_node()
  +     root.children = [habib_maurer_algorithm(graph.subgraph(vertices=sg), g_classes)
  +                 for sg in g_comp.connected_components()]
  +     return root
  

• - if g_classes == None:
  + if g_classes is None:
  

• - vertex_set = frozenset(graph.vertices())
  + vertex_set = frozenset(G.vertex_iterator())
  

• sub.neighbors(v) -> sub.neighbor_iterator(v)

[git]

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

​8ba0fc6

Implemented suggested changes

[deinst]

I thank you for all the work that you've done to improve this. A few more silly questions.

I'm not fond of using frozensets of two numbers to identify edges of an undirected graph, but do not see any other way to work it without sorting.

Also the last patchbot run complained of non-ascii characters: I cannot find any. There were also complaints from the coverage tests of 6 missing doctests. Is there any way to figure out exactly what it wants?

[git]

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

​0a06a7b

Added missing doctests.

[deinst]

Ok this should cover the complaints about the coverage. I broke down and RTFM'd and it should work now. I don't know what to do about the startup time complaint. Nothing I did should affect the startup time, should it?

[deinst]

Ok, I have no idea what is going on with the patchbot. Of course src/sage/graphs/modular_decomposition.py does not exist. Why is it looking for it? I'm more than willing to admit fault, but I have no idea what I did.

[tscrim]

The patchbot can be quite dumb, so don't always read so much into it. Some quick comments:

         EXAMPLES::
+
             sage: from sage.graphs.graph_decompositions.modular_decomposition import *
             sage: NodeType.PARALLEL
             PARALLEL

(although the __str__ is actually not being tested because you explicitly need to call str(NodeType.PARALLEL, but the method is unnecessary in this case IIRC; worst-case a simple alias __str__ = __repr__ can be done).

TODO: -> .. TODO:: (and putting the todo part in an indented block).

Your INPUT: items should start with a lowercase letter and not end with a period (unless they are multiple sentences).

I think the example graphs, e.g., from Marc Tedder, should be with the usual EXAMPLES: block. Moreover, I don't see why you need two TESTS: blocks.

I would add a reference to the Habib and Maurer paper.

$O(n^3)$ -> `O(n^3)`

[dcoudert]

You should rebuild on last beta and resolve merge conflicts.

[git]

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

​fc82c80	Small doc fixes.
​e00479e	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
​a86307a	Fixed doctests for __str__ and __repr__

[dcoudert]

Some more comments, mostly cosmetic.

1. in graph.py:

   -        - ``algorithm`` -- (default: ``'tedder'``) specifies the algorithm to
   -          use among:
   +        - ``algorithm`` -- string (default: ``'tedder'``); specifies the
   +          algorithm to use among:
   

• When ``algorithm=tedder`` -> When ``algorithm='tedder'``
• When ``algorithm=habib`` -> When ``algorithm='habib'``

-        - ``algorithm`` -- (default: ``'tedder'``) specifies the algorithm to
-          use to find the modular decomposition from among:
+        - ``algorithm`` -- string (default: ``'tedder'``); specifies the
+          algorithm to use among:

2. in modular_decomposition.py

in __str__, __repr__, __init__

-            sage: from sage.graphs.graph_decompositions.modular_decomposition import *
+            sage: from sage.graphs.graph_decompositions.modular_decomposition import NodeType

This could be better

-    NodeSplit is an enumeration class which is used to specify the split that
-    has occurred at the node or at any of its descendants.
+    Enumeration class specifying the split that occurred at a node or any of
+    its descendants.

-    * If the graph is not fragile (neither it or its complement is
-    disconnected) then there is exactly one class that visits all the
-    vertices of the graph, and this class consists of just the edges
-    that connect the maximal strong modules of that graph.
+    * If the graph is not fragile (neither it or its complement is
+      disconnected) then there is exactly one class that visits all the
+      vertices of the graph, and this class consists of just the edges
+      that connect the maximal strong modules of that graph.

Align in 80 columns mode:

+    The gamma_classes of the octahedral graph are the three 4-cycles corresponding to
+    the slices through the center of the octahedron::

Remove blank lines

+    """
+
+
+    from itertools import chain

• graph.edges(labels=False, sort=False) -> graph.edge_iterator(labels=False)

-    - ``g_classes`` -- a dictionary whose values are the gamma classes of the
-      graph, and whose keys are a frozenset of the vertices corresponding to
-      the class. Used internally.
+    - ``g_classes`` -- dictionary (default: ``None``); a dictionary whose values
+      are the gamma classes of the graph, and whose keys are a frozenset of the
+      vertices corresponding to the class. Used internally.

-    - ``root`` -- The root of the modular decomposition tree.
+    - ``root`` -- the root of the modular decomposition tree

-    - ``nest`` -- A nested tuple of the form returned by ``tree_to_nested_tuple``.
+    - ``nest`` -- a nested tuple of the form returned by ``tree_to_nested_tuple``

-    - ``root`` -- The root of the tree.
+    - ``root`` -- the root of the tree

-        perm = dict( [ i, perm(i) ] for i in get_vertices(root) )
+        perm = {i: perm(i) for i in get_vertices(root)}

-        raise TypeError("Type of perm is not supported for relabeling.")
+        raise TypeError("type of perm is not supported for relabeling")

80 columns mode for

+    Check that a graph and its permuted relabeling have the same modular decomposition.

In general, all comments must be in 80 columns mode.

-        random_perm = Permutations(list(g1.vertices())).random_element()
+        random_perm = Permutations(list(g1)).random_element()

Don't put a . at the end of itemize like this, unless you have several sentences.

+    - ``max_depth`` -- the maximum depth of the tree.

+================================================================================

[git]

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

​225dfe0	Improved formatting of documentation
​161e1d6	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs

[git]

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

​cd41b57

fixed stupid errors

[mantepse]

two superficial questions:

• would it be sensible / feasable / outside the scope of this ticket to make modular_decomposition actually return a LabelledRootedTree?

• it would be more emacs-friendly to use

              sage: from sage.graphs.graph_decompositions.modular_decomposition \
              ....:      import NodeType
  

instead of

            sage: from sage.graphs.graph_decompositions.modular_decomposition \
                       import NodeType

[dcoudert]

It is certainly possible to add a parameter to choose the output format.

[dcoudert]

Sorry for the delay in reviewing this ticket. It is almost ready.

• consider comment ​https://trac.sagemath.org/ticket/26496#comment:25

• Ensure that comments are in 80 columns formatting mode. For instance, this should be too long

  +        - ``algorithm`` -- string (default: ``'tedder'``); specifies the algorithm to
  +          use among:
  

• indentation

  -          4
  -         5
  +          4
  +          5
  

• avoid calls to .vertices() whenever possible (i.e., when it is not required to sort the vertices)

  -            for v in g.vertices():
  -                if v not in module:
  +            for v in g:
  +                if v not in module:
  

• Method md_tree_to_graph could made more visible (could be useful not only for testing) and possibly renamed something like modular_decomposition_tree_to_graph.

In a future ticket, we could create a class ModularDecomposition that computes de decomposition and provides access to various format of the result (tree, LabelledRootedTree, nested tuples, etc.) and ease access to methods like md_tree_to_graph.

[mantepse]

Here is a translation routine:

def to_labelled_rooted_tree(m):
    if m.node_type.name == "NORMAL":
        return LabelledRootedTree([], label=m.children[0])
    else:
        return LabelledRootedTree(map(to_labelled_rooted_tree, m.children),
                                  label=m.node_type)

A comment: I think it is quite unusual in sage to have properties (as opposed to methods that only take self as argument). They may be practical here, but are probably confusing for users.

[tscrim]

Replying to mantepse:

• it would be more emacs-friendly to use

              sage: from sage.graphs.graph_decompositions.modular_decomposition \
              ....:      import NodeType
  

instead of

            sage: from sage.graphs.graph_decompositions.modular_decomposition \
                       import NodeType

The former is how it would appear as actual Sage input, so IMO that would be the preferable thing to have.

[mantepse]

I stumbled over a strange problem:

sage: from sage.graphs.graph_decompositions.modular_decomposition import NodeType
sage: LabelledRootedTree([LabelledRootedTree([], label=NodeType(1)), LabelledRootedTree([], label=NodeType(2))])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-341-93c36028eb0d> in <module>()
----> 1 LabelledRootedTree([LabelledRootedTree([], label=NodeType(Integer(1))), LabelledRootedTree([], label=NodeType(Integer(2)))])

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1700)()
    328         """
    329         if cls.classcall is not None:
--> 330             return cls.classcall(cls, *args, **kwds)
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/combinat/rooted_tree.pyc in __classcall_private__(cls, *args, **opts)
    866             <class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'>
    867         """
--> 868         return cls._auto_parent.element_class(cls._auto_parent, *args, **opts)
    869 
    870     @lazy_class_attribute

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1725)()
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)
--> 333             return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    334 
    335     def __get__(cls, instance, owner):

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/combinat/abstract_tree.pyc in __init__(self, parent, children, label, check)
   2091         else:
   2092             self._label = label
-> 2093         super(AbstractLabelledTree, self).__init__(parent, children, check=check)
   2094 
   2095     def _repr_(self):

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/combinat/rooted_tree.pyc in __init__(self, parent, children, check)
    197         #        and children.parent() == parent):
    198         children = [self.__class__(parent, x) for x in children]
--> 199         NormalizedClonableList.__init__(self, parent, children, check=check)
    200 
    201     def sort_key(self):

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/structure/list_clone.pyx in sage.structure.list_clone.NormalizedClonableList.__init__ (build/cythonized/sage/structure/list_clone.c:12917)()
   1815         """
   1816         ClonableList.__init__(self, parent, lst, False, False)
-> 1817         self.normalize()
   1818         self._is_immutable = immutable
   1819         if check:

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/structure/list_clone.pyx in sage.structure.list_clone.NormalizedClonableList.normalize (build/cythonized/sage/structure/list_clone.c:13217)()
   1837         return ClonableList.__exit__(self, typ, value, tracback)
   1838 
-> 1839     cpdef normalize(self):
   1840         """
   1841         Normalize ``self``

/home/martin/sage-develop/local/lib/python2.7/site-packages/sage/combinat/rooted_tree.pyc in normalize(self)
    299         for st in self:
    300             assert st.is_immutable(), "Subtree {} is not normalized".format(st)
--> 301         self._get_list().sort(key=lambda t: t.sort_key())
    302         # ensure unique representation
    303         self.set_immutable()

/home/martin/sage-develop/local/lib/python2.7/site-packages/enum/__init__.pyc in __lt__(self, other)
    728 
    729     def __lt__(self, other):
--> 730         raise TypeError("unorderable types: %s() < %s()" % (self.__class__.__name__, other.__class__.__name__))
    731     temp_enum_dict['__lt__'] = __lt__
    732     del __lt__

TypeError: unorderable types: NodeType() < NodeType()

[mantepse]

Another tiny comment: lines 425--447 are duplicate.

[mantepse]

Yet another question: there are three graphs on six vertices where habib_maurer and modular_decomposition yield different results:

sage: def to_labelled_rooted_tree(m):
....:    if m.node_type.name == "NORMAL":
....:        return LabelledRootedTree([], label=m.children[0])
....:    else:
....:        return LabelledRootedTree(map(to_labelled_rooted_tree, m.children), label=(m.node_type.value,))

sage: view([(G, to_labelled_rooted_tree(modular_decomposition(G)), to_labelled_rooted_tree(habib_maurer_algorithm(G))) for G in graphs(6) if to_labelled_rooted_tree(modular_decomposition(G)) != to_labelled_rooted_tree(habib_maurer_algorithm(G))])

I am guessing that Habib-Maurer is more reliable, right? If so, maybe it would make sense to indicate this problem in modular_decomposition?

[mantepse]

I feel stupid now. Please excuse, I just discovered G.modular_decomposition...

[deinst]

Ok, I'll fix the cosmetic bugs later tonight.

I am loath to make a sweeping change to the return type until I figure out all the places that modular decomposition is used. I agree that the rooted tree is a more sensible return type than the nested tuples, but changing the return type will break things in Poset, and possibly other places. I would be more than willing to do the work, but I think that it should be in another ticket.

The habib-maurer algorithm should be more reliable, the algorithm is much simpler (albeit theoretically slower) than the other algorithm. It is also much more heavily tested.

[mantepse]

Wonderful!

However, I think it would be important to make it the default in graph.py, since the current version is definitively wrong for graphs of size 6.

[mantepse]

PS: I retract my comment about properties vs. methods. I think it is more efficient to change the return type in a later ticket, and then the properties aren't user-visible anymore anyway.

[mantepse]

One more superficiality: I believe that __str__ defaults to using __repr__, so the code in class NodeType and in class Node can be simplified.

[mantepse]

Replying to deinst:

I am loath to make a sweeping change to the return type until I figure out all the places that modular decomposition is used. I agree that the rooted tree is a more sensible return type than the nested tuples, but changing the return type will break things in Poset, and possibly other places. I would be more than willing to do the work, but I think that it should be in another ticket.

I just checked by printing a warning in sage.graphs.graph_decompositions.modular_decomposition.modular_decomposition and .habib_maurer, and running all doctests (with --long): at least in current develop modular_decomposition is only called in sage.graphs.graph.Graph.is_prime and sage.graphs.graph.Graph.modular_decomposition.

So there shouldn't be any problem, but I agree that it's better to do that in a separate ticket.

[dcoudert]

May be you can already open a ticket with a todo list ? We also have to fix #25872...

[mantepse]

I'm on it - I actually prepared a patch. Should the default be 'habib' or 'tedder'? Unfortunately, the ordering of the output changed?

[dcoudert]

as long as #25872 is not fixed, 'habib' seems a better choice...

Can e do something for the ordering of the output ? may be just change doctest to be more robust (independent of ordering) ?

[mantepse]

A simple way would be to use explicitely algorithm='tedder' in the doctest.

[mantepse]

The output style issue is #27247.

I also added the ....: stuff there.

[mantepse]

There is something very strange:

both modular_decomposition and habib_maurer return NORMAL [0] for the graph with one vertex, but this is manually changed to PRIME in the method. Why so? A similar thing is done to the empty graph.

[deinst]

In response to comment 44: The normal nodes are leaf nodes, and the graph with one node should return one prime node with one leaf as a child, as a graph with one node is indecomposible. This is much like the discussions about whether 1 is prime in Z. I just made habib-maurer mimic the extant behavior. When I started, I expected bug #25872 to eventually be fixed, so made as little change as possible to the existing interface.

In response to comment 27: The strange indentation is intentional, the indentation represents the depth of the leaf in the tree. Again, this was not my choice for the way of representing the tree.

[git]

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

​c0ca87b	Cosmetic changes
​063c0d8	Removed redundant __str__ and made habib the default method.

[mantepse]

I am sorry, I made a mistake in comment:37 concerning __str__ in __repr__. See #27247 for a more correct fix, also for the ordering problem.

[dcoudert]

Replying to mantepse:

I am sorry, I made a mistake in comment:37 concerning __str__ in __repr__. See #27247 for a more correct fix, also for the ordering problem.

So we should revert changes about __str__ and __repr__, right ?

[mantepse]

Replying to dcoudert:

Replying to mantepse:

I am sorry, I made a mistake in comment:37 concerning __str__ in __repr__. See #27247 for a more correct fix, also for the ordering problem.

So we should revert changes about __str__ and __repr__, right ?

I did

    __str__ = __repr__

(and please excuse me, I wanted to write 'possibly more correct', because I don't know much about python)

For the ordering problem, I think it's best to specify the algorithm explicitely in the doctests:

sage: graphs.PetersenGraph().modular_decomposition(algorithm='tedder')

or alternatively

sage: graphs.PetersenGraph().modular_decomposition(algorithm='habib')

and additionally adapt the result.

[embray]

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[dcoudert]

For the ordering problem, I think it's best to specify the algorithm explicitely in the doctests:

sage: graphs.PetersenGraph().modular_decomposition(algorithm='tedder')

or alternatively

sage: graphs.PetersenGraph().modular_decomposition(algorithm='habib')

and additionally adapt the result.

Sorry, I forgot to answer and lost track of the discussion.... I agree with your proposal.

[dcoudert]

I rebased the branch on 8.8.beta3, fixed merge conflicts, and fixed a few issues for Python3. The new branch is in public/, so you can modify it.

---

New commits:

​19517b1	trac #26496: fix merge conflict with 8.8.beta3
​a956126	trac #26496: some changes for py3

[dcoudert]

We have some failing doctests in graph.py both with Python2 and 3 that I have not fixed. It's due to the order of vertices in each module. We should find a solution to have better doctests here without introducing sorting inside the methods.

In modular_decomposition.py, I marked 1 doctest as # py2. Same issue.

[git]

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

​9244f20	trac #26496: merged with 8.8.beta5
​577fe61	trac #26496: review comments

[git]

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

​bef8d18

trac #26496: fix py2 doctest

[dcoudert]

I corrected the doctests for Python 2 and Python 3. I'm not happy with the solution (mark doctests as py2 or py3), but I don't have a better one.

For me this patch is good to go. With it, we will get a correct algorithm. Further improvements can be done in other tickets.

Can you double check that everything is ok for you so that I can finalize the review ?

[embray]

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[git]

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

​bbe7694	trac #26496: Merged with 8.9.beta1
​cc32a97	trac #26496: add modular decomposition module to graphs/index.rst

[dcoudert]

This way it will be more visible in the documentation.

Is it OK for you ? if so, you can set this ticket to positive review on my behalf. Thanks.

[git]

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

​8d3698f	trac #26496: Merged with 8.9.beta7
​81a4629	trac #26496: fix some issues in the documentation

[dcoudert]

I fixed some issues. Now the html documentation should build properly. More can certainly be done in another ticket...

[chapoton]

red branch

[git]

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

​f577d00

trac #26496: fix merge conflict with 8.9.rc0

[dcoudert]

fixed.

[dcoudert]

now its green ;)

[chapoton]

please do not use \ to break long lines in doctests, but ....:

EDIT: or do not wrap them if this does not work (for import lines)

[git]

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

​b6ffd63	trac #26496: avoid using \
​71b7e42	trac #26496: some pep8 cleaning
​c910704	trac #26496: more cleaning

[dcoudert]

I used some from ... import * instead of a long list of imports. I also tried to improve parts of the code / comments. More can certainly be done.

[chapoton]

I've just launched my bot on it.

[chapoton]

ok, let us say "good to go"

[dcoudert]

Thanks.

[chapoton]

moving milestone to 9.0 (after release of 8.9)