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 \(v_1,\cdots, v_n\) of the vertices of \(V(G)\), its cost is defined as:
Where
The vertex separation of a digraph \(G\) 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 \(G\) a digraph \(D\) with the same vertex set, and in which each edge \(uv\) of \(G\) is replaced by two edges \(uv\) and \(vu\) in \(D\). The vertex separation of \(D\) is equal to the pathwidth of \(G\), and the corresponding ordering of the vertices of \(D\), also called a layout, encodes an optimal pathdecomposition of \(G\). This is a result of Kinnersley [Kin1992] and Bodlaender [Bod1998].
This module contains the following methods
Compute the pathwidth of 

Return the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition 

Return an optimal ordering of the vertices and its cost for vertexseparation 

Compute the vertex separation of \(G\) using an exponential time and space algorithm 

Compute the vertex separation of \(G\) and the optimal ordering of its vertices using an MILP formulation 

Compute the vertex separation of \(G\) and the optimal ordering of its vertices using a branch and bound algorithm 

Return a lower bound on the vertex separation of \(G\) 

Test if the linear vertex ordering \(L\) is valid for (di)graph \(G\) 

Return the width of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\) 

Return the path decomposition encoded in the ordering \(L\) 
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 \(c'(S)\) at most once once for each of the sets \(S\subseteq V(G)\). These values are stored in an array of size \(2^n\) where reading the value of \(c'(S)\) or updating it can be done in constant (and small) time.
Assuming that we can compute the cost of a set \(S\) and remember it, finding an optimal ordering is an easy task. Indeed, we can think of the sequence \(v_1, ..., v_n\) of vertices as a sequence of sets \(\{v_1\}, \{v_1,v_2\}, ..., \{v_1,...,v_n\}\), whose cost is precisely \(\max c'(\{v_1\}), c'(\{v_1,v_2\}), ... , c'(\{v_1,...,v_n\})\). Hence, when considering the digraph on the \(2^n\) sets \(S\subseteq V(G)\) where there is an arc from \(S\) to \(S'\) if \(S'=S\cap \{v\}\) for some \(v\) (that is, if the sets \(S\) and \(S'\) can be consecutive in a sequence), an ordering of the vertices of \(G\) corresponds to a path from \(\emptyset\) to \(\{v_1,...,v_n\}\). In this setting, checking whether there exists a ordering of cost less than \(k\) can be achieved by checking whether there exists a directed path \(\emptyset\) to \(\{v_1,...,v_n\}\) using only sets of cost less than \(k\). This is just a depthfirstsearch, for each \(k\).
Lazy evaluation of \(c'\)
In the previous algorithm, most of the time is actually spent on the computation of \(c'(S)\) for each set \(S\subseteq V(G)\) – i.e. \(2^n\) computations of neighborhoods. This can be seen as a huge waste of time when noticing that it is useless to know that the value \(c'(S)\) for a set \(S\) is less than \(k\) if all the paths leading to \(S\) have a cost greater than \(k\). For this reason, the value of \(c'(S)\) is computed lazily during the depthfirst search. Explanation :
When the depthfirst search discovers a set of size less than \(k\), the costs of its outneighbors (the potential sets that could follow it in the optimal ordering) are evaluated. When an outneighbor is found that has a cost smaller than \(k\), the depthfirst search continues with this set, which is explored with the hope that it could lead to a path toward \(\{v_1,...,v_n\}\). On the other hand, if an outneighbour has a cost larger than \(k\) 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 \(c'\). Indeed, \(c'(S)\) is a lower bound on the cost of a sequence containing the set \(S\), but if all outneighbors of \(S\) have a cost of \(c'(S) + 5\) then one knows that having \(S\) in a sequence means a total cost of at least \(c'(S) + 5\). For this reason, for each set \(S\) we store the value of \(c'(S)\), and replace it by \(\max (c'(S), \min_{\text{next}})\) (where \(\min_{\text{next}}\) is the minimum of the costs of the outneighbors of \(S\)) once the costs of these outneighbors 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 \(:D\)
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 \(S\). Indeed, the cost of a sequence \(v_1, ..., v_n\) corresponding to sets \(\{v_1\}, \{v_1,v_2\}, ..., \{v_1,...,v_n\}\) is
where \(c_i\) is the minimum cost of a set \(S\) on \(i\) vertices. Evaluating the \(c_i\) 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 \(G\), which is an improved version of the formulation proposed in [SP2010]. It aims at building a sequence \(S_t\) of sets such that an ordering \(v_1, ..., v_n\) of the vertices correspond to \(S_0=\{v_1\}, S_2=\{v_1,v_2\}, ..., S_{n1}=\{v_1,...,v_n\}\).
Variables:
\(y_v^t\) – Variable set to 1 if \(v\in S_t\), and 0 otherwise. The order of \(v\) in the layout is the smallest \(t\) such that \(y_v^t==1\).
\(u_v^t\) – Variable set to 1 if \(v\not \in S_t\) and \(v\) has an inneighbor in \(S_t\). It is set to 0 otherwise.
\(x_v^t\) – Variable set to 1 if either \(v\in S_t\) or if \(v\) has an inneighbor in \(S_t\). It is set to 0 otherwise.
\(z\) – Objective value to minimize. It is equal to the maximum over all step \(t\) of the number of vertices such that \(u_v^t==1\).
MILP formulation:
The vertex separation of \(G\) is given by the value of \(z\), and the order of vertex \(v\) in the optimal layout is given by the smallest \(t\) for which \(y_v^t==1\).
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 \(G\), as proposed in [CMN2014].
Greedy steps:
Let us denote \({\cal L}(S)\) the set of all possible orderings of the vertices in \(S\), and let \({\cal L}_P(S)\subseteq {\cal L}(S)\) be the orderings starting with a prefix \(P\). Let also \(c(L)\) be the cost of the ordering \(L\in{\cal L}(V)\) as defined above.
Given a digraph \(D=(V,A)\), a set \(S\subset V\), and a prefix \(P\), it has been proved in [CMN2014] that \(\min_{L\in{\cal L}_P(V)} c(L) = \min_{L\in{\cal L}_{P+v}(V)} c(L)\) holds in two (non exhaustive) cases:
In other words, if we find a vertex \(v\) satisfying the above conditions, the best possible ordering with prefix \(P\) has the same cost as the best possible ordering with prefix \(P+v\). 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 \(P\) and the current upper bound \(UB\) (either an input upper bound or the cost of the best solution found so far), apply the following steps:
Extend the prefix \(P\) into a prefix \(P'\) using the greedy steps as described above.
Sort the vertices \(v\in V\setminus P'\) by increasing values of \(N^+(P+v)\), and prune the vertices with a value larger or equal to \(UB\). Let \(\Delta\) be the resulting sorted list.
Repeat with prefix \(P'+v\) for all \(v\in\Delta\) 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 \(P\) we have \(c(P)<\min_{L\in{\cal L}_P(V)} c(L)=C\), then for any permutation \(P'\) of \(P\) we have \(\min_{L\in{\cal L}_{P'}(V)} c(L)\geq C\).
Thus, given such a prefix \(P\) there is no need to explore any of the orderings starting with one of its permutations. To do so, we store \(P\) (as a set of vertices) to cut branches later. See [CMN2014] 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.
Methods#
 sage.graphs.graph_decompositions.vertex_separation.is_valid_ordering(G, L)[source]#
Test if the linear vertex ordering \(L\) is valid for (di)graph \(G\).
A linear ordering \(L\) of the vertices of a (di)graph \(G\) is valid if all vertices of \(G\) are in \(L\), and if \(L\) 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
if \(L\) is a valid vertex ordering for \(G\), andFalse
otherwise.EXAMPLES:
Path decomposition of a cycle:
sage: from sage.graphs.graph_decompositions import vertex_separation sage: G = graphs.CycleGraph(6) sage: L = G.vertices(sort=True) sage: vertex_separation.is_valid_ordering(G, L) True sage: vertex_separation.is_valid_ordering(G, [1,2]) False
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation >>> G = graphs.CycleGraph(Integer(6)) >>> L = G.vertices(sort=True) >>> vertex_separation.is_valid_ordering(G, L) True >>> vertex_separation.is_valid_ordering(G, [Integer(1),Integer(2)]) False
 sage.graphs.graph_decompositions.vertex_separation.linear_ordering_to_path_decomposition(G, L)[source]#
Return the path decomposition encoded in the ordering L
INPUT:
G
– a GraphL
– a linear ordering for G
OUTPUT:
A path graph whose vertices are the bags of the path decomposition.
EXAMPLES:
The bags of an optimal path decomposition of a pathgraph have two vertices each:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: from sage.graphs.graph_decompositions.vertex_separation import linear_ordering_to_path_decomposition sage: g = graphs.PathGraph(5) sage: pw, L = vertex_separation(g, algorithm = "BAB"); pw 1 sage: h = linear_ordering_to_path_decomposition(g, L) sage: sorted(h, key=str) [{0, 1}, {1, 2}, {2, 3}, {3, 4}] sage: sorted(h.edge_iterator(labels=None), key=str) [({0, 1}, {1, 2}), ({1, 2}, {2, 3}), ({2, 3}, {3, 4})]
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import vertex_separation >>> from sage.graphs.graph_decompositions.vertex_separation import linear_ordering_to_path_decomposition >>> g = graphs.PathGraph(Integer(5)) >>> pw, L = vertex_separation(g, algorithm = "BAB"); pw 1 >>> h = linear_ordering_to_path_decomposition(g, L) >>> sorted(h, key=str) [{0, 1}, {1, 2}, {2, 3}, {3, 4}] >>> sorted(h.edge_iterator(labels=None), key=str) [({0, 1}, {1, 2}), ({1, 2}, {2, 3}), ({2, 3}, {3, 4})]
Giving a nonoptimal linear ordering:
sage: g = graphs.PathGraph(5) sage: L = [1, 4, 0, 2, 3] sage: from sage.graphs.graph_decompositions.vertex_separation import width_of_path_decomposition sage: width_of_path_decomposition(g, L) 3 sage: h = linear_ordering_to_path_decomposition(g, L) sage: h.vertices(sort=True) [{0, 2, 3, 4}, {0, 1, 2}]
>>> from sage.all import * >>> g = graphs.PathGraph(Integer(5)) >>> L = [Integer(1), Integer(4), Integer(0), Integer(2), Integer(3)] >>> from sage.graphs.graph_decompositions.vertex_separation import width_of_path_decomposition >>> width_of_path_decomposition(g, L) 3 >>> h = linear_ordering_to_path_decomposition(g, L) >>> h.vertices(sort=True) [{0, 2, 3, 4}, {0, 1, 2}]
The bags of the path decomposition of a cycle have three vertices each:
sage: g = graphs.CycleGraph(6) sage: pw, L = vertex_separation(g, algorithm = "BAB"); pw 2 sage: h = linear_ordering_to_path_decomposition(g, L) sage: sorted(h, key=str) [{0, 1, 5}, {1, 2, 5}, {2, 3, 4}, {2, 4, 5}] sage: sorted(h.edge_iterator(labels=None), key=str) [({0, 1, 5}, {1, 2, 5}), ({1, 2, 5}, {2, 4, 5}), ({2, 4, 5}, {2, 3, 4})]
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(6)) >>> pw, L = vertex_separation(g, algorithm = "BAB"); pw 2 >>> h = linear_ordering_to_path_decomposition(g, L) >>> sorted(h, key=str) [{0, 1, 5}, {1, 2, 5}, {2, 3, 4}, {2, 4, 5}] >>> sorted(h.edge_iterator(labels=None), key=str) [({0, 1, 5}, {1, 2, 5}), ({1, 2, 5}, {2, 4, 5}), ({2, 4, 5}, {2, 3, 4})]
 sage.graphs.graph_decompositions.vertex_separation.lower_bound(G)[source]#
Return a lower bound on the vertex separation of \(G\).
INPUT:
G
– a Graph or a DiGraph
OUTPUT:
A lower bound on the vertex separation of \(D\) (see the module’s documentation).
Note
This method runs in exponential time but has no memory constraint.
EXAMPLES:
On a circuit:
sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound sage: g = digraphs.Circuit(6) sage: lower_bound(g) 1
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import lower_bound >>> g = digraphs.Circuit(Integer(6)) >>> lower_bound(g) 1
 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)[source]#
Return the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition.
INPUT:
G
– a Graphalgorithm
– string (default:"BAB"
); algorithm to use among:"BAB"
– Use a branchandbound 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
– integer (default:None
); parameter 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
– integer (default:None
); parameter 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 (default:False
); whether to display information on the computationsmax_prefix_length
– integer (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
– integer (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
EXAMPLES:
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 # needs sage.numerical.mip 2
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import path_decomposition >>> g = graphs.CycleGraph(Integer(6)) >>> pw, L = path_decomposition(g, algorithm="BAB"); pw 2 >>> pw, L = path_decomposition(g, algorithm="exponential"); pw 2 >>> pw, L = path_decomposition(g, algorithm="MILP"); pw # needs sage.numerical.mip 2
 sage.graphs.graph_decompositions.vertex_separation.pathwidth(self, k=None, certificate=False, algorithm='BAB', verbose=False, max_prefix_length=20, max_prefix_number=1000000, solver=None)[source]#
Compute the pathwidth of
self
(and provides a decomposition)INPUT:
k
– integer (default:None
); the width to be considered. Whenk
is an integer, the method checks that the graph has pathwidth \(\leq k\). Ifk
isNone
(default), the method computes the optimal pathwidth.certificate
– boolean (default:False
); whether to return the pathdecomposition itselfalgorithm
– string (default:"BAB"
); algorithm to use among:"BAB"
– Use a branchandbound 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 graph has pathwidth \(\leq k\), in which cas it will return the first found solution with width \(\leq k\) iscertificate==True
.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.
verbose
– boolean (default:False
); whether to display information on the computationsmax_prefix_length
– integer (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
– integer (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"
.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.
OUTPUT:
Return the pathwidth of
self
. Whenk
is specified, it returnsFalse
when no pathdecomposition of width \(\leq k\) exists orTrue
otherwise. Whencertificate=True
, the pathdecomposition is also returned.See also
Graph.treewidth()
– computes the treewidth of a graphvertex_separation()
– computes the vertex separation of a (di)graph
EXAMPLES:
The pathwidth of a cycle is equal to 2:
sage: g = graphs.CycleGraph(6) sage: g.pathwidth() 2 sage: pw, decomp = g.pathwidth(certificate=True) sage: sorted(decomp, key=str) [{0, 1, 5}, {1, 2, 5}, {2, 3, 4}, {2, 4, 5}]
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(6)) >>> g.pathwidth() 2 >>> pw, decomp = g.pathwidth(certificate=True) >>> sorted(decomp, key=str) [{0, 1, 5}, {1, 2, 5}, {2, 3, 4}, {2, 4, 5}]
The pathwidth of a Petersen graph is 5:
sage: g = graphs.PetersenGraph() sage: g.pathwidth() 5 sage: g.pathwidth(k=2) False sage: g.pathwidth(k=6) True sage: g.pathwidth(k=6, certificate=True) (True, Graph on 5 vertices)
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> g.pathwidth() 5 >>> g.pathwidth(k=Integer(2)) False >>> g.pathwidth(k=Integer(6)) True >>> g.pathwidth(k=Integer(6), certificate=True) (True, Graph on 5 vertices)
 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, solver=None, integrality_tolerance=0.001)[source]#
Return an optimal ordering of the vertices and its cost for vertexseparation.
INPUT:
G
– a Graph or a DiGraphalgorithm
– string (default:"BAB"
); algorithm to use among:"BAB"
– Use a branchandbound 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
– integer (default:None
); parameter 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
– integer (default:None
); parameter 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 (default:False
); whether to display information on the computationsmax_prefix_length
– integer (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
– integer (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"
.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
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: # needs sage.combinat 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 # needs sage.numerical.mip 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 # needs sage.numerical.mip 3
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import vertex_separation >>> # needs sage.combinat >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> vs,L = vertex_separation(G, algorithm="BAB"); vs 2 >>> vs,L = vertex_separation(G, algorithm="exponential"); vs 2 >>> vs,L = vertex_separation(G, algorithm="MILP"); vs # needs sage.numerical.mip 2 >>> G = graphs.Grid2dGraph(Integer(3),Integer(3)) >>> vs,L = vertex_separation(G, algorithm="BAB"); vs 3 >>> vs,L = vertex_separation(G, algorithm="exponential"); vs 3 >>> vs,L = vertex_separation(G, algorithm="MILP"); vs # needs sage.numerical.mip 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 = digraphs.RandomDirectedAcyclicGraph(10, .5) 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, [10, 11, 8, 9, 4, 5, 6, 7, 0, 1, 2, 3])
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import vertex_separation >>> D = digraphs.Path(Integer(8)) >>> print(vertex_separation(D)) (0, [7, 6, 5, 4, 3, 2, 1, 0]) >>> D = digraphs.RandomDirectedAcyclicGraph(Integer(10), RealNumber('.5')) >>> vs,L = vertex_separation(D); vs 0 >>> K4 = DiGraph( graphs.CompleteGraph(Integer(4)) ) >>> D = K4+K4 >>> D.add_edge(Integer(0), Integer(4)) >>> print(vertex_separation(D)) (3, [4, 5, 6, 7, 0, 1, 2, 3]) >>> D = K4+K4+K4 >>> D.add_edge(Integer(0), Integer(4)) >>> D.add_edge(Integer(0), Integer(8)) >>> print(vertex_separation(D)) (3, [10, 11, 8, 9, 4, 5, 6, 7, 0, 1, 2, 3])
Using a specific MILP solver:
sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation sage: G = graphs.PetersenGraph() sage: vs, L = vertex_separation(G, algorithm="MILP", solver="SCIP"); vs # optional  pyscipopt, needs sage.numerical.mip 5
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import vertex_separation >>> G = graphs.PetersenGraph() >>> vs, L = vertex_separation(G, algorithm="MILP", solver="SCIP"); vs # optional  pyscipopt, needs sage.numerical.mip 5
 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)[source]#
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 [CMN2014]. 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
– integer (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
– integer (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
– integer (default: 20); limits the length of the stored prefixes to prevent storing too many prefixesmax_prefix_number
– integer (default: 10**6); upper bound on the number of stored prefixes used to prevent using too much memoryverbose
– boolean (default:False
); display some information when set toTrue
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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> D = digraphs.RandomDirectedGNP(Integer(15), RealNumber('.2')) >>> vb, seqb = VS.vertex_separation_BAB(D) >>> vd, seqd = VS.vertex_separation_exp(D) >>> vb == vd True >>> vb == VS.width_of_path_decomposition(D, seqb) True
The vertex separation of a \(N\times N\) grid is \(N\):
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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.Grid2dGraph(Integer(4),Integer(4)) >>> vs, seq = VS.vertex_separation_BAB(G); vs 4 >>> vs == VS.width_of_path_decomposition(G, seq) True
The vertex separation of a \(N\times M\) grid with \(N<M\) is \(N\):
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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.Grid2dGraph(Integer(3),Integer(5)) >>> vs, seq = VS.vertex_separation_BAB(G); vs 3 >>> vs == VS.width_of_path_decomposition(G, seq) True
The vertex separation of circuit of order \(N\geq 2\) 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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> D = digraphs.Circuit(Integer(10)) >>> vs, seq = VS.vertex_separation_BAB(D); vs 1 >>> vs == VS.width_of_path_decomposition(D, seq) True
The vertex separation of cycle of order \(N\geq 3\) 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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.CycleGraph(Integer(10)) >>> 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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.MycielskiGraph(Integer(5)) >>> 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.vertex_separation_BAB(G, cut_off=11)[0] <= 11 True sage: VS.vertex_separation_BAB(G, cut_off=10)[0] <= 10 True sage: VS.vertex_separation_BAB(G, cut_off=9)[0] <= 9 False
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.MycielskiGraph(Integer(5)) >>> VS.vertex_separation_BAB(G, cut_off=Integer(11))[Integer(0)] <= Integer(11) True >>> VS.vertex_separation_BAB(G, cut_off=Integer(10))[Integer(0)] <= Integer(10) True >>> VS.vertex_separation_BAB(G, cut_off=Integer(9))[Integer(0)] <= Integer(9) False
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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.MycielskiGraph(Integer(5)) >>> vs, seq = VS.vertex_separation_BAB(G, upper_bound=Integer(11)); vs 10 >>> vs, seq = VS.vertex_separation_BAB(G, upper_bound=Integer(10)); vs 1 >>> vs, seq = VS.vertex_separation_BAB(G, cut_off=Integer(11), upper_bound=Integer(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
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation as VS >>> G = graphs.MycielskiGraph(Integer(5)) >>> vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=Integer(0)); vs 10 >>> vs, seq = VS.vertex_separation_BAB(G, max_prefix_number=Integer(5)); vs 10 >>> vs, seq = VS.vertex_separation_BAB(G, max_prefix_number=Integer(0)); vs 10
 sage.graphs.graph_decompositions.vertex_separation.vertex_separation_MILP(G, integrality=False, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute the vertex separation of \(G\) 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 \(G\). This MILP is an improved version of the formulation proposed in [SP2010]. See the
module's documentation
for more details on this MILP formulation.INPUT:
G
– a Graph or a DiGraphintegrality
– boolean (default:False
); specify if variables \(x_v^t\) and \(u_v^t\) 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
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
OUTPUT:
A pair
(cost, ordering)
representing the optimal ordering of the vertices and its cost.EXAMPLES:
Vertex separation of a De Bruijn digraph:
sage: # needs sage.combinat 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 # needs sage.numerical.mip 2 sage: vs == vertex_separation.width_of_path_decomposition(G, L) # needs sage.numerical.mip True sage: vse, Le = vertex_separation.vertex_separation(G); vse 2
>>> from sage.all import * >>> # needs sage.combinat >>> from sage.graphs.graph_decompositions import vertex_separation >>> G = digraphs.DeBruijn(Integer(2),Integer(3)) >>> vs, L = vertex_separation.vertex_separation_MILP(G); vs # needs sage.numerical.mip 2 >>> vs == vertex_separation.width_of_path_decomposition(G, L) # needs sage.numerical.mip True >>> 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 # needs sage.numerical.mip 1
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation >>> G = digraphs.Circuit(Integer(6)) >>> vs, L = vertex_separation.vertex_separation_MILP(G); vs # needs sage.numerical.mip 1
 sage.graphs.graph_decompositions.vertex_separation.vertex_separation_exp(G, verbose=False)[source]#
Return an optimal ordering of the vertices and its cost for vertexseparation.
INPUT:
G
– a Graph or a DiGraphverbose
– boolean (default:False
); 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.
EXAMPLES:
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])
>>> from sage.all import * >>> from sage.graphs.graph_decompositions.vertex_separation import vertex_separation_exp >>> g = digraphs.Circuit(Integer(6)) >>> vertex_separation_exp(g) (1, [0, 1, 2, 3, 4, 5])
 sage.graphs.graph_decompositions.vertex_separation.width_of_path_decomposition(G, L)[source]#
Return the width of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\).
If \(G\) is an instance of
Graph
, this function returns the width \(pw_L(G)\) of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\). If \(G\) is aDiGraph
, it returns instead the width \(vs_L(G)\) of the directed path decomposition induced by the linear ordering \(L\) of the vertices of \(G\), where\[\begin{split}vs_L(G) & = \max_{0\leq i< V1}  N^+(L[:i])\setminus L[:i] \\ pw_L(G) & = \max_{0\leq i< V1}  N(L[:i])\setminus L[:i] \\\end{split}\]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 = G.vertices(sort=True) sage: vertex_separation.width_of_path_decomposition(G, L) 2
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation >>> G = graphs.CycleGraph(Integer(6)) >>> L = G.vertices(sort=True) >>> 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 = G.vertices(sort=True) sage: vertex_separation.width_of_path_decomposition(G, L) 1
>>> from sage.all import * >>> from sage.graphs.graph_decompositions import vertex_separation >>> G = digraphs.Circuit(Integer(6)) >>> L = G.vertices(sort=True) >>> vertex_separation.width_of_path_decomposition(G, L) 1