Decomposition by clique minimal separators

This module implements methods related to the decomposition of a graph by clique minimal separators. See [TY1984] and [BPS2010] for more details on the algorithms.

Methods

sage.graphs.graph_decompositions.clique_separators.atoms_and_clique_separators(G, tree=False, rooted_tree=False, separators=False)

Return the atoms of the decomposition of \(G\) by clique minimal separators.

Let \(G = (V, E)\) be a graph. A set \(S \subset V\) is a clique separator if \(G[S]\) is a clique and the graph \(G \setminus S\) has at least 2 connected components. Let \(C \subset V\) be the vertices of a connected component of \(G \setminus S\). The graph \(G[C + S]\) is an atom if it has no clique separator.

This method implements the algorithm proposed in [BPS2010], that improves upon the algorithm proposed in [TY1984], for computing the atoms and the clique minimal separators of a graph. This algorithm is based on the maximum_cardinality_search_M() graph traversal and has time complexity in \(O(|V|\cdot|E|)\).

If the graph is not connected, we insert empty separators between the lists of separators of each connected components. See the examples below for more details.

INPUT:

  • G – a Sage graph

  • tree – boolean (default: False); whether to return the result as a directed tree in which internal nodes are clique separators and leaves are the atoms of the decomposition. Since a clique separator is repeated when its removal partition the graph into 3 or more connected components, vertices are labels by tuples \((i, S)\), where \(S\) is the set of vertices of the atom or the clique separator, and \(0 \leq i \leq |T|\).

  • rooted_tree – boolean (default: False); whether to return the result as a LabelledRootedTree. When tree is True, this parameter is ignored.

  • separators – boolean (default: False); whether to also return the complete list of separators considered during the execution of the algorithm. When tree or rooted_tree is True, this parameter is ignored.

OUTPUT:

  • By default, return a tuple \((A, S_c)\), where \(A\) is the list of atoms of the graph in the order of discovery, and \(S_c\) is the list of clique separators, with possible repetitions, in the order the separator has been considered. If furthermore separators is True, return a tuple \((A, S_h, S_c)\), where \(S_c\) is the list of considered separators of the graph in the order they have been considered.

  • When tree is True, format the result as a directed tree

  • When rooted_tree is True and tree is False, format the output as a LabelledRootedTree

EXAMPLES:

Example of [BPS2010]:

sage: G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
....:            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
....:            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
....:            'i': ['k'], 'j': ['k']})
sage: atoms, cliques = G.atoms_and_clique_separators()
sage: sorted(sorted(a) for a in atoms)
[['a', 'b', 'c', 'k'],
 ['c', 'd', 'j', 'k'],
 ['d', 'e', 'f', 'g', 'j', 'k'],
 ['h', 'i', 'j', 'k']]
sage: sorted(sorted(c) for c in cliques)
[['c', 'k'], ['d', 'j', 'k'], ['j', 'k']]
sage: T = G.atoms_and_clique_separators(tree=True)
sage: T.is_tree()
True
sage: T.diameter() == len(atoms)
True
sage: all(u[1] in atoms for u in T if T.degree(u) == 1)
True
sage: all(u[1] in cliques for u in T if T.degree(u) != 1)
True

A graph without clique separator:

sage: G = graphs.CompleteGraph(5)
sage: G.atoms_and_clique_separators()
([{0, 1, 2, 3, 4}], [])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
{0, 1, 2, 3, 4}

Graphs with several biconnected components:

sage: G = graphs.PathGraph(4)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ____{2}____
 /          /
{2, 3}   __{1}__
        /      /
       {1, 2} {0, 1}

