Orientations¶
Enumerating \(k\)connected orientations
This module is the code implemented in [TYT] based of the graph work on enumerating \(k\)connected orientations by [SKP].
References¶
[SKP]  Sarah Blind, Kolja Knauer, Petru Valicov Enumerating karcconnected orientations. https://arxiv.org/abs/1908.02050 
[TYT]  Taras Yarema Enumerating kconnected orientations. Degree thesis, University of Barcelona, 2021. 
This module contains the following main methods
orientation() 
Computes a \(k\)connected orientation of \(G\). 
k_orientations_iterator() 
Returns an iterator over all \(k\)connected orientations of \(G\). 
The following are helper functions that are exported
subdivide() 
Transform a multigraph into a simple graph 
gomory_hu_tree() 
GomoryHu tree implementation with multigraph support 
local_connectivity() 
Compute the min. edge label of a \(uv\) path 
connectivity() 
Edgeconnectivity of a undirected multigraph \(G\) 
splitting_off_to_capacity() 
Splitoff to capacity an edge pair 
complete_splitting_off() 
Efficient complete splittingoff at \(x\) 
lovasz_decomposition() 
Lovasz decomposition of \(G\) 
alpha_orientations_iterator() 
Iterator over all \(\alpha\)orientations 
outdegree_sequence_iterator() 
Iterator over all \(k\)connected outdegree sequences 
Authors¶
 Taras Yarema (20210124) – initial version
Methods¶

orientations.
subdivide
(G)¶ Subdivides the multigraph \(G\) such that the resulting graph preserves connectivity and it’s not multiedged.
INPUT:
 \(G\) – a Graph that may have multiple edges.
OUTPUT: \((H, C)\) where \(H\) is the subdivided graph version of \(G\) and \(C\) is the list of added vertices.
EXAMPLES:
Simple usage for a graph formed by two vertices and a double edge between:
sage: from orientations import subdivide sage: g = Graph({0: [1, 1]}) sage: h, added = subdivide(g) sage: added [2, 3] sage: h.edges() [(0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None)]
TEST:
sage: H, C = subdivide(graphs.CompleteGraph(5)) sage: len(C) 0 sage: H == graphs.CompleteGraph(5) True
Given a multigraph with two vertices and \(n\) edges between them, the subdivided graph should have \(2 + n\) vertices \(2n\) edges. Also we should be able to make the graph simple:
sage: for n in range(2, 11): ....: u, v = 0, 1 ....: edges = [(u, v) for _ in range(n)] ....: g = Graph({u: [v for _ in range(n)]}) ....: assert len(g) == 2 ....: assert len(g.edges()) == n ....: new_g, added = subdivide(g) ....: assert len(new_g) == 2 + n ....: assert len(new_g.edges()) == 2 * n ....: assert len(added) == n ....: assert added == [i for i in range(2, n+2)] ....: new_g.allow_multiple_edges(True) ....: for added_v in added: ....: assert new_g.has_edge(u, added_v) ....: assert new_g.has_edge(added_v, v)

orientations.
gomory_hu_tree
(G, added=None)¶ Computes the GomoryHu tree representation of an undirected multigraph G.
INPUT:
 \(G\) – a Graph that may have multiple edges.
