Opened 3 years ago

Closed 19 months 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:

Status badges

Description (last modified by deinst)

Change return type to rooted labeled tree.

Change History (34)

comment:1 Changed 3 years ago by deinst

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

  • Branch set to u/mantepse/modular_decomposition_should_be_able_to_return_a_tree

comment:3 Changed 3 years ago by mantepse

  • Authors set to Martin Rubey
  • Commit set to 9e82fd6101e8f3d59cbd76725e756d63377512ab
  • Status changed from new to needs_review

Last 10 new commits:

8ba0fc6Implemented suggested changes
0a06a7bAdded missing doctests.
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__
225dfe0Improved formatting of documentation
161e1d6Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
cd41b57fixed stupid errors
1f1b9dfMerge 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
9e82fd6add possibility to return a tree

comment:4 Changed 3 years ago by mantepse

  • Dependencies set to #26496

comment:5 Changed 3 years ago by dcoudert

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: Changed 3 years ago by mantepse

I added 9e82fd6, all the rest is the dependency on #26496.

comment:7 Changed 3 years ago by mantepse

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: Changed 3 years ago by dcoudert

Replying to mantepse:

I added 9e82fd6, all the rest is the dependency on #26496.

My concern is that I don't see the last commits of #26496 like c0ca87b.

comment:9 in reply to: ↑ 8 Changed 3 years ago by mantepse

Replying to dcoudert:

Replying to mantepse:

I added 9e82fd6, all the rest is the dependency on #26496.

My concern is that I don't see the last commits of #26496 like c0ca87b.

Yes, as far as I know, trac doesn't do this for us. In other words: first finish #26496, and wait until it is in the develop-branch.

comment:10 Changed 3 years 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:11 Changed 2 years 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:12 follow-up: Changed 2 years ago by dcoudert

  • 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 22 months ago by dcoudert

  • Milestone changed from sage-9.0 to sage-9.1

comment:14 in reply to: ↑ 12 Changed 19 months ago by gh-vipul79321

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 19 months ago by gh-vipul79321

  • Status changed from needs_work to needs_info

comment:16 Changed 19 months ago by gh-vipul79321

  • Cc dcoudert added

comment:17 Changed 19 months ago by dcoudert

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 19 months ago by mantepse

Please go ahead! I have currently no time to work on this.

comment:19 Changed 19 months ago by gh-vipul79321

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

d8e69ceStyle=tree added and doc updated

comment:20 Changed 19 months ago by gh-vipul79321

  • Status changed from needs_info to needs_review

comment:21 follow-up: Changed 19 months ago by 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:
    
  • a minor correction
    +          - ``'tree'`` -- as `LabelledRootedTree`.
    +          - ``'tree'`` -- as :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`.
    

comment:22 follow-up: Changed 19 months ago by git

  • Commit changed from d8e69ce14d69b87cc706e0117a4a70168aff445c to 428c0bf3e684d7fa332a49ca6d05741d114fb382

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

428c0bfdocumentation fixed

comment:23 in reply to: ↑ 21 Changed 19 months ago by gh-vipul79321

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 19 months ago by gh-vipul79321

Replying to git:

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

428c0bfdocumentation fixed

Updated according to comment 23

comment:25 follow-up: Changed 19 months ago by dcoudert

Right, but you should change accordingly the part

+        We can choose output to be a
+        :class:`<sage.combinat.rooted_tree.LabelledRootedTree>`::

comment:26 Changed 19 months ago by git

  • Commit changed from 428c0bf3e684d7fa332a49ca6d05741d114fb382 to 3ecdc645fff4999ff67891ef0ade56f2800577ac

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

3ecdc64fixed silly mistake

comment:27 in reply to: ↑ 25 Changed 19 months ago by gh-vipul79321

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 19 months ago by dcoudert

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 19 months ago by git

  • Commit changed from 3ecdc645fff4999ff67891ef0ade56f2800577ac to b5f18845ee0076863e64b12bc9a4961285bbcefe

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

83ac09bStyle=tree added and doc updated
f03b2a6documentation fixed
00a86d4fixed silly mistake
27a1a8bRebased and updated according to comment 28
b5f1884Merge branch 'u/gh-vipul79321/ticket27247' of git://trac.sagemath.org/sage into u/gh-vipul79321/ticket27247

comment:30 Changed 19 months ago by dcoudert

  • Reviewers set to David Coudert

LGTM. Please add your name in authors field (in addition to the name of Martin).

comment:31 follow-up: Changed 19 months ago by gh-vipul79321

  • Authors changed from Martin Rubey to Martin Rubey, Vipul Gupta

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 19 months ago by dcoudert

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 system build failed(current scenario).

Check on the logs if a failure is related to the ticket.Here it is clearly not the case.

comment:33 Changed 19 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:34 Changed 19 months ago by vbraun

  • Branch changed from u/gh-vipul79321/ticket27247 to b5f18845ee0076863e64b12bc9a4961285bbcefe
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.