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