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_exp() |
Computes the vertex separation of ![]() |
vertex_separation_MILP() |
Computes the vertex separation of ![]() |
vertex_separation_BAB() |
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 ![]() ![]() |
Exponential algorithm for vertex separation¶
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 algorithm.
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.
MILP formulation for the vertex separation¶
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:
– Variable set to 1 if
, and 0 otherwise. The order of
in the layout is the smallest
such that
.
– Variable set to 1 if
and
has an in-neighbor in
. It is set to 0 otherwise.
– Variable set to 1 if either
or if
has an in-neighbor in
. It is set to 0 otherwise.
– Objective value to minimize. It is equal to the maximum over all step
of the number of vertices such that
.
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
.
Branch and Bound algorithm for the vertex separation¶
We describe below the principle of a branch and bound algorithm (BAB) for
determining an optimal ordering for the vertex separation of , as proposed in
[CMN14].
Greedy steps:
Let us denote the set of all possible orderings of the vertices in
, and let
be the orderings starting with
a prefix
. Let also
be the cost of the ordering
as
defined above.
Given a digraph , a set
, and a prefix
, it has been
proved in [CMN14] that
holds in two (non exhaustive) cases:
In other words, if we find a vertex satisfying the above conditions, the best
possible ordering with prefix
has the same cost as the best possible
ordering with prefix
. So we can greedily extend the prefix with vertices
satisfying the conditions which results in a significant reduction of the search
space.
The algorithm:
Given the current prefix and the current upper bound
(either an input
upper bound or the cost of the best solution found so far), apply the following
steps:
- Extend the prefix
into a prefix
using the greedy steps as described above.
- Sort the vertices
by increasing values of
, and prune the vertices with a value larger or equal to
. Let
be the resulting sorted list.
- Repeat with prefix
for all
and keep the best found solution.
If a lower bound is passed to the algorithm, it will stop as soon as a solution with cost equal to that lower bound is found.
Storing prefixes:
If for a prefix we have
, then for any
permutation
of
we have
.
Thus, given such a prefix there is no need to explore any of the orderings
starting with one of its permutations. To do so, we store
(as a set of
vertices) to cut branches later. See [CMN14] for more details.
Since the number of stored sets can get very large, one can control the maximum length and the maximum number of stored prefixes.
REFERENCES¶
[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. |
[CMN14] | (1, 2, 3, 4) Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth, David Coudert, Dorian Mazauric, and Nicolas Nisse. In Symposium on Experimental Algorithms (SEA), volume 8504 of LNCS, Copenhagen, Denmark, pages 46-58, June 2014, http://hal.inria.fr/hal-00943549/document |
Authors¶
- Nathann Cohen (2011-10): Initial version and exact exponential algorithm
- David Coudert (2012-04): MILP formulation and tests functions
- David Coudert (2015-01): BAB formulation and tests functions
Methods¶
-
sage.graphs.graph_decompositions.vertex_separation.
is_valid_ordering
(G, L)¶ 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:
G
– a Graph or a DiGraph.L
– an ordered list of the vertices ofG
.
OUTPUT:
Returns
True
ifis a valid vertex ordering for
, and
False
otherwise.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'.
-
sage.graphs.graph_decompositions.vertex_separation.
lower_bound
(G)¶ Returns a lower bound on the vertex separation of
INPUT:
G
– a Graph or a DiGraph
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 Graph or a DiGraph:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound sage: lower_bound(range(2)) Traceback (most recent call last): ... ValueError: The parameter must be a Graph or a DiGraph.
Given a too large graph:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound sage: lower_bound(graphs.PathGraph(50)) Traceback (most recent call last): ... ValueError: The (di)graph can have at most 31 vertices.
-
sage.graphs.graph_decompositions.vertex_separation.
path_decomposition
(G, algorithm='BAB', cut_off=None, upper_bound=None, verbose=False, max_prefix_length=20, max_prefix_number=1000000)¶ Returns the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition.
INPUT:
G
– a Graphalgorithm
– (default:"BAB"
) Specify the algorithm to use among"BAB"
– Use a branch-and-bound algorithm. This algorithm has no size restriction but could take a very long time on large graphs. It can also be used to test is the input (di)graph has vertex separation at mostupper_bound
or to return the first found solution with vertex separation less or equal to acut_off
value.exponential
– Use an exponential time and space algorithm. This algorithm only works of graphs on less than 32 vertices.MILP
– Use a mixed integer linear programming formulation. This algorithm has no size restriction but could take a very long time.
upper_bound
– (default:None
) This is parameter is used by the"BAB"
algorithm. If specified, the algorithm searches for a solution withwidth < upper_bound
. It helps cutting branches. However, if the given upper bound is too low, the algorithm may not be able to find a solution.cut_off
– (default: None) This is parameter is used by the"BAB"
algorithm. This bound allows us 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, unless a too lowupper_bound
is given.verbose
(boolean) – whether to display information on the computations.max_prefix_length
– (default: 20) limits the length of the stored prefixes to prevent storing too many prefixes. This parameter is used only whenalgorithm=="BAB"
.max_prefix_number
– (default: 10**6) upper bound on the number of stored prefixes used to prevent using too much memory. This parameter is used only whenalgorithm=="BAB"
.
OUTPUT:
A pair
(cost, ordering)
representing the optimal ordering of the vertices and its cost.See also
Graph.treewidth()
– computes the treewidth of a graph
EXAMPLE:
The pathwidth 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, algorithm = "BAB"); pw 2 sage: pw, L = path_decomposition(g, algorithm = "exponential"); pw 2 sage: pw, L = path_decomposition(g, algorithm = "MILP"); pw 2
TEST:
Given anything else than a Graph:
sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition sage: path_decomposition(DiGraph()) Traceback (most recent call last): ... ValueError: The parameter must be a Graph.
Given a wrong algorithm:
sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition sage: path_decomposition(Graph(), algorithm="SuperFast") Traceback (most recent call last): ... ValueError: Algorithm "SuperFast" has not been implemented yet. Please contribute.
-
sage.graphs.graph_decompositions.vertex_separation.
vertex_separation
(G, algorithm='BAB', cut_off=None, upper_bound=None, verbose=False, max_prefix_length=20, max_prefix_number=1000000)¶ Returns an optimal ordering of the vertices and its cost for vertex-separation.
INPUT:
G
– a Graph or a DiGraphalgorithm
– (default:"BAB"
) Specify the algorithm to use among"BAB"
– Use a branch-and-bound algorithm. This algorithm has no size restriction but could take a very long time on large graphs. It can also be used to test is the input (di)graph has vertex separation at mostupper_bound
or to return the first found solution with vertex separation less or equal to acut_off
value.exponential
– Use an exponential time and space algorithm. This algorithm only works of graphs on less than 32 vertices.MILP
– Use a mixed integer linear programming formulation. This algorithm has no size restriction but could take a very long time.
upper_bound
– (default:None
) This is parameter is used by the"BAB"
algorithm. If specified, the algorithm searches for a solution withwidth < upper_bound
. It helps cutting branches. However, if the given upper bound is too low, the algorithm may not be able to find a solution.cut_off
– (default: None) This is parameter is used by the"BAB"
algorithm. This bound allows us 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, unless a too lowupper_bound
is given.verbose
(boolean) – whether to display information on the computations.max_prefix_length
– (default: 20) limits the length of the stored prefixes to prevent storing too many prefixes. This parameter is used only whenalgorithm=="BAB"
.max_prefix_number
– (default: 10**6) upper bound on the number of stored prefixes used to prevent using too much memory. This parameter is used only whenalgorithm=="BAB"
.
OUTPUT:
A pair
(cost, ordering)
representing the optimal ordering of the vertices and its cost.EXAMPLES:
Comparison of methods:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: G = digraphs.DeBruijn(2,3) sage: vs,L = vertex_separation(G, algorithm="BAB"); vs 2 sage: vs,L = vertex_separation(G, algorithm="exponential"); vs 2 sage: vs,L = vertex_separation(G, algorithm="MILP"); vs 2 sage: G = graphs.Grid2dGraph(3,3) sage: vs,L = vertex_separation(G, algorithm="BAB"); vs 3 sage: vs,L = vertex_separation(G, algorithm="exponential"); vs 3 sage: vs,L = vertex_separation(G, algorithm="MILP"); vs 3
Digraphs with multiple strongly connected components:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: D = digraphs.Path(8) sage: print(vertex_separation(D)) (0, [7, 6, 5, 4, 3, 2, 1, 0]) sage: D = DiGraph( random_DAG(30) ) sage: vs,L = vertex_separation(D); vs 0 sage: K4 = DiGraph( graphs.CompleteGraph(4) ) sage: D = K4+K4 sage: D.add_edge(0, 4) sage: print(vertex_separation(D)) (3, [4, 5, 6, 7, 0, 1, 2, 3]) sage: D = K4+K4+K4 sage: D.add_edge(0, 4) sage: D.add_edge(0, 8) sage: print(vertex_separation(D)) (3, [8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3])
TESTS:
Given a wrong algorithm:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: vertex_separation(Graph(), algorithm="SuperFast") Traceback (most recent call last): ... ValueError: Algorithm "SuperFast" has not been implemented yet. Please contribute.
Given anything else than a Graph or a DiGraph:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: vertex_separation(range(4)) Traceback (most recent call last): ... ValueError: The parameter must be a Graph or a DiGraph.
-
sage.graphs.graph_decompositions.vertex_separation.
vertex_separation_BAB
(G, cut_off=None, upper_bound=None, max_prefix_length=20, max_prefix_number=1000000, verbose=False)¶ Branch and Bound algorithm for the vertex separation.
This method implements the branch and bound algorithm for the vertex separation of directed graphs and the pathwidth of undirected graphs proposed in [CMN14]. The implementation is valid for both Graph and DiGraph. See the documentation of the
vertex_separation
module.INPUT:
G
– a Graph or a DiGraph.cut_off
– (default: None) bound to consider in the branch and bound algorithm. This allows us 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, unless a too lowupper_bound
is given.upper_bound
– (default: None) if specified, the algorithm searches for a solution withwidth < upper_bound
. It helps cutting branches. However, if the given upper bound is too low, the algorithm may not be able to find a solution.max_prefix_length
– (default: 20) limits the length of the stored prefixes to prevent storing too many prefixes.max_prefix_number
– (default: 10**6) upper bound on the number of stored prefixes used to prevent using too much memory.verbose
– (default: False) display some information when set to True.
OUTPUT:
width
– the computed vertex separationseq
– an ordering of the vertices of widthwidth
.
EXAMPLES:
The algorithm is valid for the vertex separation:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: D = digraphs.RandomDirectedGNP(15, .2) sage: vb, seqb = VS.vertex_separation_BAB(D) sage: vd, seqd = VS.vertex_separation_exp(D) sage: vb == vd True sage: vb == VS.width_of_path_decomposition(D, seqb) True
The vertex separation of a
grid is
:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.Grid2dGraph(4,4) sage: vs, seq = VS.vertex_separation_BAB(G); vs 4 sage: vs == VS.width_of_path_decomposition(G, seq) True
The vertex separation of a
grid with
is
:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.Grid2dGraph(3,5) sage: vs, seq = VS.vertex_separation_BAB(G); vs 3 sage: vs == VS.width_of_path_decomposition(G, seq) True
The vertex separation of circuit of order
is 1:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: D = digraphs.Circuit(10) sage: vs, seq = VS.vertex_separation_BAB(D); vs 1 sage: vs == VS.width_of_path_decomposition(D, seq) True
The vertex separation of cycle of order
is 2:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.CycleGraph(10) sage: vs, seq = VS.vertex_separation_BAB(G); vs 2
The vertex separation of
MycielskiGraph(5)
is 10:sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.MycielskiGraph(5) sage: vs, seq = VS.vertex_separation_BAB(G); vs 10
Searching for any solution with width less or equal to
cut_off
:sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.MycielskiGraph(5) sage: vs, seq = VS.vertex_separation_BAB(G, cut_off=11); vs 11 sage: vs, seq = VS.vertex_separation_BAB(G, cut_off=10); vs 10 sage: vs, seq = VS.vertex_separation_BAB(G, cut_off=9); vs 10
Testing for the existence of a solution with width strictly less than
upper_bound
:sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.MycielskiGraph(5) sage: vs, seq = VS.vertex_separation_BAB(G, upper_bound=11); vs 10 sage: vs, seq = VS.vertex_separation_BAB(G, upper_bound=10); vs -1 sage: vs, seq = VS.vertex_separation_BAB(G, cut_off=11, upper_bound=10); vs -1
Changing the parameters of the prefix storage:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: G = graphs.MycielskiGraph(5) sage: vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=0); vs 10 sage: vs, seq = VS.vertex_separation_BAB(G, max_prefix_number=5); vs 10 sage: vs, seq = VS.vertex_separation_BAB(G, max_prefix_number=0); vs 10
TESTS:
Giving anything else than a Graph or a DiGraph:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: VS.vertex_separation_BAB(range(5)) Traceback (most recent call last): ... ValueError: The input parameter must be a Graph or a DiGraph.
Giving an empty Graph or DiGraph:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: VS.vertex_separation_BAB(Graph()) (0, []) sage: VS.vertex_separation_BAB(DiGraph()) (0, [])
Giving a too low upper bound:
sage: from sage.graphs.graph_decompositions import vertex_separation as VS sage: VS.vertex_separation_BAB(digraphs.Circuit(3), upper_bound=0) Traceback (most recent call last): ... ValueError: The input upper bound must be at least 1.
-
sage.graphs.graph_decompositions.vertex_separation.
vertex_separation_MILP
(G, integrality=False, solver=None, verbosity=0)¶ 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.INPUT:
G
– a Graph or a DiGraphintegrality
– (default:False
) Specify if variablesand
must be integral or if they can be relaxed. This has no impact on the validity of the solution, but it is sometimes faster to solve the problem using binary variables only.
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
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 Graph or 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 Graph or a DiGraph.
-
sage.graphs.graph_decompositions.vertex_separation.
vertex_separation_exp
(G, verbose=False)¶ Returns an optimal ordering of the vertices and its cost for vertex-separation.
INPUT:
G
– a Graph or a DiGraph.verbose
(boolean) – whether to display information on the computations.
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_exp sage: g = digraphs.Circuit(6) sage: vertex_separation_exp(g) (1, [0, 1, 2, 3, 4, 5])
TEST:
Given anything else than a Graph or a DiGraph:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation_exp sage: vertex_separation_exp(range(3)) Traceback (most recent call last): ... ValueError: The parameter must be a Graph or a DiGraph.
Graphs with non-integer vertices:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation_exp sage: D=digraphs.DeBruijn(2,3) sage: vertex_separation_exp(D) (2, ['000', '001', '100', '010', '101', '011', '110', '111'])
Given a too large graph:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation_exp sage: vertex_separation_exp(graphs.PathGraph(50)) Traceback (most recent call last): ... ValueError: The graph should have at most 31 vertices !
-
sage.graphs.graph_decompositions.vertex_separation.
width_of_path_decomposition
(G, L)¶ 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 widthof the path decomposition induced by the linear ordering
of the vertices of
. If
is a
DiGraph
, it returns instead the widthof the directed path decomposition induced by the linear ordering
of the vertices of
, where
INPUT:
G
– a Graph or a DiGraphL
– a linear ordering of the vertices ofG
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.