TAOCP 2.3.4.2 Exercise 11
Let the directed graph be processed exactly as in the solution to exercise 2.
Section 2.3.4.2: Oriented Trees
Exercise 11. [**] $$28$$ Using the assumptions of exercise 2.3.4.1-6, but with $(a_k,b_k)$ representing an arc from $V_{a_k}$ to $V_{b_k}$, design an algorithm that not only prints out a free subtree as in that algorithm, but also prints out the fundamental cycles. [Hint: The algorithm given in the solution to exercise 2.3.4.1-6 can be combined with the algorithm in the preceding exercise.]
Verified: yes
Solve time: 1m11s
Let the directed graph be processed exactly as in the solution to exercise 2.3.4.1-6, except that whenever an arc $(a_k,b_k)$ is found to join two vertices already belonging to the same free subtree, that arc is not inserted into the subtree. Instead, use the algorithm of exercise 10 to re-root the current oriented tree at $V_{a_k}$. In the resulting orientation there is a unique oriented path from $V_{b_k}$ to $V_{a_k}$, by property (c) of oriented trees. Printing this path together with the arc $(a_k,b_k)$ gives the fundamental cycle determined by that arc.
When an arc $(a_k,b_k)$ joins two different free subtrees, proceed exactly as in the solution to exercise 2.3.4.1-6 and include the corresponding edge in the printed free subtree. When an arc joins vertices already in the same subtree, print the cycle obtained from the unique path between $V_{b_k}$ and $V_{a_k}$ in the re-rooted tree together with $(a_k,b_k)$. Since every non-tree arc determines exactly one such path in a tree, every fundamental cycle is printed exactly once, and all fundamental cycles are obtained.