Opened 2 years ago
Closed 16 months ago
#27247 closed enhancement (fixed)
modular_decomposition should be able to return a tree
Reported by:  mantepse  Owned by:  deinst 

Priority:  major  Milestone:  sage9.1 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Martin Rubey, Vipul Gupta  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  b5f1884 (Commits, GitHub, GitLab)  Commit:  b5f18845ee0076863e64b12bc9a4961285bbcefe 
Dependencies:  #26496  Stopgaps: 
Description (last modified by )
Change return type to rooted labeled tree.
Change History (34)
comment:1 Changed 2 years ago by
 Component changed from PLEASE CHANGE to graph theory
 Description modified (diff)
 Owner changed from (none) to deinst
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 2 years ago by
 Branch set to u/mantepse/modular_decomposition_should_be_able_to_return_a_tree
comment:3 Changed 2 years ago by
 Commit set to 9e82fd6101e8f3d59cbd76725e756d63377512ab
 Status changed from new to needs_review
comment:4 Changed 2 years ago by
 Dependencies set to #26496
comment:5 Changed 2 years ago by
I'm a bit lost here. What's the part you added ?
At least, the ascii_art tree is really nice ;)
comment:6 followup: ↓ 8 Changed 2 years ago by
comment:7 Changed 2 years ago by
Thanks for the compliment! The style='tree'
is also useful, because you can, for example, easily collect graphs by equivalent modular decomposition:
def doit(n): from collections import defaultdict d = defaultdict(list) for g in graphs(n): m = g.modular_decomposition(algorithm='habib', style='tree') m = m.map_labels(lambda x: None if x in ZZ else x) d[m].append(g.canonical_label()) return dict(d)
and then
sage: view(doit(5).items())
comment:8 in reply to: ↑ 6 ; followup: ↓ 9 Changed 2 years ago by
comment:9 in reply to: ↑ 8 Changed 2 years ago by
comment:10 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:11 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:12 followup: ↓ 14 Changed 22 months ago by
 Milestone changed from sage8.9 to sage9.0
 Status changed from needs_review to needs_work
Now that #26496 is merge, we can restart working on this ticket
comment:13 Changed 19 months ago by
 Milestone changed from sage9.0 to sage9.1
comment:14 in reply to: ↑ 12 Changed 16 months ago by
Replying to dcoudert:
Now that #26496 is merge, we can restart working on this ticket
We can proceed by adding below codeblock in graph.py
as introduced in commit 9e82fd6 and modify documentation and doctest accordingly.
self._scream_if_not_simple() if not self.order(): D = None elif self.order() == 1: D = create_prime_node() D.children.append(create_normal_node(self.vertices()[0])) else: if algorithm == 'habib': D = habib_maurer_algorithm(self) elif algorithm == 'tedder': D = modular_decomposition(self) else: raise ValueError("unknown algorithm: %s" % algorithm) if style == 'tuple': if D is None: return tuple() relabel = lambda x: ((x.node_type, map(relabel, x.children)) if x.node_type != NodeType.NORMAL else x.children[0]) return relabel(D) elif style == 'tree': from sage.combinat.rooted_tree import LabelledRootedTree if D is None: return LabelledRootedTree([]) to_tree = lambda x: (LabelledRootedTree(map(to_tree, x.children), label=x.node_type) if x.node_type != NodeType.NORMAL else LabelledRootedTree([], label=x.children[0]))+ return to_tree(D) else: raise ValueError("unknown style: %s" % style)
If Nobody is working on it currently, Can I proceed to implement proposed changes?
comment:15 Changed 16 months ago by
 Status changed from needs_work to needs_info
comment:16 Changed 16 months ago by
 Cc dcoudert added
comment:17 Changed 16 months ago by
I don't know if the original author is willing to finalize this ticket or not. Let him some time to answer.
comment:18 Changed 16 months ago by
Please go ahead! I have currently no time to work on this.
comment:19 Changed 16 months ago by
 Branch changed from u/mantepse/modular_decomposition_should_be_able_to_return_a_tree to u/ghvipul79321/ticket27247
 Commit changed from 9e82fd6101e8f3d59cbd76725e756d63377512ab to d8e69ce14d69b87cc706e0117a4a70168aff445c
New commits:
d8e69ce  Style=tree added and doc updated

comment:20 Changed 16 months ago by
 Status changed from needs_info to needs_review
