Opened 4 years ago
Closed 3 years 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, 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(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 4 years ago by
Type: | PLEASE CHANGE → enhancement |
---|
comment:2 Changed 4 years ago by
Branch: | → u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs |
---|
comment:3 Changed 4 years ago by
Commit: | → 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6 |
---|
comment:4 Changed 4 years ago by
Commit: | 8e57c73f52acf9a56ef484b88ddd87bf1b2550e6 → d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
d00dcbe | Added some randomized tests.
|
comment:5 Changed 4 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 union-find (DisjointSet
) ? If I understand well, you merge groups of edges, right ? - what is
either_connected_or_not_connected
?
comment:6 Changed 4 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 4 years ago by
Commit: | d00dcbe3e86a6fd3a2332e6599b542cb89c6fa3a → 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 4 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 4 years ago by
Commit: | a81f2d2b91681e27903a0f227c2266134c52ed86 → ff7c910999656cde73c173e6b79dfaf0d6811c79 |
---|
comment:10 Changed 4 years ago by
Status: | new → needs_review |
---|
Most of the new code is to support the random tests.
comment:11 Changed 4 years ago by
Status: | needs_review → needs_work |
---|
comment:12 Changed 4 years ago by
Commit: | ff7c910999656cde73c173e6b79dfaf0d6811c79 → 65ed276dba24555f5418ac7f576aa93fedfe7732 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
65ed276 | Fixed errors the patchbot was complaining about
|
comment:13 Changed 4 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 4 years ago by
Commit: | 65ed276dba24555f5418ac7f576aa93fedfe7732 → 8ba0fc62d7736d87796dfe6b22fd333d4934a091 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
8ba0fc6 | Implemented suggested changes
|
comment:15 Changed 4 years ago by
Status: | needs_work → 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 4 years ago by
Commit: | 8ba0fc62d7736d87796dfe6b22fd333d4934a091 → 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
0a06a7b | Added missing doctests.
|
comment:17 Changed 4 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 4 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 4 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; 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:21 Changed 4 years ago by
Commit: | 0a06a7bd59e2bd607dc1f26de6d5588fb70e0e84 → a86307a50c42a2a334fb89b4b26ed09dcf3960bb |
---|
comment:22 Changed 4 years ago by
Milestone: | sage-8.4 → sage-8.5 |
---|---|
Reviewers: | → 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 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 4 years ago by
Commit: | a86307a50c42a2a334fb89b4b26ed09dcf3960bb → 161e1d64765a9537b68454355711ff3c4f28db44 |
---|
comment:24 Changed 4 years ago by
Commit: | 161e1d64765a9537b68454355711ff3c4f28db44 → cd41b57f8c03cfcc4ec6da5abd9b2609d487714b |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
cd41b57 | fixed stupid errors
|
comment:25 follow-up: 29 Changed 4 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 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 4 years ago by
It is certainly possible to add a parameter to choose the output format.
comment:27 Changed 4 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 4 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 Changed 4 years ago by
Replying to mantepse:
- it would be more emacs-friendly 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 4 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) <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:32 Changed 4 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 Habib-Maurer is more reliable, right? If so, maybe it would make sense to indicate this problem in modular_decomposition
?
comment:33 Changed 4 years ago by
I feel stupid now. Please excuse, I just discovered G.modular_decomposition
...
comment:34 follow-up: 38 Changed 4 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 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 4 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 4 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 user-visible anymore anyway.
comment:37 Changed 4 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 Changed 4 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 4 years ago by
May be you can already open a ticket with a todo list ? We also have to fix #25872...
comment:40 Changed 4 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 4 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 4 years ago by
A simple way would be to use explicitely algorithm='tedder'
in the doctest.
comment:43 Changed 4 years ago by
The output style issue is #27247.
I also added the ....:
stuff there.
comment:44 Changed 4 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 4 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 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 4 years ago by
Commit: | cd41b57f8c03cfcc4ec6da5abd9b2609d487714b → 063c0d82bde748cb642b28db978ef0c913ae25b1 |
---|
comment:47 follow-up: 48 Changed 4 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 follow-up: 49 Changed 4 years ago by
Milestone: | sage-8.5 → 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 follow-up: 51 Changed 4 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 4 years ago by
Milestone: | sage-8.7 → 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 Changed 4 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 4 years ago by
Branch: | u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs → public/graphs/26496_habib_maurer_algorithm_for_modular_decomposition |
---|---|
Commit: | 063c0d82bde748cb642b28db978ef0c913ae25b1 → a9561267083c46a953d7707c38203f3e1afd39b9 |
comment:53 Changed 4 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 4 years ago by
Commit: | a9561267083c46a953d7707c38203f3e1afd39b9 → 577fe61d2d3938d8bb5c204b334663bc84886766 |
---|
comment:55 Changed 4 years ago by
Commit: | 577fe61d2d3938d8bb5c204b334663bc84886766 → bef8d183f25369cc4572c67a2d1973e35c9f3339 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
bef8d18 | trac #26496: fix py2 doctest
|
comment:56 Changed 4 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 4 years ago by
Milestone: | sage-8.8 → 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 4 years ago by
Commit: | bef8d183f25369cc4572c67a2d1973e35c9f3339 → cc32a970a1725a00afb37e1c0cb33c859709fd3b |
---|
comment:59 Changed 4 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 3 years ago by
Commit: | cc32a970a1725a00afb37e1c0cb33c859709fd3b → 81a46297691c08441f391a76ddad704fa7877258 |
---|
comment:61 Changed 3 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 3 years ago by
Commit: | 81a46297691c08441f391a76ddad704fa7877258 → f577d00cddf4c77f6f392749bddb7913490ee27b |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
f577d00 | trac #26496: fix merge conflict with 8.9.rc0
|
comment:66 Changed 3 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 3 years ago by
Commit: | f577d00cddf4c77f6f392749bddb7913490ee27b → c910704f123d90cefa2e8a2b54375f98806825b3 |
---|
comment:68 Changed 3 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:70 Changed 3 years ago by
Reviewers: | David Coudert → David Coudert, Frédéric Chapoton |
---|---|
Status: | needs_review → positive_review |
ok, let us say "good to go"
comment:72 Changed 3 years ago by
Milestone: | sage-8.9 → sage-9.0 |
---|
moving milestone to 9.0 (after release of 8.9)
comment:73 Changed 3 years ago by
Branch: | public/graphs/26496_habib_maurer_algorithm_for_modular_decomposition → c910704f123d90cefa2e8a2b54375f98806825b3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → 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 Habib-Maurer algorithm to Graph.modular_decomposition