Vertex separation
This module implements several algorithms to compute the vertex separation of a digraph and the corresponding ordering of the vertices. It also implements tests functions for evaluation the width of a linear ordering.
Given an ordering
of the vertices of
, its cost is defined as:
Where
The vertex separation of a digraph is equal to the minimum cost of an
ordering of its vertices.
Vertex separation and pathwidth
The vertex separation is defined on a digraph, but one can obtain from a graph
a digraph
with the same vertex set, and in which each edge
of
is replaced by two edges
and
in
. The vertex separation of
is
equal to the pathwidth of
, and the corresponding ordering of the vertices of
, also called a layout, encodes an optimal path-decomposition of
.
This is a result of Kinnersley [Kin92] and Bodlaender [Bod98].
This module contains the following methods
path_decomposition() | Returns the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition |
vertex_separation() | Returns an optimal ordering of the vertices and its cost for vertex-separation |
vertex_separation_MILP() | Computes the vertex separation of ![]() |
lower_bound() | Returns a lower bound on the vertex separation of ![]() |
is_valid_ordering() | Test if the linear vertex ordering ![]() ![]() |
width_of_path_decomposition() | Returns the width of the path decomposition induced by the linear ordering ![]() ![]() |
In order to find an optimal ordering of the vertices for the vertex separation,
this algorithm tries to save time by computing the function at most
once once for each of the sets
. These values are stored in
an array of size
where reading the value of
or updating it can be
done in constant (and small) time.
Assuming that we can compute the cost of a set and remember it, finding an
optimal ordering is an easy task. Indeed, we can think of the sequence
of vertices as a sequence of sets
, whose cost is precisely
. Hence, when considering the digraph on the
sets
where there is an arc from
to
if
for some
(that is, if the sets
and
can be consecutive in a
sequence), an ordering of the vertices of
corresponds to a path from
to
. In this setting, checking whether there exists
a ordering of cost less than
can be achieved by checking whether there
exists a directed path
to
using only sets of cost
less than
. This is just a depth-first-search, for each
.
Lazy evaluation of
In the previous algorithm, most of the time is actually spent on the computation
of for each set
– i.e.
computations of
neighborhoods. This can be seen as a huge waste of time when noticing that it is
useless to know that the value
for a set
is less than
if all the
paths leading to
have a cost greater than
. For this reason, the value of
is computed lazily during the depth-first search. Explanation :
When the depth-first search discovers a set of size less than , the costs of
its out-neighbors (the potential sets that could follow it in the optimal
ordering) are evaluated. When an out-neighbor is found that has a cost smaller
than
, the depth-first search continues with this set, which is explored with
the hope that it could lead to a path toward
. On the other
hand, if an out-neighbour has a cost larger than
it is useless to attempt to
build a cheap sequence going though this set, and the exploration stops
there. This way, a large number of sets will never be evaluated and a lot of
computational time is saved this way.
Besides, some improvement is also made by “improving” the values found by
. Indeed,
is a lower bound on the cost of a sequence containing the
set
, but if all out-neighbors of
have a cost of
then one
knows that having
in a sequence means a total cost of at least
. For this reason, for each set
we store the value of
, and replace
it by
(where
is the
minimum of the costs of the out-neighbors of
) once the costs of these
out-neighbors have been evaluated by the algrithm.
Note
Because of its current implementation, this algorithm only works on graphs
on less than 32 vertices. This can be changed to 64 if necessary, but 32
vertices already require 4GB of memory. Running it on 64 bits is not
expected to be doable by the computers of the next decade
Lower bound on the vertex separation
One can obtain a lower bound on the vertex separation of a graph in exponential
time but small memory by computing once the cost of each set . Indeed, the
cost of a sequence
corresponding to sets
is
where is the minimum cost of a set
on
vertices. Evaluating the
can take time (and in particular more than the previous exact algorithm),
but it does not need much memory to run.
We describe below a mixed integer linear program (MILP) for determining an
optimal layout for the vertex separation of , which is an improved version of
the formulation proposed in [SP10]. It aims at building a sequence
of
sets such that an ordering
of the vertices correspond to
.
Variables:
MILP formulation:
The vertex separation of is given by the value of
, and the order of
vertex
in the optimal layout is given by the smallest
for which
.
[Bod98] | A partial k-arboretum of graphs with bounded treewidth, Hans L. Bodlaender, Theoretical Computer Science 209(1-2):1-45, 1998. |
[Kin92] | The vertex separation number of a graph equals its path-width, Nancy G. Kinnersley, Information Processing Letters 42(6):345-350, 1992. |
[SP10] | (1, 2) Lightpath Reconfiguration in WDM networks, Fernando Solano and Michal Pioro, IEEE/OSA Journal of Optical Communication and Networking 2(12):1010-1021, 2010. |
Bases: object
x.__init__(...) initializes x; see help(type(x)) for signature
Displays the adjacency matrix of self.
Test if the linear vertex ordering is valid for (di)graph
.
A linear ordering of the vertices of a (di)graph
is valid if all
vertices of
are in
, and if
contains no other vertex and no
duplicated vertices.
INPUT:
OUTPUT:
Returns True if is a valid vertex ordering for
, and False
oterwise.
EXAMPLE:
Path decomposition of a cycle:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.is_valid_ordering(G, L)
True
sage: vertex_separation.is_valid_ordering(G, [1,2])
False
TEST:
Giving anything else than a Graph or a DiGraph:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: vertex_separation.is_valid_ordering(2, [])
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph or a DiGraph.
Giving anything else than a list:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: vertex_separation.is_valid_ordering(G, {})
Traceback (most recent call last):
...
ValueError: The second parameter must be of type 'list'.
Returns a lower bound on the vertex separation of
INPUT:
OUTPUT:
A lower bound on the vertex separation of (see the module’s
documentation).
Note
This method runs in exponential time but has no memory constraint.
EXAMPLE:
On a circuit:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = digraphs.Circuit(6)
sage: lower_bound(g)
1
TEST:
Given anything else than a DiGraph:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = graphs.CycleGraph(5)
sage: lower_bound(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a DiGraph.
Returns the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition.
INPUT:
OUTPUT:
A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.
Note
Because of its current implementation, this exponential algorithm only works on graphs on less than 32 vertices. This can be changed to 54 if necessary, but 32 vertices already require 4GB of memory.
See also
EXAMPLE:
The vertex separation of a cycle is equal to 2:
sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition
sage: g = graphs.CycleGraph(6)
sage: pw, L = path_decomposition(g); pw
2
sage: pwm, Lm = path_decomposition(g, algorithm = "MILP"); pwm
2
TEST:
Given anything else than a Graph:
sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition
sage: g = digraphs.Circuit(6)
sage: path_decomposition(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a Graph.
Correction test for popcount32.
EXAMPLE:
sage: from sage.graphs.graph_decompositions.vertex_separation import test_popcount
sage: test_popcount() # not tested
Returns an optimal ordering of the vertices and its cost for vertex-separation.
INPUT:
OUTPUT:
A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.
Note
Because of its current implementation, this algorithm only works on graphs on less than 32 vertices. This can be changed to 54 if necessary, but 32 vertices already require 4GB of memory.
EXAMPLE:
The vertex separation of a circuit is equal to 1:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation
sage: g = digraphs.Circuit(6)
sage: vertex_separation(g)
(1, [0, 1, 2, 3, 4, 5])
TEST:
Given anything else than a DiGraph:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = graphs.CycleGraph(5)
sage: lower_bound(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a DiGraph.
Graphs with non-integer vertices:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation
sage: D=digraphs.DeBruijn(2,3)
sage: vertex_separation(D)
(2, ['000', '001', '100', '010', '101', '011', '110', '111'])
Computes the vertex separation of and the optimal ordering of its
vertices using an MILP formulation.
This function uses a mixed integer linear program (MILP) for determining an
optimal layout for the vertex separation of . This MILP is an improved
version of the formulation proposed in [SP10]. See the module's
documentation for more
details on this MILP formulation.
INPUTS:
OUTPUT:
A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.
EXAMPLE:
Vertex separation of a De Bruijn digraph:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.DeBruijn(2,3)
sage: vs, L = vertex_separation.vertex_separation_MILP(G); vs
2
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
True
sage: vse, Le = vertex_separation.vertex_separation(G); vse
2
The vertex separation of a circuit is 1:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(6)
sage: vs, L = vertex_separation.vertex_separation_MILP(G); vs
1
TESTS:
Comparison with exponential algorithm:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: for i in range(10):
... G = digraphs.RandomDirectedGNP(10, 0.2)
... ve, le = vertex_separation.vertex_separation(G)
... vm, lm = vertex_separation.vertex_separation_MILP(G)
... if ve != vm:
... print "The solution is not optimal!"
Comparison with different values of the integrality parameter:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: for i in range(10): # long time (11s on sage.math, 2012)
....: G = digraphs.RandomDirectedGNP(10, 0.2)
....: va, la = vertex_separation.vertex_separation_MILP(G, integrality=False)
....: vb, lb = vertex_separation.vertex_separation_MILP(G, integrality=True)
....: if va != vb:
....: print "The integrality parameter changes the result!"
Giving anything else than a DiGraph:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: vertex_separation.vertex_separation_MILP([])
Traceback (most recent call last):
...
ValueError: The first input parameter must be a DiGraph.
Returns the width of the path decomposition induced by the linear ordering
of the vertices of
.
If is an instance of Graph, this function
returns the width
of the path decomposition induced by the linear
ordering
of the vertices of
. If
is a DiGraph, it returns instead the width
of the
directed path decomposition induced by the linear ordering
of the
vertices of
, where
INPUT:
EXAMPLES:
Path decomposition of a cycle:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.width_of_path_decomposition(G, L)
2
Directed path decomposition of a circuit:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.width_of_path_decomposition(G, L)
1
TESTS:
Path decomposition of a BalancedTree:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.BalancedTree(3,2)
sage: pw, L = vertex_separation.path_decomposition(G)
sage: pw == vertex_separation.width_of_path_decomposition(G, L)
True
sage: L.reverse()
sage: pw == vertex_separation.width_of_path_decomposition(G, L)
False
Directed path decomposition of a circuit:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(8)
sage: vs, L = vertex_separation.vertex_separation(G)
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
True
sage: L = [0,4,6,3,1,5,2,7]
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
False
Giving a wrong linear ordering:
sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = Graph()
sage: vertex_separation.width_of_path_decomposition(G, ['a','b'])
Traceback (most recent call last):
...
ValueError: The input linear vertex ordering L is not valid for G.