OUTPUT: \(T\) a GomoryHu representation of \(G\).
EXAMPLES:
Example usage:
sage: from orientations import gomory_hu_tree sage: g = graphs.PetersenGraph() sage: g.allow_multiple_edges(True) sage: for edge in g.edges(): ....: g.add_edge(edge) sage: ght = gomory_hu_tree(g) sage: ght.is_tree() True sage: min(ght.edge_labels()) 6
TEST:
First of all, let’s make sure that the implementation is consistent with the existing when the graph is simple:
sage: for n in range(3, 10): ....: g = graphs.CompleteGraph(n) ....: assert gomory_hu_tree(g) == g.gomory_hu_tree()
If the given graph is multiedged it should handle this correctly and keep edgeconnectivity. We will then add 5 new edges and it should make the \(\lambda_G'(u, v) = \lambda_G(u, v) + 1\):
sage: g = graphs.CompleteGraph(5) sage: k = g.edge_connectivity() sage: g.allow_multiple_edges(True) sage: for u, v, _ in g.edges()[:5]: ....: g.add_edge(u, v, None) sage: t = gomory_hu_tree(g) sage: new_k = min(w for _, _, w in t.edges()) sage: assert new_k == k + 1

orientations.
local_connectivity
(T, u, v)¶ Computes the minimum label of the \(uv\) path in \(T\). As \(T\) is a GomoryHu tree representation of some \(G\) this label is the value of the \(uv\) cut.
INPUT:
 \(T\) – a GomoryHu tree.
 \(u\) – a vertex of \(T\).
 \(v\) – a vertex of \(T\).
OUTPUT: The local edgeconnectivity between \(u\) and \(v\).
EXAMPLES:
Example usage:
sage: from orientations import local_connectivity
TEST:
sage: g = graphs.CompleteGraph(7) sage: t = g.gomory_hu_tree() sage: all_pairs = Subsets(g.vertices(), 2) sage: assert all(local_connectivity(t, u, v) == 6 \ for u, v in all_pairs)
For a \(K(n)\) we have that \(\lambda(u, v) = n  1\), for all pairs \(u, v\):
sage: g = graphs.CompleteGraph(7) sage: for u in g: ....: for v in g: ....: if u == v: ....: continue ....: assert len(g.edge_disjoint_paths(u, v)) == 6
We now check that for all pairs \({u, v}\) the local edgeconnectivity is at least \(n\):
sage: g = graphs.CompleteGraph(7) sage: g.allow_multiple_edges(True) sage: for u, v, _ in g.edges()[:7]: ....: g.add_edge(u, v, None) sage: from orientations import gomory_hu_tree sage: t = gomory_hu_tree(g) sage: for u in t: ....: for v in t: ....: if u == v: ....: continue ....: current = local_connectivity(t, u, v) ....: assert current >= 7

orientations.
connectivity
(G, indicator=None)¶ Computes the local edgeconnectivity of an undirected multigraph \(G\).
INPUT:
 \(G\) – a Graph.
OUTPUT: The edgeconnectivity of \(G\).
EXAMPLES:
We will mymic the Sage edge_connectivity examples.
A basic application on the PappusGraph:
sage: from orientations import connectivity sage: g = graphs.PappusGraph() sage: g.edge_connectivity() 3 sage: connectivity(g) 3
Even if obviously in any graph we know that the edge connectivity is less than the minimum degree of the graph:
sage: g = graphs.RandomGNP(10,.3) sage: assert min(g.degree()) >= connectivity(g)
TEST:
sage: g = graphs.CompleteGraph(7) sage: assert connectivity(g) == 6

orientations.
splitting_off_to_capacity
(g, x, indicator, req, candidates=None, verbose=False)¶ Attempt to do a splittingoff to capacity at the vertex \(x\) in \(G\), such that it preserves the edgeconnectivity requirements defined by req. The indicator is the a vertex of \(G\). If the candidates are given the splittingoff is attempted with them.
INPUT:
 \(G\) – a Graph.
 \(x\) – the vertex to splitoff.
 \(indicator\) – a vertex.
 \(candidates\) – a pair of neighbors of \(x\).
 \(verbose\) – if the users wants debugging output.
OUTPUT: The capacity of the splitting off.
EXAMPLES:
Example usage:
sage: from orientations import splitting_off_to_capacity
TEST:
The initial connectivity of g will be the requirement, i.e. its global. We splitoff to capacity the vertex 1 and pick 4 as indicator. We could pick any vertex (non x) as indicator, as the requirement is global. We will then compute the minimum local edgeconnectivity of the resulting graph via all vertex pairs that do not contain \(x\):
sage: from orientations import connectivity sage: g = Graph({1: [2, 2, 2, 2, 3, 3, 3], 4: [2, 2, 3, 3]}) sage: req = connectivity(g) sage: x, indicator = 1, 4 sage: cap = splitting_off_to_capacity(g, x, indicator, \ req, candidates=(2, 3)) sage: for _ in range(cap): ....: g.delete_edges([(1, 2), (1, 3)]) ....: g.add_edge(2, 3) sage: from orientations import gomory_hu_tree sage: t = gomory_hu_tree(g) sage: after_conn = None sage: from orientations import local_connectivity sage: for u in g: ....: for v in g: ....: if u == v or x in (u, v): ....: continue ....: l_conn = local_connectivity(t, u, v) ....: if after_conn is None or l_conn <= after_conn: ....: after_conn = l_conn sage: assert req == after_conn

orientations.
complete_splitting_off
(G, x, req, verbose=False, iter_max=1000)¶ Computes the complete splittingoff sequence of \(x\) in \(G\), such that it preserves the global edgeconnectivity requirement.
INPUT:
 \(G\) – a Graph.
 \(x\) – the vertex to splitoff.
 \(req\) – the global edgeconnectivity requirement.
 \(verbose\) – if the user wants debugging output.
OUTPUT: \((C, A, R)\) where \(A\) is a list with the added edges and \(R\) the removed ones.
EXAMPLES:
Example usage:
sage: from orientations import complete_splitting_off
TEST:
We know that, for even n, all vertices at \(g = K(n)\) have degree \(n  1\). If we pick \(k = (n  1) // 2\), then we know that \(g\) has a vertex of degree \(2k\) and hence can compute a complete splittingoff in it:
sage: g = graphs.CompleteGraph(5) sage: req = g.edge_connectivity() sage: g.allow_multiple_edges(True) sage: x = g.vertices()[0] sage: _ = complete_splitting_off(g, x, req)
Finally, we check that the edgeconnectivity requirement after the complete splittingoff is preserved:
sage: from orientations import connectivity sage: after_conn = connectivity(g) sage: assert req == after_conn

orientations.
lovasz_decomposition
(G, req, verbose=False)¶ Consider that the given requirement is of the form \(2k\) for some \(k \geq 1\). Then this function computes the decomposition of a the \(2k\)connected graph \(G\) into a pair of vertices and \(2k\) edges connecting them.
INPUT:
 \(G\) – a Graph.
 \(req\) – the global edgeconnectivity requirement.
 \(verbose\) – if the user wants debugging output.
OUTPUT: \((H, (A, R))\) where \(H\) is a Graph with only a pair of vertices and \(req\) edges connecting them.
EXAMPLES:
Example usage:
sage: from orientations import lovasz_decomposition
TEST:
We know that, for even n, all vertices at \(g = K(n)\) have edgeconnectivity \(n  1\). Hencem the decomposed graph should have \(n  1\) edges between the two vertice:
sage: g = graphs.CompleteGraph(7) sage: g.allow_multiple_edges(True) sage: req, k = 6, 3
By the Lovasz decomposition Theorem, h should have 2 vertices and 2k edges connecting those vertices:
sage: h, _ = lovasz_decomposition(g, 6) sage: assert len(h) == 2 and len(h.edges()) == 2 * k

orientations.
orientation
(G, k, verbose=False)¶ Computes an arbitrary \(k\)connected orientation of the graph \(G\).
INPUT:
 \(G\) – a Graph.
 \(k\) – the wanted connectivity.
 \(verbose\) – if the user wants debugging output.
OUTPUT: A \(k\)connected orientation of \(G\).
EXAMPLES:
Example usage:
sage: from orientations import orientation
TEST:
We know that, for even n, all vertices at \(g = K(n)\) have edgeconnectivity \(n  1\):
sage: g = graphs.CompleteGraph(7) sage: g.allow_multiple_edges(True) sage: req, k = 6, 3
Now let’s actually generate a \(k\)connected orientation of \(g\):
sage: ori = orientation(g.copy(), k)
The following properties should be true: 1. The undirected version of ori should be g 2. ori should be kconnected:
sage: assert ori.to_undirected() == g
An orientation of \(K_n\) should not have multiple edges:
sage: assert ori.has_multiple_edges() == False sage: ori.allow_multiple_edges(False) sage: assert ori.edge_connectivity() == k

orientations.
alpha_orientations_iterator
(D, F=[], verbose=False)¶ Return an iterator over all \(\alpha\)orientations of \(D\).
INPUT:
 \(D\) – a DiGraph.
 \(F\) – a set of vertices.
 \(verbose\) – if the user wants debugging output.
OUTPUT: An iterator.
EXAMPLES:
Example usage:
sage: from orientations import alpha_orientations_iterator
TEST:

orientations.
outdegree_sequence_iterator
(D, F, req, verbose=False)¶ Return an iterator over all \(k\)connected orientations of \(D\).
INPUT:
 \(D\) – a DiGraph.
 \(F\) – a set.
 \(req\) – the edgeconnectivity requirement, \(k\).
 \(verbose\) – if the user wants debugging output.
OUTPUT: An iterator.
EXAMPLES:
Example usage:
sage: from orientations import outdegree_sequence_iterator
TEST:

orientations.
k_orientations_iterator
(G, k, verbose=False)¶ Return an iterator over all \(k\)connected orientations of an undirected multigraph \(G\).
INPUT:
 \(G\) – a Graph, which may have multiple edges.
 \(k\) – the wanted connectivity of the orientations.
 \(verbose\) – if the user wants debugging output.
OUTPUT: An iterator over all \(k\)connected orientations of \(G\).
EXAMPLES:
If \(k = 1\) we get the same results as the strong orientations iterator, but we need to multiply by two as it does not consider reflections:
sage: from orientations import k_orientations_iterator sage: from sage.graphs.orientations import strong_orientations_iterator sage: pet = graphs.PetersenGraph() sage: strong = len(list(strong_orientations_iterator(pet))) * 2 sage: strong 1920 sage: new = len(list(k_orientations_iterator(pet, 1))) sage: assert strong == new
We can compute how many 2connected have the Harary \(H_{4,7}\) graph:
sage: h = graphs.HararyGraph(4, 7) sage: len(list(k_orientations_iterator(h, 2))) 60
TEST:
For k = 1 we should get the same result as the native strong orientations iterator from Sage:
sage: for n in (3, 5): ....: g = graphs.CompleteGraph(n) ....: new = len(list(k_orientations_iterator(g, 1))) ....: strong = len(list(strong_orientations_iterator(g))) * 2 ....: assert new == strong
Now let’s test for some random graphs with known connectivities:
sage: query = GraphQuery( ....: display_cols=['num_vertices', 'edge_connectivity'], ....: edge_connectivity=['=', 4], ....: num_vertices=['<', 7], ....: num_edges=['<', 15], ....: ) sage: items = query.get_graphs_list() sage: for item in items[:3]: ....: g = item.copy() ....: g.allow_multiple_edges(True) ....: got_1, got_2 = 0, 0 ....: for ori in strong_orientations_iterator(g): ....: got_1 += 1 ....: if ori.edge_connectivity() == 2: ....: got_2 += 1 ....: got_1 *= 2 ....: got_2 *= 2 ....: want_1 = len(list(k_orientations_iterator(g.copy(), 1))) ....: want_2 = len(list(k_orientations_iterator(g.copy(), 2))) ....: assert got_1 == want_1 and got_2 == want_2
We know that this graph has 3842 2connected orientations (see Conclusions arXiv:1908.02050):
sage: g1 = { ....: 1: [2, 3, 8, 9], ....: 2: [3, 4, 8], ....: 3: [4, 9], ....: 4: [5, 6, 8, 9], ....: 5: [6, 7, 8], ....: 6: [7, 9], ....: 7: [8, 9], ....: 8: [9], ....: } sage: oris = len(list(k_orientations_iterator(Graph(g1), 2))) sage: assert oris == 3842