Slice decomposition¶

This module implements an extended lexBFS algorithm for computing the slice decomposition of undirected graphs and the class SliceDecomposition to represent such decompositions.

A formal definition of slice decompositions can be found in Section 3.2 of [TCHP2008] and a description of the extended lexBFS algorithm is given in Section 3.3 of [TCHP2008].

AUTHORS:

Cyril Bouvier (2024-06-25): initial version

class sage.graphs.graph_decompositions.slice_decomposition.SliceDecomposition[source]¶

Bases: SageObject

Represents a slice decomposition of a simple directed graph.

INPUT:

G – a Sage graph.
initial_vertex – (default: None); the first vertex to consider.

See also

slice_decomposition() – compute a slice decomposition of the simple undirected graph
Section 3.2 of [TCHP2008] for a formal definition.

EXAMPLES:

The constructor of the SliceDecomposition class is called by the slice_decomposition() method of undirected graphs:

Sage

sage: from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
sage: G = graphs.PetersenGraph()
sage: SliceDecomposition(G) == G.slice_decomposition()
True

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
>>> G = graphs.PetersenGraph()
>>> SliceDecomposition(G) == G.slice_decomposition()
True

The vertex appearing first in the slice decomposition can be specified:

Sage

sage: from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
sage: SliceDecomposition(graphs.PetersenGraph(), initial_vertex=3)
[3[2[4[8]]] [1[7]] [0] [9] [6] [5]]

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
>>> SliceDecomposition(graphs.PetersenGraph(), initial_vertex=Integer(3))
[3[2[4[8]]] [1[7]] [0] [9] [6] [5]]

Slice decompositions are not defined for directed graphs:

Sage

sage: from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
sage: SliceDecomposition(DiGraph())
Traceback (most recent call last):
...
ValueError: parameter G must be an undirected graph

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.slice_decomposition import SliceDecomposition
>>> SliceDecomposition(DiGraph())
Traceback (most recent call last):
...
ValueError: parameter G must be an undirected graph

__getitem__(v)[source]¶

Return the data about the x-slice of the vertex \(v\).

INPUT:

v – a vertex of the graph corresponding to the slice decomposition.

OUTPUT:

A dictionnary with the keys:

"pivot" – the vertex \(v\) given as parameter
"slice" – the slice of \(v\) (see slice())
"active_edges" – the actives edges of \(v\) (see active_edges())
"lexicographic_label" – the lexicographic label of \(v\) (see lexicographic_label())
"sequence" – the x-slice sequence of \(v\) (see xslice_sequence())

This method can also be called via xslice_data().

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.xslice_data('a')
{'active_edges': [('a', 'b'),
  ('a', 'c'),
  ('a', 'd'),
  ('a', 'e'),
  ('a', 'f'),
  ('c', 'g'),
  ('d', 'g'),
  ('f', 'g')],
 'lexicographic_label': ['x'],
 'pivot': 'a',
 'sequence': [['a'], ['b', 'c', 'd', 'e', 'f'], ['g']],
 'slice': ['a', 'b', 'c', 'd', 'e', 'f', 'g']}
sage: SD.xslice_data('u')
{'active_edges': [],
 'lexicographic_label': ['a', 'b', 'c', 'd', 'e', 'f', 'g'],
 'pivot': 'u',
 'sequence': [['u'], ['y', 'z']],
 'slice': ['u', 'y', 'z']}

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.xslice_data('a')
{'active_edges': [('a', 'b'),
  ('a', 'c'),
  ('a', 'd'),
  ('a', 'e'),
  ('a', 'f'),
  ('c', 'g'),
  ('d', 'g'),
  ('f', 'g')],
 'lexicographic_label': ['x'],
 'pivot': 'a',
 'sequence': [['a'], ['b', 'c', 'd', 'e', 'f'], ['g']],
 'slice': ['a', 'b', 'c', 'd', 'e', 'f', 'g']}
>>> SD.xslice_data('u')
{'active_edges': [],
 'lexicographic_label': ['a', 'b', 'c', 'd', 'e', 'f', 'g'],
 'pivot': 'u',
 'sequence': [['u'], ['y', 'z']],
 'slice': ['u', 'y', 'z']}

Some values of the returned dictionnary can be obtained via other methods (slice(), xslice_sequence(), active_edges(), lexicographic_label()):

Sage

sage: SD.slice('a')
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: SD.xslice_data('a')['slice']
['a', 'b', 'c', 'd', 'e', 'f', 'g']

