Opened 15 months ago

Closed 4 months ago

#26496 closed enhancement (fixed)

Add the Habib Maurer algorithm for modular decomposition to graphs

Reported by: deinst Owned by:
Priority: major Milestone: sage-9.0
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Einstein Reviewers: David Coudert, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: c910704 (Commits) Commit: c910704f123d90cefa2e8a2b54375f98806825b3
Dependencies: Stopgaps:

Description

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

Change History (73)

comment:1 Changed 15 months ago by deinst

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 15 months ago by deinst

  • Branch set to u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs

comment:3 Changed 15 months ago by deinst

  • Commit set to 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6

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


New commits:

534ba95Moved modular_decomposition.
6722b32Fix is_prime
8e57c73Added Habib-Maurer algorithm to Graph.modular_decomposition

comment:4 Changed 15 months ago by git

  • Commit changed from 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6 to d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a

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

d00dcbeAdded some randomized tests.

comment:5 Changed 15 months ago by 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 ?

comment:6 Changed 15 months ago by 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.

comment:7 Changed 15 months ago by git

  • Commit changed from d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a to a81f2d2b91681e27903a0f227c2266134c52ed86

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

a81f2d2Added code for random test of modular decomposition from reconstruction

comment:8 Changed 15 months ago by 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.

comment:9 Changed 15 months ago by git

  • Commit changed from a81f2d2b91681e27903a0f227c2266134c52ed86 to ff7c910999656cde73c173e6b79dfaf0d6811c79

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

314ada6Minor documentation changes.
abe1365Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
ff7c910Fixed up docstrings.

comment:10 Changed 15 months ago by deinst

  • Status changed from new to needs_review

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

comment:11 Changed 15 months ago by deinst

  • Status changed from needs_review to needs_work

comment:12 Changed 15 months ago by git

  • Commit changed from ff7c910999656cde73c173e6b79dfaf0d6811c79 to 65ed276dba24555f5418ac7f576aa93fedfe7732

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

65ed276Fixed errors the patchbot was complaining about

comment:13 Changed 15 months ago by 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)

comment:14 Changed 15 months ago by git

  • Commit changed from 65ed276dba24555f5418ac7f576aa93fedfe7732 to 8ba0fc62d7736d87796dfe6b22fd333d4934a091

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

8ba0fc6Implemented suggested changes

comment:15 Changed 15 months ago by deinst

  • Status changed from needs_work to needs_review

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?

comment:16 Changed 15 months ago by git

  • Commit changed from 8ba0fc62d7736d87796dfe6b22fd333d4934a091 to 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84

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

0a06a7bAdded missing doctests.

comment:17 Changed 15 months ago by 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?

comment:18 Changed 15 months ago by 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.

