Rank Decompositions of graphs#
This module wraps C code from Philipp Klaus Krause computing an optimal rank-decomposition.
Definitions :
Given a graph \(G\) and a subset \(S\subseteq V(G)\) of vertices, the rank-width of \(S\) in \(G\), denoted \(rw_G(S)\), is equal to the rank in \(GF(2)\) of the \(|S| \times (|V|-|S|)\) matrix of the adjacencies between the vertices of \(S\) and \(V\backslash S\). By definition, \(rw_G(S)\) is equal to \(rw_G(\overline S)\) where \(\overline S\) is the complement of \(S\) in \(V(G)\).
A rank-decomposition of \(G\) is a tree whose \(n\) leaves are the elements of \(V(G)\), and whose internal nodes have degree 3. In a tree, any edge naturally corresponds to a bipartition of the vertex set : indeed, the removal of any edge splits the tree into two connected components, thus splitting the set of leaves (i.e. vertices of \(G\)) into two sets. Hence we can define for any edge \(e\in E(G)\) a width equal to the value \(rw_G(S)\) or \(rw_G(\overline S)\), where \(S,\overline S\) is the bipartition obtained from \(e\). The rank-width associated to the whole decomposition is then set to the maximum of the width of all the edges it contains.
A rank-decomposition is said to be optimal for \(G\) if it is the decomposition achieving the minimal rank-width.
RW – The original source code :
RW is a program that calculates rank-width and rank-decompositions. It is based on ideas from:
OUTPUT:
The rank decomposition is returned as a tree whose vertices are subsets of \(V(G)\). Its leaves, corresponding to the vertices of \(G\) are sets of 1 elements, i.e. singletons.
sage: g = graphs.PetersenGraph()
sage: rw, tree = g.rank_decomposition()
sage: all(len(v)==1 for v in tree if tree.degree(v) == 1)
True
>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> rw, tree = g.rank_decomposition()
>>> all(len(v)==Integer(1) for v in tree if tree.degree(v) == Integer(1))
True
The internal nodes are sets of the decomposition. This way, it is easy to deduce the bipartition associated to an edge from the tree. Indeed, two adjacent vertices of the tree are comparable sets : they yield the bipartition obtained from the smaller of the two and its complement.
sage: g = graphs.PetersenGraph()
sage: rw, tree = g.rank_decomposition()
sage: u = Set([8, 9, 3, 7])
sage: v = Set([8, 9])
sage: tree.has_edge(u,v)
True
sage: m = min(u,v)
sage: bipartition = (m, Set(g.vertices(sort=False)) - m)
sage: bipartition
({8, 9}, {0, 1, 2, 3, 4, 5, 6, 7})
>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> rw, tree = g.rank_decomposition()
>>> u = Set([Integer(8), Integer(9), Integer(3), Integer(7)])
>>> v = Set([Integer(8), Integer(9)])
>>> tree.has_edge(u,v)
True
>>> m = min(u,v)
>>> bipartition = (m, Set(g.vertices(sort=False)) - m)
>>> bipartition
({8, 9}, {0, 1, 2, 3, 4, 5, 6, 7})
Warning
The current implementation cannot handle graphs of \(\geq 32\) vertices.
A bug that has been reported upstream make the code crash immediately on instances of size \(30\). If you experience this kind of bug please report it to us, what we need is some information on the hardware you run to know where it comes from !
EXAMPLES:
sage: g = graphs.PetersenGraph()
sage: g.rank_decomposition()
(3, Graph on 19 vertices)
>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> g.rank_decomposition()
(3, Graph on 19 vertices)
AUTHORS:
Philipp Klaus Krause : Implementation of the C algorithm
Nathann Cohen : Interface with Sage and documentation
Methods#
- sage.graphs.graph_decompositions.rankwidth.mkgraph(num_vertices)[source]#
Return the graph corresponding to the current rank-decomposition.
(This function is for internal use)
EXAMPLES:
sage: from sage.graphs.graph_decompositions.rankwidth import rank_decomposition sage: g = graphs.PetersenGraph() sage: rank_decomposition(g) (3, Graph on 19 vertices)
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.rankwidth import rank_decomposition >>> g = graphs.PetersenGraph() >>> rank_decomposition(g) (3, Graph on 19 vertices)
- sage.graphs.graph_decompositions.rankwidth.rank_decomposition(G, verbose=False)[source]#
Compute an optimal rank-decomposition of the given graph.
This function is available as a method of the
Graph
class. Seerank_decomposition
.INPUT:
verbose
– boolean (default:False
); whether to display progress information while computing the decomposition
OUTPUT:
A pair
(rankwidth, decomposition_tree)
, whererankwidth
is a numerical value anddecomposition_tree
is a ternary tree describing the decomposition (cf. the module’s documentation).EXAMPLES:
sage: from sage.graphs.graph_decompositions.rankwidth import rank_decomposition sage: g = graphs.PetersenGraph() sage: rank_decomposition(g) (3, Graph on 19 vertices)
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.rankwidth import rank_decomposition >>> g = graphs.PetersenGraph() >>> rank_decomposition(g) (3, Graph on 19 vertices)
On more than 32 vertices:
sage: g = graphs.RandomGNP(40, .5) sage: rank_decomposition(g) Traceback (most recent call last): ... RuntimeError: the rank decomposition cannot be computed on graphs of >= 32 vertices
>>> from sage.all import * >>> g = graphs.RandomGNP(Integer(40), RealNumber('.5')) >>> rank_decomposition(g) Traceback (most recent call last): ... RuntimeError: the rank decomposition cannot be computed on graphs of >= 32 vertices
The empty graph:
sage: g = Graph() sage: rank_decomposition(g) (0, Graph on 0 vertices)
>>> from sage.all import * >>> g = Graph() >>> rank_decomposition(g) (0, Graph on 0 vertices)