sage: SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]
sage: SD.xslice_data('a')['sequence']
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]

sage: SD.active_edges('b') == SD.xslice_data('b')['active_edges']
True

sage: SD.lexicographic_label('u')
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: SD.xslice_data('u')['lexicographic_label']
['a', 'b', 'c', 'd', 'e', 'f', 'g']

Python

>>> from sage.all import *
>>> SD.slice('a')
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> SD.xslice_data('a')['slice']
['a', 'b', 'c', 'd', 'e', 'f', 'g']

>>> SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]
>>> SD.xslice_data('a')['sequence']
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]

>>> SD.active_edges('b') == SD.xslice_data('b')['active_edges']
True

>>> SD.lexicographic_label('u')
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> SD.xslice_data('u')['lexicographic_label']
['a', 'b', 'c', 'd', 'e', 'f', 'g']

active_edges(v)[source]¶

Return the active edges of the vertex \(v\).

An edge \((u, w)\) is said to be active for \(v\) if \(u\) and \(w\) belongs to two differents slices of the x-slice sequence of \(v\). Note that it defines a partition of the edges of the underlying graph.

INPUT:

v – a vertex of the graph corresponding to the slice decomposition.

OUTPUT:

A list of edges

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]
sage: ('c', 'g') in SD.active_edges('a')
True
sage: ('a', 'c') in SD.active_edges('a')
True
sage: ('c', 'd') in SD.active_edges('a')  # c and d in same slice
False
sage: ('a', 'u') in SD.active_edges('a')  # u not in x-slice of a
False

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]
>>> ('c', 'g') in SD.active_edges('a')
True
>>> ('a', 'c') in SD.active_edges('a')
True
>>> ('c', 'd') in SD.active_edges('a')  # c and d in same slice
False
>>> ('a', 'u') in SD.active_edges('a')  # u not in x-slice of a
False

The set of active edges of every vertex is a partition of the edges:

Sage

sage: from itertools import chain
sage: E = list(chain(*(SD.active_edges(v) for v in G)))
sage: G.size() == len(E) == len(set(E)) \
....:   and all(G.has_edge(u, w) for v in G for u, w in SD.active_edges(v))
True

Python

>>> from sage.all import *
>>> from itertools import chain
>>> E = list(chain(*(SD.active_edges(v) for v in G)))
>>> G.size() == len(E) == len(set(E))   and all(G.has_edge(u, w) for v in G for u, w in SD.active_edges(v))
True

lexBFS_order()[source]¶

Return the lexBFS order corresponding to the slice decomposition.

EXAMPLES:

Sage

sage: from sage.graphs.traversals import _is_valid_lex_BFS_order
sage: G = graphs.PetersenGraph(); SD = G.slice_decomposition()
sage: SD.lexBFS_order()
[0, 1, 4, 5, 2, 6, 3, 9, 7, 8]
sage: _is_valid_lex_BFS_order(G, SD.lexBFS_order())
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import _is_valid_lex_BFS_order
>>> G = graphs.PetersenGraph(); SD = G.slice_decomposition()
>>> SD.lexBFS_order()
[0, 1, 4, 5, 2, 6, 3, 9, 7, 8]
>>> _is_valid_lex_BFS_order(G, SD.lexBFS_order())
True

lexicographic_label(v)[source]¶

Return the lexicographic label of the vertex \(v\).

The lexicographic label of a vertex \(v\) is the list of all the neighbors of \(v\) that appear before \(v\) in the lexBFS ordering corresponding to the slice decomposition.

INPUT:

v – a vertex of the graph corresponding to the slice decomposition.

OUTPUT:

A list of vertices.

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.lexicographic_label('f')
['x', 'a', 'c', 'd']
sage: pos = lambda v: SD.lexBFS_order().index(v)
sage: set(SD.lexicographic_label('f')) \
....:   == {v for v in G.neighbors('f') if pos(v) < pos('f')}
True

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.lexicographic_label('f')
['x', 'a', 'c', 'd']
>>> pos = lambda v: SD.lexBFS_order().index(v)
>>> set(SD.lexicographic_label('f'))   == {v for v in G.neighbors('f') if pos(v) < pos('f')}
True

slice(v)[source]¶

Return the slice of the vertex \(v\).

The slice of \(v\) is the list of vertices \(u\) such that the neighbors of \(u\) that are before \(v\) in the lexBFS order are that same that the neighbors of \(v\) that are before \(v\) in the lexBFS order (i.e., the lexicographic label of \(v\)). It can be shown that it is a factor of the lexBFS order.

