Make undirected graph directed

Question

I've got a undirected, complete graph and would like to convert it to a directed acyclic graph with a (unidirectional) path between each node. To start off, I want to add random edges and stop once all nodes are connected. What would be an algorithm to look at (using Python, but any language will do).

So for instance this graph, does not to be connected any further:

A  ---- B            A ---> B
 \     /      =>           /
  \   /                   v
    C                    C

, but in this case, all undirected edges turn into a directed edge

A  ---- B            A ---> B
 \     /      =>      ^     ^
  \   /                \   /
    C                    C

Update

Note that the aim is to convert an undirected graph into a directed graph as per the above constraints. Like for a spanning tree, there are more than 1 solutions to this conversion process (as shown in above example).

I have a tutorial for you my friend :) networkx.github.io/documentation/latest/tutorial It may take a bit to get into the package.. but it can do excatly what you want.. Use the random module to add edge directions and we have a party.. good luck.. — brunsgaard
Actually, I'm using networkx. I'll follow up your link - thanks. — orange
@brunsgaard Any particular function you're recommending for this? — orange

Gene Gene · Accepted Answer · 2014-10-08T19:31:43

You need a directed spanning tree.

It's easy to find a directed spanning tree in an undirected graph. Just do depth-first-search, ignoring back and cross edges. The edges you actually traverse form a directed tree that touches every node in each connected component.

However you have added the restriction that you want edge choice to be random.

So for this you can use a Minimum Spanning Tree algorithm like Kruskal's algorithm with random edge weights.

Note there is no reason to actually store and compute random edge weights. The first step of the algorithm is to sort by weight. So replace this sort by a random permutation of the edges, and you're in business.

Make undirected graph directed

1 Answers