Opened 3 years ago
Closed 2 years ago
#26496 closed enhancement (fixed)
Add the Habib Maurer algorithm for modular decomposition to graphs
Reported by:  deinst  Owned by:  

Priority:  major  Milestone:  sage9.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, GitHub, GitLab)  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(n^{3})algorithm from Habib and Maurer "On the XJoin 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 3 years ago by
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 3 years ago by
 Branch set to u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
comment:3 Changed 3 years ago by
 Commit set to 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6
comment:4 Changed 3 years ago by
 Commit changed from 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6 to d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a
Branch pushed to git repo; I updated commit sha1. New commits:
d00dcbe  Added some randomized tests.

comment:5 Changed 3 years ago by
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 avoide = 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 unionfind (DisjointSet
) ? If I understand well, you merge groups of edges, right ?  what is
either_connected_or_not_connected
?
comment:6 Changed 3 years ago by
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 3 years ago by
 Commit changed from d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a to a81f2d2b91681e27903a0f227c2266134c52ed86
Branch pushed to git repo; I updated commit sha1. New commits:
a81f2d2  Added code for random test of modular decomposition from reconstruction

comment:8 Changed 3 years ago by
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 3 years ago by
 Commit changed from a81f2d2b91681e27903a0f227c2266134c52ed86 to ff7c910999656cde73c173e6b79dfaf0d6811c79
comment:10 Changed 3 years ago by
 Status changed from new to needs_review
Most of the new code is to support the random tests.
comment:11 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:12 Changed 3 years ago by
 Commit changed from ff7c910999656cde73c173e6b79dfaf0d6811c79 to 65ed276dba24555f5418ac7f576aa93fedfe7732
Branch pushed to git repo; I updated commit sha1. New commits:
65ed276  Fixed errors the patchbot was complaining about

comment:13 Changed 3 years ago by
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 3 years ago by
 Commit changed from 65ed276dba24555f5418ac7f576aa93fedfe7732 to 8ba0fc62d7736d87796dfe6b22fd333d4934a091
Branch pushed to git repo; I updated commit sha1. New commits:
8ba0fc6  Implemented suggested changes

comment:15 Changed 3 years ago by
 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 nonascii 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 3 years ago by
 Commit changed from 8ba0fc62d7736d87796dfe6b22fd333d4934a091 to 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84
Branch pushed to git repo; I updated commit sha1. New commits:
0a06a7b  Added missing doctests.

comment:17 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
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; worstcase 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 3 years ago by
You should rebuild on last beta and resolve merge conflicts.
comment:21 Changed 3 years ago by
 Commit changed from 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84 to a86307a50c42a2a334fb89b4b26ed09dcf3960bb
comment:22 Changed 3 years ago by
 Milestone changed from sage8.4 to sage8.5
 Reviewers set to David Coudert
Some more comments, mostly cosmetic.
 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:
 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 4cycles 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 3 years ago by
 Commit changed from a86307a50c42a2a334fb89b4b26ed09dcf3960bb to 161e1d64765a9537b68454355711ff3c4f28db44
comment:24 Changed 3 years ago by
 Commit changed from 161e1d64765a9537b68454355711ff3c4f28db44 to cd41b57f8c03cfcc4ec6da5abd9b2609d487714b
Branch pushed to git repo; I updated commit sha1. New commits:
cd41b57  fixed stupid errors

comment:25 followup: ↓ 29 Changed 3 years ago by
two superficial questions:
 would it be sensible / feasable / outside the scope of this ticket to make
modular_decomposition
actually return aLabelledRootedTree
?
 it would be more emacsfriendly 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 3 years ago by
It is certainly possible to add a parameter to choose the output format.
comment:27 Changed 3 years ago by
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 likemodular_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 3 years ago by
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 3 years ago by
Replying to mantepse:
 it would be more emacsfriendly to use