INPUT:

v – a vertex of the graph corresponding to the slice decomposition.

OUTPUT:

A list of vertices

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.slice('a')
['a', 'b', 'c', 'd', 'e', 'f', 'g']

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.slice('a')
['a', 'b', 'c', 'd', 'e', 'f', 'g']

The vertices of the slice have the same neighborhood “on the left”:

Sage

sage: pos = lambda v: SD.lexBFS_order().index(v)
sage: lla = set(SD.lexicographic_label('a'))
sage: all(lla == {u for u in G.neighbors(v) if pos(u) < pos('a')} \
....:       for v in SD.slice('a'))
True

Python

>>> from sage.all import *
>>> pos = lambda v: SD.lexBFS_order().index(v)
>>> lla = set(SD.lexicographic_label('a'))
>>> all(lla == {u for u in G.neighbors(v) if pos(u) < pos('a')}       for v in SD.slice('a'))
True

The slice is a factor of the lexBFS order:

Sage

sage: ''.join(SD.slice('a')) in ''.join(SD.lexBFS_order())
True

Python

>>> from sage.all import *
>>> ''.join(SD.slice('a')) in ''.join(SD.lexBFS_order())
True

The slice of the initial vertex is the whole graph:

Sage

sage: SD.slice('x') == SD.lexBFS_order()
True

Python

>>> from sage.all import *
>>> SD.slice('x') == SD.lexBFS_order()
True

underlying_graph()[source]¶

Return the underlying graph corresponding to the slice decomposition.

If \(G\) was the graph given as parameter to compute the slice decomposition, the underlying graph corresponds to G.to_simple() where labels are ignored, i.e., it is the input graph without loops, multiple edges and labels.

Note

This method is mostly defined to test the computation of lexicographic labels and actives edges.

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.underlying_graph() == G
True

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.underlying_graph() == G
True

The graph can have loops or multiple edges but they are ignored:

Sage

sage: G = graphs.CubeConnectedCycle(2)  # multiple edges
sage: SD = G.slice_decomposition()
sage: SD.underlying_graph() == G.to_simple(immutable=True)
True

sage: G = graphs.CubeConnectedCycle(1)  # loops
sage: SD = G.slice_decomposition()
sage: SD.underlying_graph() == G.to_simple(immutable=True)
True

Python

>>> from sage.all import *
>>> G = graphs.CubeConnectedCycle(Integer(2))  # multiple edges
>>> SD = G.slice_decomposition()
>>> SD.underlying_graph() == G.to_simple(immutable=True)
True

>>> G = graphs.CubeConnectedCycle(Integer(1))  # loops
>>> SD = G.slice_decomposition()
>>> SD.underlying_graph() == G.to_simple(immutable=True)
True

xslice_data(v)[source]¶

Return the data about the x-slice of the vertex \(v\).

This method is a wrapper around SliceDecomposition.__getitem__()

xslice_sequence(v)[source]¶

Return the x-slice sequence of the vertex \(v\).

INPUT:

v – a vertex of the graph corresponding to the slice decomposition.

OUTPUT:

A list of list corresponding to the x-slice sequence of v.

EXAMPLES:

Sage

