Ask Your Question
3

Random orientation of a graph

asked 2018-05-07 02:36:46 +0100

standardtrickyness gravatar image

updated 2019-08-29 18:20:29 +0100

FrédéricC gravatar image

Is there a command to randomly orient a graph? (no additional edges) not the to_directed command

edit retag flag offensive close merge delete

Comments

Congratulations for asking this question.

Adding such a method to Sage is now tracked at Sage trac ticket #25303: Random orientation of a graph.

slelievre gravatar imageslelievre ( 2018-05-07 18:39:52 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2018-05-07 08:00:28 +0100

slelievre gravatar image

updated 2018-05-07 16:38:36 +0100

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

For example, starting from the Petersen graph:

sage: G = 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()]))
edit flag offensive delete link more

Comments

Note: a better implementation based on this proof of concept is proposed at

slelievre gravatar imageslelievre ( 2018-05-07 18:41:52 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-05-07 02:36:46 +0100

Seen: 392 times

Last updated: May 07 '18