Charging Station: Maximal Non-Branching Paths in a Graph

Maximal non-branching path

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. We can rephrase the definition of a “maximal nonbranching 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 doesn’t handle the case when Graph has a connected component that is an isolated cycle, in which all nodes are 1-in-1-out nodes (see the figure below):

MaximalNonBranchingPaths, shown below, 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, it finds all isolated cycles in the graph.