modular_decomposition should be able to return a tree

[mantepse]

Change return type to rooted labeled tree.

[mantepse]

Last 10 new commits:

​8ba0fc6	Implemented suggested changes
​0a06a7b	Added missing doctests.
​fc82c80	Small doc fixes.
​e00479e	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
​a86307a	Fixed doctests for __str__ and __repr__
​225dfe0	Improved formatting of documentation
​161e1d6	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
​cd41b57	fixed stupid errors
​1f1b9df	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
​9e82fd6	add possibility to return a tree

[dcoudert]

I'm a bit lost here. What's the part you added ?

At least, the ascii_art tree is really nice ;)

[mantepse]

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

[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())

[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.

[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.

[embray]

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

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).

[dcoudert]

Now that #26496 is merge, we can restart working on this ticket

[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?

[dcoudert]

I don't know if the original author is willing to finalize this ticket or not. Let him some time to answer.

[mantepse]

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

[gh-vipul79321]

New commits:

​d8e69ce

Style=tree added and doc updated

[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>`.
  

[git]

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

​428c0bf

documentation fixed

[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`.

[gh-vipul79321]

Replying to git:

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

​428c0bf

documentation fixed

Updated according to comment 23

[dcoudert]

Right, but you should change accordingly the part

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

[git]

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

​3ecdc64

fixed silly mistake

[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

[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?

[git]

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

[dcoudert]

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

[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).

[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.

[dcoudert]

LGTM.