Cutwidth¶
This module implements several algorithms to compute the cutwidth of a graph and the corresponding ordering of the vertices. It also implements tests functions for evaluation the width of a linear ordering (or layout).
Given an ordering
of the vertices of
, its cost is defined as:
Where
The cutwidth of a graph is equal to the minimum cost of an ordering of its
vertices.
This module contains the following methods
cutwidth() |
Return the cutwidth of the graph and the corresponding vertex ordering. |
cutwidth_dyn() |
Compute the cutwidth of ![]() |
width_of_cut_decomposition() |
Return the width of the cut decomposition induced by the linear ordering ![]() ![]() |
Exponential algorithm for cutwidth¶
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 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 algorithm.
This algorithm and its implementation are very similar to
sage.graphs.graph_decompositions.vertex_separation.vertex_separation_exp()
.
The main difference is in the computation of . See the
vertex
separation module's documentation
for more details on this
algorithm.
Note
Because of its current implementation, this algorithm only works on graphs on strictly less than 32 vertices. This can be changed to 64 if necessary, but 32 vertices already require 4GB of memory.
Authors¶
- David Coudert (2015-06): Initial version
Methods¶
-
sage.graphs.graph_decompositions.cutwidth.
cutwidth
(G, algorithm='exponential', cut_off=0)¶ Return the cutwidth of the graph and the corresponding vertex ordering.
INPUT:
G
– a Graph or a DiGraphalgorithm
– (default:"exponential"
) Specify the algorithm to use amongexponential
– Use an exponential time and space algorithm based on dynamic programming. This algorithm only works on graphs with strictly less than 32 vertices.
cut_off
– (default: 0) This parameter is used to stop the search as soon as a solution with width at mostcut_off
is found, if any. If this bound cannot be reached, the best solution found is returned.
OUTPUT:
A pair
(cost, ordering)
representing the optimal ordering of the vertices and its cost.EXAMPLES:
Cutwidth of a Complete Graph:
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth sage: G = graphs.CompleteGraph(5) sage: cw,L = cutwidth(G, algorithm="exponential"); cw 6 sage: K = graphs.CompleteGraph(6) sage: cw,L = cutwidth(K, algorithm="exponential"); cw 9 sage: cw,L = cutwidth(K+K, algorithm="exponential"); cw 9
The cutwidth of a
Grid Graph with
is
:
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth sage: G = graphs.Grid2dGraph(3,3) sage: cw,L = cutwidth(G, algorithm="exponential"); cw 4 sage: G = graphs.Grid2dGraph(3,5) sage: cw,L = cutwidth(G, algorithm="exponential"); cw 4
TESTS:
Given a wrong algorithm:
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth sage: cutwidth(Graph(), algorithm="SuperFast") Traceback (most recent call last): ... ValueError: Algorithm "SuperFast" has not been implemented yet. Please contribute.
Given anything else than a Graph:
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth sage: cutwidth(range(4)) Traceback (most recent call last): ... ValueError: The parameter must be a Graph.
Giving a wrong type cut off:
sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth sage: cutwidth(Graph(), cut_off='toto') Traceback (most recent call last): ... ValueError: The specified cut off parameter must be an integer.
-
sage.graphs.graph_decompositions.cutwidth.
cutwidth_dyn
(G, lower_bound=0)¶ Dynamic programming algorithm for the cutwidth of a Graph.
This function uses dynamic programming algorithm for determining an optimal layout for the cutwidth of
. See the
module's documentation
for more details on this method.INPUT:
G
– a Graphlower_bound
– (default: 0) the algorithm returns immediately if it finds a solution lower or equal tolower_bound
(in which case it may not be optimal).
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 strictly less than 32 vertices. This can be changed to 63 if necessary, but 32 vertices already require 4GB of memory.
TESTS:
Giving anything else than a Graph:
sage: from sage.graphs.graph_decompositions import cutwidth sage: cutwidth.cutwidth_dyn([]) Traceback (most recent call last): ... ValueError: The parameter must be a Graph.
Giving a too large Graph:
sage: from sage.graphs.graph_decompositions import cutwidth sage: cutwidth.cutwidth_dyn(graphs.PathGraph(40)) Traceback (most recent call last): ... ValueError: The graph should have at most 31 vertices !
Giving a wrong type lower bound:
sage: from sage.graphs.graph_decompositions import cutwidth sage: cutwidth.cutwidth_dyn(Graph(), lower_bound='toto') Traceback (most recent call last): ... ValueError: The specified lower bound must be an integer.
-
sage.graphs.graph_decompositions.cutwidth.
width_of_cut_decomposition
(G, L)¶ Returns the width of the cut decomposition induced by the linear ordering
of the vertices of
.
If
is an instance of
Graph
, this function returns the widthof the cut decomposition induced by the linear ordering
of the vertices of
.
INPUT:
G
– a GraphL
– a linear ordering of the vertices ofG
EXAMPLES:
Cut decomposition of a Cycle graph:
sage: from sage.graphs.graph_decompositions import cutwidth sage: G = graphs.CycleGraph(6) sage: L = G.vertices() sage: cutwidth.width_of_cut_decomposition(G, L) 2
Cut decomposition of a Path graph:
sage: from sage.graphs.graph_decompositions import cutwidth sage: P = graphs.PathGraph(6) sage: cutwidth.width_of_cut_decomposition(P, [0, 1, 2, 3, 4, 5]) 1 sage: cutwidth.width_of_cut_decomposition(P, [5, 0, 1, 2, 3, 4]) 2 sage: cutwidth.width_of_cut_decomposition(P, [0, 2, 4, 1, 3, 5]) 5
TESTS:
Giving a wrong linear ordering:
sage: from sage.graphs.graph_decompositions import cutwidth sage: cutwidth.width_of_cut_decomposition(Graph(), ['a','b']) Traceback (most recent call last): ... ValueError: The input linear vertex ordering L is not valid for G.