Add the Habib Maurer algorithm for modular decomposition to graphs

[deinst]

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(n³)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.

Component: graph theory

Author: David Einstein

Branch/Commit: c910704

Reviewer: David Coudert, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/26496

[deinst]

Branch: u/deinst/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs

[deinst]

comment:3

The code should now be functional. I need to fix up the documentation and add a bunch of tests.

---

New commits:

534ba95	Moved modular_decomposition.
6722b32	Fix is_prime
8e57c73	Added Habib-Maurer algorithm to Graph.modular_decomposition

[deinst]

Commit: 8e57c73

[sagetrac-git]

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

d00dcbe

Added some randomized tests.

[sagetrac-git]

Changed commit from 8e57c73 to d00dcbe

[dcoudert]

comment:5

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 avoid e = 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 ?

[deinst]

comment:6

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.

[sagetrac-git]

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

a81f2d2

Added code for random test of modular decomposition from reconstruction

[sagetrac-git]

Changed commit from d00dcbe to a81f2d2

[deinst]

comment:8

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.

[sagetrac-git]

Changed commit from a81f2d2 to ff7c910

[sagetrac-git]

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

314ada6	Minor documentation changes.
abe1365	Merge branch 'develop' into t/26496/add_the_habib_maurer_algorithm_for_modular_decomposition_to_graphs
ff7c910	Fixed up docstrings.

[deinst]

comment:10

Most of the new code is to support the random tests.

[sagetrac-git]

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

65ed276

Fixed errors the patchbot was complaining about

[sagetrac-git]

Changed commit from ff7c910 to 65ed276

[dcoudert]

comment:13

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)

[sagetrac-git]

Changed commit from 65ed276 to 8ba0fc6

[sagetrac-git]

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

8ba0fc6

Implemented suggested changes

[deinst]

comment:15

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?

[sagetrac-git]

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

0a06a7b

Added missing doctests.

[sagetrac-git]

Changed commit from 8ba0fc6 to 0a06a7b

[sagetrac-git]

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

8d3698f	trac #26496: Merged with 8.9.beta7
81a4629	trac #26496: fix some issues in the documentation

[sagetrac-git]

Changed commit from cc32a97 to 81a4629

[dcoudert]

comment:61

I fixed some issues. Now the html documentation should build properly. More can certainly be done in another ticket...

[fchapoton]

comment:62

red branch

[sagetrac-git]

Changed commit from 81a4629 to f577d00

[sagetrac-git]

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

f577d00

trac #26496: fix merge conflict with 8.9.rc0

[dcoudert]

comment:64

fixed.

[dcoudert]

comment:65

now its green ;)

[fchapoton]

comment:66

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)

[sagetrac-git]

Changed commit from f577d00 to c910704

[sagetrac-git]

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

b6ffd63	trac #26496: avoid using \
71b7e42	trac #26496: some pep8 cleaning
c910704	trac #26496: more cleaning

[dcoudert]

comment:68

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.

[fchapoton]

comment:69

I've just launched my bot on it.

[fchapoton]

Changed reviewer from David Coudert to David Coudert, Frédéric Chapoton

[fchapoton]

comment:70

ok, let us say "good to go"

[dcoudert]

comment:71

Thanks.

[fchapoton]

comment:72

moving milestone to 9.0 (after release of 8.9)

[vbraun]

Changed branch from public/graphs/26496_habib_maurer_algorithm_for_modular_decomposition to c910704