# 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].

## 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()
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: ,
....: }
sage: oris = len(list(k_orientations_iterator(Graph(g1), 2)))
sage: assert oris == 3842