sage: G = graphs.WindmillGraph(3, 4)
sage: G.atoms_and_clique_separators()
([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ________{0}________
 /                  /
{0, 1, 2}   _______{0}______
           /               /
          {0, 3, 4}   ____{0}___
                     /         /
                    {0, 8, 7} {0, 5, 6}

When the removal of a clique separator results in \(k > 2\) connected components, this separator is repeated \(k - 1\) times, but the repetitions are not necessarily contiguous:

sage: G = Graph(2)
sage: for i in range(5):
....:     G.add_cycle([0, 1, G.add_vertex()])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  _________{0, 1}_____
 /                   /
{0, 1, 4}   ________{0, 1}_____
           /                  /
          {0, 1, 2}   _______{0, 1}___
                     /               /
                    {0, 1, 3}   ____{0, 1}
                               /         /
                              {0, 1, 5} {0, 1, 6}

sage: G = graphs.StarGraph(3)
sage: G.subdivide_edges(G.edges(), 2)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{5}______
 /              /
{1, 5}   ______{7}______
        /              /
       {2, 7}   ______{9}______
               /              /
              {9, 3}   ______{6}______
                      /              /
                     {6, 7}   ______{4}_____
                             /             /
                            {4, 5}   _____{0}_____
                                    /            /
                                   {0, 6}   ____{8}____
                                           /          /
                                          {8, 9}   __{0}__
                                                  /      /
                                                 {0, 8} {0, 4}

If the graph is not connected, we insert empty separators between the lists of separators of each connected components. For instance, let \(G\) be a graph with 3 connected components. The method returns the list \(S_c = [S_0,\cdots,S_{i},\ldots, S_{j},\ldots,S_{k-1}]\) of \(k\) clique separators, where \(i\) and \(j\) are the indexes of the inserted empty separators and \(0 \leq i < j < k - 1\). The method also returns the list \(A = [A_0,\ldots,S_{k}]\) of the \(k + 1\) atoms, with \(k + 1 \geq 3\). The lists of atoms and clique separators of each of the connected components are respectively \([A_0,\ldots,A_{i}]\) and \([S_0,\ldots,S_{i-1}]\), \([A_{i+1},\ldots,A_{j}]\) and \([S_{i+1},\ldots,S_{j-1}]\), and \([A_{j+1},\ldots,A_{k}]\) and \([S_{j+1},\ldots,S_{k-1}]\). One can check that for each connected component, we get one atom more than clique separators:

sage: G = graphs.PathGraph(3) * 3
sage: A, Sc = G.atoms_and_clique_separators()
sage: A
[{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}]
sage: Sc
[{1}, {}, {4}, {}, {7}]
sage: i , j = [i for i, s in enumerate(Sc) if not s]
sage: i, j
(1, 3)
sage: A[:i+1], Sc[:i]
([{1, 2}, {0, 1}], [{1}])
sage: A[i+1:j+1], Sc[i+1:j]
([{4, 5}, {3, 4}], [{4}])
sage: A[j+1:], Sc[j+1:]
([{8, 7}, {6, 7}], [{7}])
sage: I = [-1, i, j, len(Sc)]
sage: for i, j in zip(I[:-1], I[1:]):
....:     print(A[i+1:j+1], Sc[i+1:j])
[{1, 2}, {0, 1}] [{1}]
[{4, 5}, {3, 4}] [{4}]
[{8, 7}, {6, 7}] [{7}]
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

Loops and multiple edges are ignored:

sage: G.allow_loops(True)
sage: G.add_edges([(u, u) for u in G])
sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges())
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

We can check that the returned list of separators is valid:

sage: G = graphs.RandomGNP(50, .1)
sage: while not G.is_connected():
....:     G = graphs.RandomGNP(50, .1)
sage: _, separators, _ = G.atoms_and_clique_separators(separators=True)
sage: for S in separators:
....:     H = G.copy()
....:     H.delete_vertices(S)
....:     if H.is_connected():
....:         raise ValueError("something goes wrong")
sage.graphs.graph_decompositions.clique_separators.make_labelled_rooted_tree(atoms, cliques)

Return a LabelledRootedTree of atoms and cliques.

The atoms are the leaves of the tree and the cliques are the internal vertices. The number of atoms is the number of cliques plus one.

EXAMPLES:

sage: G = graphs.PathGraph(5)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  _____{3}_____
 /            /
{3, 4}   ____{2}____
        /          /
       {2, 3}   __{1}__
               /      /
              {0, 1} {1, 2}
sage.graphs.graph_decompositions.clique_separators.make_tree(atoms, cliques)

Return a tree of atoms and cliques.

The atoms are the leaves of the tree and the cliques are the internal vertices. The number of atoms is the number of cliques plus one.

As a clique may appear several times in the list cliques, vertices are numbered by pairs \((i, S)\), where \(0 \leq i < |atoms| + |cliques|\) and \(S\) is either an atom or a clique.

The root of the tree is the only vertex with even or null degree, i.e., 0 if cliques is empty and 2 otherwise. When cliques is not empty, other internal vertices (each of which is a clique) have degree 3, and the leaves (vertices of degree 1) are the atoms.

INPUT:

  • atoms – list of atoms

  • cliques – list of cliques

EXAMPLES:

sage: from sage.graphs.graph_decompositions.clique_separators import make_tree
sage: G = graphs.Grid2dGraph(2, 4)
sage: A, Sc = G.atoms_and_clique_separators()
sage: T = make_tree(A, Sc)
sage: all(u[1] in A for u in T if T.degree(u) == 1)
True
sage: all(u[1] in Sc for u in T if T.degree(u) != 1)
True