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

A node v 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.

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

Extra Dataset

Click for an extra dataset