`orientations` package demo¶

In [1]:

from orientations import *

Computing an arbitrary $k$-connected orientations¶

Now we will show how to, given an undirected Sage graph $G$, compute an arbitrary $k$-connected orientation of it.

In [2]:

k, v = 3, 9
g = graphs.HararyGraph(2 * k, 9)
g.allow_multiple_edges(True)

ori = orientation(g, k)

# We can check the actual orientation
# is actually an orientation
assert ori.to_undirected() == g

assert ori.has_multiple_edges() == False
ori.allow_multiple_edges(False)

# We can check also that the actual
# connectivity of the orientation is correct
assert ori.edge_connectivity() == k

ori.plot(layout='circular').show()

Enumerating $k$-connected orientations¶

Now we will show how to compute all the $k$-connected orientations of a given graph.

In [3]:

g = Graph({
    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],
})

# Plot the vertices in pre-defined coordinated
positions = {
    1: [0, +2],
    2: [-0.5, 0.75],
    3: [+0.5, 0.75],
    4: [0, 0],
    5: [-0.5, -0.75],
    6: [+0.5, -0.75],
    7: [0, -1.5],
    8: [-4, -2],
    9: [+4, -2],
}

g.plot(pos=positions).show()

# This may take a few seconds (~7s)
oris = list(k_orientations_iterator(g, 2))

# We can check that the number of orientations is correct
assert len(oris) == 3842

oris[0].plot(pos=positions).show()

In [ ]:

orientations package demo¶

Computing an arbitrary $k$-connected orientations¶

Enumerating $k$-connected orientations¶

`orientations` package demo¶