Revision history [back]

Picking each edge and applying a random orientation is a one-liner.

Let us take the example of the Petersen graph.

sage: G = graphs.PetersenGraph()
sage: G
Petersen graph: Graph on 10 vertices

Here is how to obtain the edges of G

sage: G.edges(labels=False)
[(0, 1),
 (0, 4),
 (0, 5),
 (1, 2),
 (1, 6),
 (2, 3),
 (2, 7),
 (3, 4),
 (3, 8),
 (4, 9),
 (5, 7),
 (5, 8),
 (6, 8),
 (6, 9),
 (7, 9)]

Now we build a directed graph, running through the edges of G and picking a random orientation for each.

sage: DiGraph([(a, b) if randint(0, 1) else (b, a) for (a, b) in G.edges(labels=False)])
Digraph on 10 vertices

sage: DiGraph([e if randint(0, 1) else e[::-1] for e in G.edges(labels=False)])
Digraph on 10 vertices

Picking each edge and applying a random orientation is a one-liner.

Let us take the example of For example, starting from the Petersen graph.graph:

sage: G = graphs.PetersenGraph()
sage: PetersenGraph(); G
Petersen graph: Graph on 10 vertices

Here is how we can apply a random orientation to obtain the edges of Geach edge:

sage: G.edges(labels=False)
[(0, 1),
 (0, 4),
 (0, 5),
 (1, 2),
 (1, 6),
 (2, 3),
 (2, 7),
 (3, 4),
 (3, 8),
 (4, 9),
 (5, 7),
 (5, 8),
 (6, 8),
 (6, 9),
 (7, 9)]

Now we build a directed graph, running through the edges of G and picking a random orientation for each.

sage: GG = DiGraph([(a, b) b, c) if randint(0, 1) else (b, a) a, c) for (a, b) b, c) in G.edges(labels=False)])
Digraph on 10 vertices

sage: DiGraph([e if randint(0, 1) else e[::-1] for e in G.edges(labels=False)])
G.edge_iterator()]); GG
Digraph on 10 vertices

def orient_edge_at_random((a, b, c)):
    r"""
    Return this edge with a random orientation

    An edge consists of a start vertex, end vertex, and a label.
    At random, we switch the start vertex and the end vertex.

    EXAMPLE::

        sage: orient_edge_at_random((0, 1, None)) # random
        (0, 1, None)
        sage: orient_edge_at_random((0, 1, None)) # random
        (1, 0, None)
    """
    if randint(0, 1):
        return(a, b, c)
    return(b, a, c)

def random_orientation_digraph(G):
    r"""
    Return a directed graph built from this undirected graph

    The edges of the directed graph will be the edges of the undirected
    graph, each of them being assigned an orientation at random.

    EXAMPLE::

        sage: G = graphs.PetersenGraph(); G
        Petersen graph: Graph on 10 vertices
        sage: edges = G.edge_iterator(labels=False)
        sage: random_orientation_digraph(G)
        Digraph on 10 vertices
    """
    return(DiGraph([orient_edge_at_random(e) for e in G.edge_iterator()]))

Picking each edge and applying a random orientation is a one-liner.

For example, starting from the Petersen graph:

sage: G = PetersenGraph(); G
Petersen graph: Graph on 10 vertices

we can apply a random orientation to each edge:

sage: GG = DiGraph([(a, b, c) if randint(0, 1) else (b, a, c) for (a, a, b, c) c in G.edge_iterator()]); GG
G.edge_iterator()])
Digraph on 10 vertices

To make reuse easier, we write a function to orient an edge at random as follows:

def orient_edge_at_random((a, b, c)):
    r"""
    Return this edge with a random orientation

    An edge consists of a start vertex, end vertex, and a label.
    At random, we switch the start vertex and the end vertex.

    EXAMPLE::

        sage: orient_edge_at_random((0, 1, None)) # random
        (0, 1, None)
        sage: orient_edge_at_random((0, 1, None)) # random
        (1, 0, None)
    """
    if randint(0, 1):
        return(a, b, c)
    return(b, a, c)

and a function to orient all edges of an unoriented graph at random as follows:

def random_orientation_digraph(G):
    r"""
    Return a directed graph built from this undirected graph

    The edges of the directed graph will be the edges of the undirected
    graph, each of them being assigned an orientation at random.

    EXAMPLE::

        sage: G = graphs.PetersenGraph(); G
        Petersen graph: Graph on 10 vertices
        sage: edges = G.edge_iterator(labels=False)
        sage: random_orientation_digraph(G)
        Digraph on 10 vertices
    """
    return(DiGraph([orient_edge_at_random(e) for e in G.edge_iterator()]))

Picking each edge and applying a random orientation is a one-liner.

For example, starting from the Petersen graph:

sage: G = PetersenGraph(); graphs.PetersenGraph(); G
Petersen graph: Graph on 10 vertices

we can apply a random orientation to each edge:

sage: DiGraph([(a, b, c) if randint(0, 1) else (b, a, c) for a, b, c in G.edge_iterator()])
Digraph on 10 vertices

To make reuse easier, we write a function to orient an edge at random as follows:

def orient_edge_at_random((a, b, c)):
    r"""
    Return this edge with a random orientation

    An edge consists of a start vertex, end vertex, and a label.
    At random, we switch the start vertex and the end vertex.

    EXAMPLE::

        sage: orient_edge_at_random((0, 1, None)) # random
        (0, 1, None)
        sage: orient_edge_at_random((0, 1, None)) # random
        (1, 0, None)
    """
    if randint(0, 1):
        return(a, b, c)
    return(b, a, c)

and a function to orient all edges of an unoriented graph at random as follows:

def random_orientation_digraph(G):
    r"""
    Return a directed graph built from this undirected graph

    The edges of the directed graph will be the edges of the undirected
    graph, each of them being assigned an orientation at random.

    EXAMPLE::

        sage: G = graphs.PetersenGraph(); G
        Petersen graph: Graph on 10 vertices
        sage: edges = G.edge_iterator(labels=False)
        sage: random_orientation_digraph(G)
        Digraph on 10 vertices
    """
    return(DiGraph([orient_edge_at_random(e) for e in G.edge_iterator()]))