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

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.

        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
            add Cycle to Paths
        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

Extra Dataset

Please login to solve this problem.