ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 07 May 2018 11:41:52 -0500Random orientation of a graphhttp://ask.sagemath.org/question/42274/random-orientation-of-a-graph/ Is there a command to randomly orient a graph? (no additional edges) not the to_directed commandSun, 06 May 2018 19:36:46 -0500http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/Comment by slelievre for <p>Is there a command to randomly orient a graph? (no additional edges) not the to_directed command</p>
http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?comment=42286#post-id-42286Congratulations for asking this question.
Adding such a method to Sage is now tracked at
[Sage trac ticket #25303: Random orientation of a graph](https://trac.sagemath.org/ticket/25303).Mon, 07 May 2018 11:39:52 -0500http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?comment=42286#post-id-42286Answer by slelievre for <p>Is there a command to randomly orient a graph? (no additional edges) not the to_directed command</p>
http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?answer=42279#post-id-42279Picking 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()]))Mon, 07 May 2018 01:00:28 -0500http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?answer=42279#post-id-42279Comment by slelievre for <p>Picking each edge and applying a random orientation is a one-liner.</p>
<p>For example, starting from the Petersen graph:</p>
<pre><code>sage: G = graphs.PetersenGraph(); G
Petersen graph: Graph on 10 vertices
</code></pre>
<p>we can apply a random orientation to each edge:</p>
<pre><code>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
</code></pre>
<p>To make reuse easier, we write a function to orient an edge at random as follows:</p>
<pre><code>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)
</code></pre>
<p>and a function to orient all edges of an unoriented graph at random as follows:</p>
<pre><code>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()]))
</code></pre>
http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?comment=42287#post-id-42287Note: a better implementation based on this proof of concept is proposed at
- [Sage trac ticket #25303: Random orientation of a graph](https://trac.sagemath.org/ticket/25303)Mon, 07 May 2018 11:41:52 -0500http://ask.sagemath.org/question/42274/random-orientation-of-a-graph/?comment=42287#post-id-42287