# Algorithm undirected graph to directed strongly connected graph

For an undirected connected graph $$G=(V,E)$$ given as adjacency list I want to find a directed strongly connected graph $$G=(V,E')$$ where each $$e' \in E'$$ is either $$(u,v)$$ or $$(v,u)$$ if we look at its original $$e=\{u,v\}$$. Also we're assuming there are no bridges in the given graph G (which I'm checking before hand).

• "Transform" is vague. You could add a new vertex that has an edge to and from every other vertex of the graph or, if the graph is connected, you could just replace each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$... but I doubt that's what you want as this would be trivial. Can you edit your question with a formal definition of your problem? Nov 7 '19 at 13:55
• Yeah, you are right, sorry. By transform I meant, every undirected edge {u, v} can either be transformed into (u, v) or (v, u), but not both.
– user106782
Nov 7 '19 at 17:24
• Then this is not possible in general. Think of a disconnected graph. If the graph has to be connected then think of a tree. Nov 7 '19 at 17:26
• I formalized the problem. Sorry I didn't find time to do this earlier. Is any more information needed?
– user106782
Nov 8 '19 at 17:02
• Iteratively do the following: 1) find a cycle $C$ in $G$, 2) orient the edges of $C$ in an arbitrary but consistent direction w.r.t. $C$, 3) Orient the chords of $C$ in an arbitrary direction. 4) identify the vertices in $C$ (ignoring self-loops but possibly creating parallel edges). If there are two or more vertices left in $G$ then there must still be a cycle (otherwise there was a bridge in $G$), therefore you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done. Nov 8 '19 at 18:04

The idea is that if we find a cycle in $$G$$, then we can orient its edges so that the nodes in the cycle will be all strongly connected. The cycle can then be collapsed into a single node. If the graph had no bridges the new graph will also have no bridges and this procedure can be repeated. Eventually, you will be left with a single node, meaning that the whole graph is a single strongly connected component, as desired.

More precisely, you can iteratively do the following:

• Find a cycle $$C$$in $$G$$;

• Orient the edges of $$C = \langle u_1, u_2, \dots, u_k, u_{k+1} = u_1 \rangle$$ in an arbitrary but consistent direction w.r.t. $$C$$. For example, for $$i=1, \dots, k$$ orient $$(u_i, u_{i+1})$$ towards $$u_{i+1}$$;

• Orient the chords of $$C$$ in an arbitrary direction.

• Identify the vertices in $$C$$, possibly creating parallel edges (but ignoring self-loops). This means replacing $$u_1, \dots, u_k$$ with a new super-vertex $$\overline{u}$$. For every edge $$(x,y)$$ where $$x \in C$$ and $$y \not\in C$$, add a new edge $$(\overline{u}, y)$$.

• Repeat until a single vertex is left in $$G$$.

Notice that if there are two or more vertices left in $$G$$ then there must still be a cycle (otherwise there is a bridge that was also bridge in the original graph). This means that you will eventually be left with a single vertex. When this happens, all edges in the original graph $$G$$ must have been assigned a direction and you are done.

If you think of using the above algorithm while performing a single DFS visit to discover the cycles to contract, then all the cycles $$C$$ will be of the form $$\langle u_1, \dots, u_k, u_{k+1} = u_1 \rangle$$, where for $$i=1,\dots,k-1$$, $$u_{i}$$ is the parent of $$u_{i+1}$$ in the DFS tree, and $$(u_k, u_1)$$ is a back-edge. If you use the above choice for the orientation of the edges of $$C$$, then this is equivalent to this simpler algorithm:

• Perform a DFS visit of $$G$$ from an arbitrary vertex $$r$$ to obtain a tree $$T$$.
• Orient all the edges of $$T$$ away from $$r$$.
• Orient the edges not in $$T$$ towards $$r$$ (notice that this is well defined since there will be no edges between two nodes at the same depth in $$T$$).

You can also give a direct proof that the orientation $$G'$$ computed by this second algorithm is a strongly-connected graph. It is clear that there is a path from $$r$$ to any other vertex in $$G'$$. The following claim implies the converse.

Claim: Let $$(u,v)$$ be an edge of $$T$$, with $$u$$ being the parent of $$v$$. There is a path from $$v$$ to $$u$$ in $$G'$$.

Proof: Since $$(u,v)$$ is not a bridge, there must be a cycle of the form $$C = \langle u_1 = u, u_2 = v, u_3, \dots, u_k, u_{k+1} = u_1 \rangle$$. Let $$i$$ be the smallest index in $$\{1, \dots, k\}$$ such that $$u_i$$ lies in the subtree $$T_v$$ of $$T$$ rooted at $$v$$ and $$u_{i+1} \not\in T_v$$ (this edge must always exist). Since $$u_i \in T_v$$, there is a (possibly empty) directed path $$P$$ from $$v$$ to $$u_i$$ in $$G'$$. Since $$u_{i+1}$$ is an ancestor of $$v$$ and $$u_{i+1} \not\in T_v$$, $$u_{i+1}$$ must be an ancestor of $$u$$ (possibly $$u$$ itself). This means that there is a (possibly empty) directed path $$Q$$ from $$u_{i+1}$$ to $$u$$ in $$G'$$. Finally, $$(u_i, u_{i+1})$$ is not a tree edge, hence it is directed towards $$u_{i+1}$$. This means that $$P \circ (u_i, u_{i+1}) \circ Q$$ is a path from $$v$$ to $$u$$ in $$G'$$ (where $$\circ$$ denotes concatenation). $$\quad\square$$