Collect all DAG paths with back and forward links

Question

I have a directed acyclic graph where each node represents a state

public class State{ List<State> ForwardStates; List<State> backStates; string stateName; } 

where ForwardStates is a list of states through direct links from the current state. and backStates is a list of states via backlinks from the current state.

I have two special conditions

 State initialState (name=initial) State finalState (name=final) 

I want to find all the paths from the initial state to the final state and fill

 List<List<string>> paths 

For example, this chart is as follows

If backlinks are represented by a brown arrow and direct links are represented by a black concrete arrow, the possible paths are {{initial, b, a, final}, {initial, c, final}, {initial, b, initial, final}}

The rule is that from the initial state, it must go through 1 or more backlinks before moving on a direct line of communication, and as soon as it switches to a direct link, it will continue to forward links (i.e. it cannot use backlinks).

This question is a continuation of this question ( Collecting all DAG paths ).

Answer 1

Make DFS from its original state using a graph that uses only backlinks. From each of the nodes detected during this DFS (except initialState), execute another DFS until you find the path to the target (using only direct links only).

For each node u that you found during DFS on backlinks, the path

 path(initialState,u) ; path(u,finalState) 

Where path(u,v) is the path found by the corresponding DFS for this step.
Please note that it can be called on some u more than once - you call it for every path you initialState from initialState to u , since this is another required path.

---

If you only need the number of paths, this could be solved faster using topological sorting and DP , but this is not the case here.