Sept. 6, 2015, 11:37 p.m. by Rosalind Team
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.
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.
1 -> 2 2 -> 3 3 -> 4,5 6 -> 7 7 -> 6
1 -> 2 -> 3 3 -> 4 3 -> 5 7 -> 6 -> 7