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)[source]#
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|)\).Note
As the graph is converted to a short_digraph (with
sort_neighbors=True), the complexity has an extra \(O(|V|+|E|\log{|E|})\) forSparseGraphand \(O(|V|^2\log{|E|})\) forDenseGraph.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 graphtree– 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 aLabelledRootedTree. WhentreeisTrue, this parameter is ignored.separators– boolean (default:False); whether to also return the complete list of separators considered during the execution of the algorithm. Whentreeorrooted_treeisTrue, 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
separatorsisTrue, 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
treeisTrue, format the result as a directed treeWhen
rooted_treeisTrueandtreeisFalse, format the output as aLabelledRootedTree
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
>>> from sage.all import * >>> 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']}) >>> atoms, cliques = G.atoms_and_clique_separators() >>> 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']] >>> sorted(sorted(c) for c in cliques) [['c', 'k'], ['d', 'j', 'k'], ['j', 'k']] >>> T = G.atoms_and_clique_separators(tree=True) >>> T.is_tree() True >>> T.diameter() == len(atoms) True >>> all(u[Integer(1)] in atoms for u in T if T.degree(u) == Integer(1)) True >>> all(u[Integer(1)] in cliques for u in T if T.degree(u) != Integer(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}
>>> from sage.all import * >>> G = graphs.CompleteGraph(Integer(5)) >>> G.atoms_and_clique_separators() ([{0, 1, 2, 3, 4}], []) >>> 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}
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(4)) >>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True)) ____{2}____ / / {2, 3} __{1}__ / / {1, 2} {0, 1} >>> G = graphs.WindmillGraph(Integer(3), Integer(4)) >>> G.atoms_and_clique_separators() ([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}]) >>> 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(sort=False), 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}
>>> from sage.all import * >>> G = Graph(Integer(2)) >>> for i in range(Integer(5)): ... G.add_cycle([Integer(0), Integer(1), G.add_vertex()]) >>> 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} >>> G = graphs.StarGraph(Integer(3)) >>> G.subdivide_edges(G.edges(sort=False), Integer(2)) >>> 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}
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(3)) * Integer(3) >>> A, Sc = G.atoms_and_clique_separators() >>> A [{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}] >>> Sc [{1}, {}, {4}, {}, {7}] >>> i , j = [i for i, s in enumerate(Sc) if not s] >>> i, j (1, 3) >>> A[:i+Integer(1)], Sc[:i] ([{1, 2}, {0, 1}], [{1}]) >>> A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j] ([{4, 5}, {3, 4}], [{4}]) >>> A[j+Integer(1):], Sc[j+Integer(1):] ([{8, 7}, {6, 7}], [{7}]) >>> I = [-Integer(1), i, j, len(Sc)] >>> for i, j in zip(I[:-Integer(1)], I[Integer(1):]): ... print(A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j]) [{1, 2}, {0, 1}] [{1}] [{4, 5}, {3, 4}] [{4}] [{8, 7}, {6, 7}] [{7}] >>> 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(sort=False)) 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}
>>> from sage.all import * >>> G.allow_loops(True) >>> G.add_edges([(u, u) for u in G]) >>> G.allow_multiple_edges(True) >>> G.add_edges(G.edges(sort=False)) >>> 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")
>>> from sage.all import * >>> G = graphs.RandomGNP(Integer(50), RealNumber('.1')) >>> while not G.is_connected(): ... G = graphs.RandomGNP(Integer(50), RealNumber('.1')) >>> _, separators, _ = G.atoms_and_clique_separators(separators=True) >>> 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)[source]#
Return a
LabelledRootedTreeof 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}
>>> from sage.all import * >>> G = graphs.PathGraph(Integer(5)) >>> 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)[source]#
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
cliquesis empty and 2 otherwise. Whencliquesis 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 atomscliques– 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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.clique_separators import make_tree >>> G = graphs.Grid2dGraph(Integer(2), Integer(4)) >>> A, Sc = G.atoms_and_clique_separators() >>> T = make_tree(A, Sc) >>> all(u[Integer(1)] in A for u in T if T.degree(u) == Integer(1)) True >>> all(u[Integer(1)] in Sc for u in T if T.degree(u) != Integer(1)) True