Generate All Maximal Non-Branching Paths in a Graph solved by 143

Sept. 6, 2015, 11:37 p.m. by Rosalind Team

A node in a directed graph Graph is called a 1-in-1-out node if its indegree and outdegree are both equal to 1, i.e., in(v) = out(v) = 1.  We can rephrase the definition of a "maximal non-branching path" from the main text as a path whose internal nodes are 1-in-1-out nodes and whose initial and final nodes are not 1-in-1-out nodes.  Also, note that the definition from the main text does not handle the special case when Graph has a connected component that is an isolated cycle, in which all nodes are 1-in-1-out nodes.

The MaximalNonBranchingPaths pseudocode below generates all non-branching paths in a graph. It iterates through all nodes of the graph that are not 1-in-1-out nodes and generates all non-branching paths starting at each such node. In a final step, MaximalNonBranchingPaths finds all isolated cycles in the graph.

MaximalNonBranchingPaths(Graph)
Paths ← empty list
for each node in Graph
if is not a 1-in-1-out node
if out(v) > 0
for each outgoing edge (v, w) from v
NonBranchingPath ← the path consisting of the single edge (v, w)
while is a 1-in-1-out node
extend NonBranchingPath by the outgoing edge (w, u) from
w ← u
add NonBranchingPath to the set Paths
for each isolated cycle Cycle in Graph
return Paths

Maximal Non-Branching Path Problem

Find all maximal non-branching paths in a graph.

Given: The adjacency list of a graph whose nodes are integers.

Return: The collection of all maximal non-branching paths in the graph.

Sample Dataset

1 -> 2
2 -> 3
3 -> 4,5
6 -> 7
7 -> 6


Sample Output

1 -> 2 -> 3
3 -> 4
3 -> 5
7 -> 6 -> 7