sage: G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
sage: SD = G.slice_decomposition(initial_vertex='x')
sage: SD.xslice_sequence('x')
[['x'], ['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['u', 'y', 'z'], ['v', 'w']]
sage: SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]

Python

>>> from sage.all import *
>>> G = Graph('L~mpn~Nrv{^o~_').relabel('abcdefguvwxyz',inplace=False)
>>> SD = G.slice_decomposition(initial_vertex='x')
>>> SD.xslice_sequence('x')
[['x'], ['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['u', 'y', 'z'], ['v', 'w']]
>>> SD.xslice_sequence('a')
[['a'], ['b', 'c', 'd', 'e', 'f'], ['g']]

The flatten x-slice sequence of a vertex corresponds to the slice of the same vertex:

Sage

sage: from itertools import chain
sage: all(list(chain(*SD.xslice_sequence(v))) == SD.slice(v) \
....:       for v in G)
True

Python

>>> from sage.all import *
>>> from itertools import chain
>>> all(list(chain(*SD.xslice_sequence(v))) == SD.slice(v)       for v in G)
True

The first list of the sequence is always a singleton containing the input vertex:

Sage

sage: all(SD.xslice_sequence(v)[0] == [v] for v in G)
True

Python

>>> from sage.all import *
>>> all(SD.xslice_sequence(v)[Integer(0)] == [v] for v in G)
True

If the length of the slice if more than 1, the second list of the sequence is either, all the remaining vertices of the slice of \(v\), if \(v\) is isolated in the subgraph induced by the slice of \(v\), or the neighbors of \(v\) in the subgraph induced by the slice of \(v\):

Sage

sage: all(SD.xslice_sequence(v)[1] == SD.slice(v)[1:] for v in G \
....:           if G.subgraph(SD.slice(v)).degree(v) == 0 \
....:               and len(SD.slice(v)) > 1)
True
sage: for v in G:
....:     if len(SD.slice(v)) > 1:
....:         xslice_seq = SD.xslice_sequence(v)
....:         S = G.subgraph(SD.slice(v))
....:         if S.degree(v) > 0:
....:             set(xslice_seq[1]) == set(S.neighbor_iterator(v))
True
True
True
True

Python

>>> from sage.all import *
>>> all(SD.xslice_sequence(v)[Integer(1)] == SD.slice(v)[Integer(1):] for v in G           if G.subgraph(SD.slice(v)).degree(v) == Integer(0)               and len(SD.slice(v)) > Integer(1))
True
>>> for v in G:
...     if len(SD.slice(v)) > Integer(1):
...         xslice_seq = SD.xslice_sequence(v)
...         S = G.subgraph(SD.slice(v))
...         if S.degree(v) > Integer(0):
...             set(xslice_seq[Integer(1)]) == set(S.neighbor_iterator(v))
True
True
True
True

sage.graphs.graph_decompositions.slice_decomposition.slice_decomposition(G, initial_vertex=None)[source]¶

Compute a slice decomposition of the simple undirected graph

INPUT:

G – a Sage graph.
initial_vertex – (default: None); the first vertex to consider.

OUTPUT:

An object of type SliceDecomposition that represents a slice decomposition of G

Note

Loops and multiple edges are ignored during the computation of the slice decomposition.

ALGORITHM:

The method use the algorithm based on “partition refinement” described in [HMPV2000] and [TCHP2008]. The time complexity of this algorithm is in \(O(n + m)\), and our implementation follows that complexity for SparseGraph. For DenseGraph, the complexity is \(O(n^2)\).

EXAMPLES:

Slice decomposition of the Petersen Graph:

Sage

sage: G = graphs.PetersenGraph()
sage: SD = G.slice_decomposition(); SD
[0[1[4[5]]] [2[6]] [3] [9] [7] [8]]

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> SD = G.slice_decomposition(); SD
[0[1[4[5]]] [2[6]] [3] [9] [7] [8]]

The graph can have loops or multiple edges but they are ignored:

Sage

sage: H = Graph(G,loops=True,multiedges=True)
sage: H.add_edges([(4, 4), (2, 2), (1, 6)])
sage: SD2 = H.slice_decomposition()
sage: SD2 == SD
True
sage: SD2.underlying_graph() == G.to_simple(immutable=True)
True

Python

>>> from sage.all import *
>>> H = Graph(G,loops=True,multiedges=True)
>>> H.add_edges([(Integer(4), Integer(4)), (Integer(2), Integer(2)), (Integer(1), Integer(6))])
>>> SD2 = H.slice_decomposition()
>>> SD2 == SD
True
>>> SD2.underlying_graph() == G.to_simple(immutable=True)
True

The tree corresponding to the slice decomposition can be displayed using view:

Sage

sage: from sage.graphs.graph_latex import check_tkz_graph
sage: check_tkz_graph()  # random - depends on Tex installation
sage: view(G)  # not tested
sage: latex(G)  # to obtain the corresponding LaTeX code
\begin{tikzpicture}
...
\end{tikzpicture}

Python

>>> from sage.all import *
>>> from sage.graphs.graph_latex import check_tkz_graph
>>> check_tkz_graph()  # random - depends on Tex installation
>>> view(G)  # not tested
>>> latex(G)  # to obtain the corresponding LaTeX code
\begin{tikzpicture}
...
\end{tikzpicture}

Slice decompositions are only defined for undirected graphs:

Sage

sage: from sage.graphs.graph_decompositions.slice_decomposition import slice_decomposition
sage: slice_decomposition(DiGraph())
Traceback (most recent call last):
...
ValueError: parameter G must be an undirected graph

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.slice_decomposition import slice_decomposition
>>> slice_decomposition(DiGraph())
Traceback (most recent call last):
...
ValueError: parameter G must be an undirected graph