python - Make undirected graph directed -

python - Make undirected graph directed -

i've got undirected, finish graph , convert directed acyclic graph (unidirectional) path between each node. start off, want add together random edges , stop 1 time nodes connected. algorithm @ (using python, language do).

so instance graph, not connected further:

a ---- b ---> b \ / => / \ / v c c

, in case, undirected edges turn directed edge

a ---- b ---> b \ / => ^ ^ \ / \ / c c

update

note aim convert undirected graph directed graph per above constraints. spanning tree, there more 1 solutions conversion process (as shown in above example).

you need directed spanning tree.

it's easy find directed spanning tree in undirected graph. depth-first-search, ignoring , cross edges. edges traverse form directed tree touches every node in each connected component.

however have added restriction want border selection random.

so can utilize minimum spanning tree algorithm kruskal's algorithm random border weights.

note there no reason store , compute random border weights. first step of algorithm sort weight. replace sort random permutation of edges, , you're in business.

python graph directed-acyclic-graphs