sage: from sage.graphs.graph_decompositions.modular_decomposition \ ....: import NodeTypeinstead 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 3 years ago by
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) <ipythoninput34193c36028eb0d> in <module>() > 1 LabelledRootedTree([LabelledRootedTree([], label=NodeType(Integer(1))), LabelledRootedTree([], label=NodeType(Integer(2)))]) /home/martin/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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 3 years ago by
Another tiny comment: lines 425447 are duplicate.
comment:32 Changed 3 years ago by
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 HabibMaurer is more reliable, right? If so, maybe it would make sense to indicate this problem in modular_decomposition
?
comment:33 Changed 3 years ago by
I feel stupid now. Please excuse, I just discovered G.modular_decomposition
...
comment:34 followup: ↓ 38 Changed 3 years ago by
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 habibmaurer 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 3 years ago by
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 3 years ago by
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 uservisible anymore anyway.
comment:37 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
May be you can already open a ticket with a todo list ? We also have to fix #25872...
comment:40 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
A simple way would be to use explicitely algorithm='tedder'
in the doctest.
comment:43 Changed 3 years ago by
The output style issue is #27247.
I also added the ....:
stuff there.
comment:44 Changed 3 years ago by
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 3 years ago by
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 habibmaurer 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 3 years ago by
 Commit changed from cd41b57f8c03cfcc4ec6da5abd9b2609d487714b to 063c0d82bde748cb642b28db978ef0c913ae25b1
comment:47 followup: ↓ 48 Changed 3 years ago by
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 ; followup: ↓ 49 Changed 3 years ago by
 Milestone changed from sage8.5 to sage8.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 ; followup: ↓ 51 Changed 3 years ago by
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 2 years ago by
 Milestone changed from sage8.7 to sage8.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 2 years ago by
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 2 years ago by
 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
comment:53 Changed 2 years ago by
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 2 years ago by
 Commit changed from a9561267083c46a953d7707c38203f3e1afd39b9 to 577fe61d2d3938d8bb5c204b334663bc84886766
comment:55 Changed 2 years ago by
 Commit changed from 577fe61d2d3938d8bb5c204b334663bc84886766 to bef8d183f25369cc4572c67a2d1973e35c9f3339
Branch pushed to git repo; I updated commit sha1. New commits:
bef8d18  trac #26496: fix py2 doctest

comment:56 Changed 2 years ago by
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 2 years ago by
 Milestone changed from sage8.8 to sage8.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 2 years ago by
 Commit changed from bef8d183f25369cc4572c67a2d1973e35c9f3339 to cc32a970a1725a00afb37e1c0cb33c859709fd3b
comment:59 Changed 2 years ago by
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 2 years ago by
 Commit changed from cc32a970a1725a00afb37e1c0cb33c859709fd3b to 81a46297691c08441f391a76ddad704fa7877258
comment:61 Changed 2 years ago by
I fixed some issues. Now the html documentation should build properly. More can certainly be done in another ticket...
comment:63 Changed 2 years ago by
 Commit changed from 81a46297691c08441f391a76ddad704fa7877258 to f577d00cddf4c77f6f392749bddb7913490ee27b
Branch pushed to git repo; I updated commit sha1. New commits:
f577d00  trac #26496: fix merge conflict with 8.9.rc0

comment:65 Changed 2 years ago by
now its green ;)
comment:66 Changed 2 years ago by
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)
comment:67 Changed 2 years ago by
 Commit changed from f577d00cddf4c77f6f392749bddb7913490ee27b to c910704f123d90cefa2e8a2b54375f98806825b3
comment:68 Changed 2 years ago by
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 2 years ago by
I've just launched my bot on it.
comment:70 Changed 2 years ago by
 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 2 years ago by
Thanks.
comment:72 Changed 2 years ago by
 Milestone changed from sage8.9 to sage9.0
moving milestone to 9.0 (after release of 8.9)
comment:73 Changed 2 years ago by
 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
The code should now be functional. I need to fix up the documentation and add a bunch of tests.
New commits:
Moved modular_decomposition.
Fix is_prime
Added HabibMaurer algorithm to Graph.modular_decomposition