comment:19 Changed 15 months ago by 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)`

comment:20 Changed 14 months ago by dcoudert

You should rebuild on last beta and resolve merge conflicts.

comment:21 Changed 14 months ago by git

  • Commit changed from 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84 to a86307a50c42a2a334fb89b4b26ed09dcf3960bb

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

fc82c80Small doc fixes.
e00479eMerge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
a86307aFixed doctests for __str__ and __repr__

comment:22 Changed 14 months ago by dcoudert

  • Milestone changed from sage-8.4 to sage-8.5
  • Reviewers set to David Coudert

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

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

comment:23 Changed 13 months ago by git

  • Commit changed from a86307a50c42a2a334fb89b4b26ed09dcf3960bb to 161e1d64765a9537b68454355711ff3c4f28db44

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

225dfe0Improved formatting of documentation
161e1d6Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs

comment:24 Changed 13 months ago by git

  • Commit changed from 161e1d64765a9537b68454355711ff3c4f28db44 to cd41b57f8c03cfcc4ec6da5abd9b2609d487714b

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

cd41b57fixed stupid errors

comment:25 follow-up: Changed 12 months ago by 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

comment:26 Changed 12 months ago by dcoudert

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

comment:27 Changed 12 months ago by dcoudert

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

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

comment:28 Changed 12 months ago by 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.

comment:29 in reply to: ↑ 25 Changed 12 months ago by 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.

comment:30 Changed 12 months ago by 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()

comment:31 Changed 11 months ago by mantepse

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

comment:32 Changed 11 months ago by 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?

comment:33 Changed 11 months ago by mantepse

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

comment:34 follow-up: Changed 11 months ago by 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.

comment:35 Changed 11 months ago by 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.

comment:36 Changed 11 months ago by 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.

comment:37 Changed 11 months ago by 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.

comment:38 in reply to: ↑ 34 Changed 11 months ago by 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.

comment:39 Changed 11 months ago by dcoudert

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

comment:40 Changed 11 months ago by mantepse

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

comment:41 Changed 11 months ago by 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) ?

comment:42 Changed 11 months ago by mantepse

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

comment:43 Changed 11 months ago by mantepse

The output style issue is #27247.

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

comment:44 Changed 11 months ago by 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.

comment:45 Changed 11 months ago by 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.

comment:46 Changed 11 months ago by git

  • Commit changed from cd41b57f8c03cfcc4ec6da5abd9b2609d487714b to 063c0d82bde748cb642b28db978ef0c913ae25b1

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

c0ca87bCosmetic changes
063c0d8Removed redundant __str__ and made habib the default method.

comment:47 follow-up: Changed 11 months ago by 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.

comment:48 in reply to: ↑ 47 ; follow-up: Changed 11 months ago by dcoudert

  • Milestone changed from sage-8.5 to sage-8.7

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 ?

comment:49 in reply to: ↑ 48 ; follow-up: Changed 11 months ago by 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.

comment:50 Changed 10 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

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

comment:51 in reply to: ↑ 49 Changed 10 months ago by 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.

comment:52 Changed 9 months ago by dcoudert

  • Branch changed from u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs to public/graphs/26496_habib_maurer_algorithm_for_modular_decomposition
  • Commit changed from 063c0d82bde748cb642b28db978ef0c913ae25b1 to a9561267083c46a953d7707c38203f3e1afd39b9

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:

19517b1trac #26496: fix merge conflict with 8.8.beta3
a956126trac #26496: some changes for py3

comment:53 Changed 9 months ago by 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.

comment:54 Changed 8 months ago by git

  • Commit changed from a9561267083c46a953d7707c38203f3e1afd39b9 to 577fe61d2d3938d8bb5c204b334663bc84886766

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

9244f20trac #26496: merged with 8.8.beta5
577fe61trac #26496: review comments

comment:55 Changed 8 months ago by git

  • Commit changed from 577fe61d2d3938d8bb5c204b334663bc84886766 to bef8d183f25369cc4572c67a2d1973e35c9f3339

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

bef8d18trac #26496: fix py2 doctest

comment:56 Changed 8 months ago by 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 ?

comment:57 Changed 7 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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

comment:58 Changed 7 months ago by git

  • Commit changed from bef8d183f25369cc4572c67a2d1973e35c9f3339 to cc32a970a1725a00afb37e1c0cb33c859709fd3b

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

bbe7694trac #26496: Merged with 8.9.beta1
cc32a97trac #26496: add modular decomposition module to graphs/index.rst

comment:59 Changed 7 months ago by 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.

comment:60 Changed 5 months ago by git

  • Commit changed from cc32a970a1725a00afb37e1c0cb33c859709fd3b to 81a46297691c08441f391a76ddad704fa7877258

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

8d3698ftrac #26496: Merged with 8.9.beta7
81a4629trac #26496: fix some issues in the documentation

comment:61 Changed 5 months ago by dcoudert

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

comment:62 Changed 4 months ago by chapoton

  • Status changed from needs_review to needs_work

red branch

comment:63 Changed 4 months ago by git

  • Commit changed from 81a46297691c08441f391a76ddad704fa7877258 to f577d00cddf4c77f6f392749bddb7913490ee27b

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

f577d00trac #26496: fix merge conflict with 8.9.rc0

comment:64 Changed 4 months ago by dcoudert

  • Status changed from needs_work to needs_review

fixed.

comment:65 Changed 4 months ago by dcoudert

now its green ;)

comment:66 Changed 4 months ago by 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)

Last edited 4 months ago by chapoton (previous) (diff)

comment:67 Changed 4 months ago by git

  • Commit changed from f577d00cddf4c77f6f392749bddb7913490ee27b to c910704f123d90cefa2e8a2b54375f98806825b3

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

b6ffd63trac #26496: avoid using \
71b7e42trac #26496: some pep8 cleaning
c910704trac #26496: more cleaning

comment:68 Changed 4 months ago by 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.

comment:69 Changed 4 months ago by chapoton

I've just launched my bot on it.

comment:70 Changed 4 months ago by chapoton

  • Reviewers changed from David Coudert to David Coudert, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let us say "good to go"

comment:71 Changed 4 months ago by dcoudert

Thanks.

comment:72 Changed 4 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

moving milestone to 9.0 (after release of 8.9)

comment:73 Changed 4 months ago by vbraun

  • Branch changed from public/graphs/26496_habib_maurer_algorithm_for_modular_decomposition to c910704f123d90cefa2e8a2b54375f98806825b3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.