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 k-arc-connected orientations. https://arxiv.org/abs/1908.02050 |
[TYT] | Taras Yarema Enumerating k-connected 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 multi-graph into a simple graph |
gomory_hu_tree() |
Gomory-Hu tree implementation with multi-graph support |
local_connectivity() |
Compute the min. edge label of a \(u-v\) path |
connectivity() |
Edge-connectivity of a undirected multi-graph \(G\) |
splitting_off_to_capacity() |
Split-off to capacity an edge pair |
complete_splitting_off() |
Efficient complete splitting-off 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 (2021-01-24) – initial version
Methods¶
-
orientations.
subdivide
(G)¶ Subdivides the multi-graph \(G\) such that the resulting graph preserves connectivity and it’s not multi-edged.
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 multi-graph 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 Gomory-Hu tree representation of an undirected multi-graph G.
INPUT:
- \(G\) – a Graph that may have multiple edges.
OUTPUT: \(T\) a Gomory-Hu 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 edge-connectivity. 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 \(u-v\) path in \(T\). As \(T\) is a Gomory-Hu tree representation of some \(G\) this label is the value of the \(u-v\) cut.
INPUT:
- \(T\) – a Gomory-Hu tree.
- \(u\) – a vertex of \(T\).
- \(v\) – a vertex of \(T\).
OUTPUT: The local edge-connectivity 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 edge-connectivity 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 edge-connectivity of an undirected multi-graph \(G\).
INPUT:
- \(G\) – a Graph.
OUTPUT: The edge-connectivity 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 splitting-off to capacity at the vertex \(x\) in \(G\), such that it preserves the edge-connectivity requirements defined by req. The indicator is the a vertex of \(G\). If the candidates are given the splitting-off is attempted with them.
INPUT:
- \(G\) – a Graph.
- \(x\) – the vertex to split-off.
- \(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 split-off 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 edge-connectivity 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 splitting-off sequence of \(x\) in \(G\), such that it preserves the global edge-connectivity requirement.
INPUT:
- \(G\) – a Graph.
- \(x\) – the vertex to split-off.
- \(req\) – the global edge-connectivity 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 splitting-off 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 edge-connectivity requirement after the complete splitting-off 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 edge-connectivity 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 edge-connectivity \(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 edge-connectivity \(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 k-connected:
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 edge-connectivity 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 multi-graph \(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 2-connected 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 2-connected 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