Opened 3 years ago
Closed 2 years ago
#27247 closed enhancement (fixed)
modular_decomposition should be able to return a tree
Reported by: | mantepse | Owned by: | deinst |
---|---|---|---|
Priority: | major | Milestone: | sage-9.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 3 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 3 years ago by
- Branch set to u/mantepse/modular_decomposition_should_be_able_to_return_a_tree
comment:3 Changed 3 years ago by
- Commit set to 9e82fd6101e8f3d59cbd76725e756d63377512ab
- Status changed from new to needs_review
comment:4 Changed 3 years ago by
- Dependencies set to #26496
comment:5 Changed 3 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 follow-up: ↓ 8 Changed 3 years ago by
comment:7 Changed 3 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 ; follow-up: ↓ 9 Changed 3 years ago by
comment:9 in reply to: ↑ 8 Changed 3 years ago by
comment:10 Changed 3 years ago by
- 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:11 Changed 3 years ago by
- 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:12 follow-up: ↓ 14 Changed 3 years ago by
- Milestone changed from sage-8.9 to sage-9.0
- Status changed from needs_review to needs_work
Now that #26496 is merge, we can restart working on this ticket
comment:13 Changed 2 years ago by
- Milestone changed from sage-9.0 to sage-9.1
comment:14 in reply to: ↑ 12 Changed 2 years ago by
Replying to dcoudert:
Now that #26496 is merge, we can restart working on this ticket
We can proceed by adding below code-block in graph.py
as introduced in commit 9e82fd6 and modify documentation and doc-test 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 2 years ago by
- Status changed from needs_work to needs_info
comment:16 Changed 2 years ago by
- Cc dcoudert added
comment:17 Changed 2 years 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 2 years ago by
Please go ahead! I have currently no time to work on this.
comment:19 Changed 2 years ago by
- Branch changed from u/mantepse/modular_decomposition_should_be_able_to_return_a_tree to u/gh-vipul79321/ticket27247
- Commit changed from 9e82fd6101e8f3d59cbd76725e756d63377512ab to d8e69ce14d69b87cc706e0117a4a70168aff445c
New commits:
d8e69ce | Style=tree added and doc updated
|
comment:20 Changed 2 years ago by
- Status changed from needs_info to needs_review
comment:21 follow-up: ↓ 23 Changed 2 years 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 follow-up: ↓ 24 Changed 2 years 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 2 years 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 2 years ago by
comment:25 follow-up: ↓ 27 Changed 2 years 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 2 years 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 2 years 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 2 years 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 2 years 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/gh-vipul79321/ticket27247' of git://trac.sagemath.org/sage into u/gh-vipul79321/ticket27247
|
comment:30 Changed 2 years ago by
- Reviewers set to David Coudert
LGTM. Please add your name in authors field (in addition to the name of Martin).
comment:31 follow-up: ↓ 32 Changed 2 years 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 2 years ago by
Replying to gh-vipul79321:
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 2 years ago by
- Branch changed from u/gh-vipul79321/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