comment:21 followup: ↓ 23 Changed 16 months ago by
 I think format is more appropriate than form
  ``style``  string (default: ``'tuple'``); specifies the output form: +  ``style``  string (default: ``'tuple'``); specifies the output format:
 a minor correction
+  ``'tree'``  as `LabelledRootedTree`. +  ``'tree'``  as :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`.
comment:22 followup: ↓ 24 Changed 16 months ago by
 Commit changed from d8e69ce14d69b87cc706e0117a4a70168aff445c to 428c0bf3e684d7fa332a49ca6d05741d114fb382
Branch pushed to git repo; I updated commit sha1. New commits:
428c0bf  documentation fixed

comment:23 in reply to: ↑ 21 Changed 16 months ago by
Replying to dcoudert:
 I think format is more appropriate than form
  ``style``  string (default: ``'tuple'``); specifies the output form: +  ``style``  string (default: ``'tuple'``); specifies the output format:
Ok.
 a minor correction
+  ``'tree'``  as `LabelledRootedTree`. +  ``'tree'``  as :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`.
Instead of this, I think this would be better
  ``'tree'``  as `LabelledRootedTree`. +  ``'tree'``  as :class:`~sage.combinat.rooted_tree.LabelledRootedTree`.
comment:24 in reply to: ↑ 22 Changed 16 months ago by
comment:25 followup: ↓ 27 Changed 16 months ago by
Right, but you should change accordingly the part
+ We can choose output to be a + :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`::
comment:26 Changed 16 months ago by
 Commit changed from 428c0bf3e684d7fa332a49ca6d05741d114fb382 to 3ecdc645fff4999ff67891ef0ade56f2800577ac
Branch pushed to git repo; I updated commit sha1. New commits:
3ecdc64  fixed silly mistake

comment:27 in reply to: ↑ 25 Changed 16 months ago by
Replying to dcoudert:
Right, but you should change accordingly the part
+ We can choose output to be a + :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`::
sorry, my bad. How could I have missed it :(
I have updated it now
comment:28 Changed 16 months ago by
Sorry I forgot this one: add an empty line after Singleton Vertex::
.
And this could be nicer (to avoid \ )
 from sage.graphs.graph_decompositions.modular_decomposition import modular_decomposition,\  NodeType, habib_maurer_algorithm, create_prime_node, create_normal_node + from sage.graphs.graph_decompositions.modular_decomposition import (modular_decomposition, + NodeType, + habib_maurer_algorithm, + create_prime_node, + create_normal_node)
Also, the patchbot reports an issue, but I'm not sure what it is. Can you investigate?
comment:29 Changed 16 months ago by
 Commit changed from 3ecdc645fff4999ff67891ef0ade56f2800577ac to b5f18845ee0076863e64b12bc9a4961285bbcefe
Branch pushed to git repo; I updated commit sha1. New commits:
83ac09b  Style=tree added and doc updated

f03b2a6  documentation fixed

00a86d4  fixed silly mistake

27a1a8b  Rebased and updated according to comment 28

b5f1884  Merge branch 'u/ghvipul79321/ticket27247' of git://trac.sagemath.org/sage into u/ghvipul79321/ticket27247

comment:30 Changed 16 months ago by
 Reviewers set to David Coudert
LGTM. Please add your name in authors field (in addition to the name of Martin).
comment:31 followup: ↓ 32 Changed 16 months ago by
I have one more doubt, how do we decide our branch passes patchbot tests, like on some systems it shows all tests passes
but on some system build failed
(current scenario).
comment:32 in reply to: ↑ 31 Changed 16 months ago by
Replying to ghvipul79321:
I have one more doubt, how do we decide our branch passes patchbot tests, like on some systems it shows
all tests passes
but on some systembuild failed
(current scenario).
Check on the logs if a failure is related to the ticket.Here it is clearly not the case.
comment:34 Changed 16 months ago by
 Branch changed from u/ghvipul79321/ticket27247 to b5f18845ee0076863e64b12bc9a4961285bbcefe
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Implemented suggested changes
Added missing doctests.
Small doc fixes.
Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
Fixed doctests for __str__ and __repr__
Improved formatting of documentation
Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
fixed stupid errors
Merge branch 'u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs' of git://trac.sagemath.org/sage into t/27247/modular_decomposition_should_be_able_to_return_a_tree
add possibility to return a tree