Collect all DAG paths

Question

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

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

where ForwardStates is a list of the following states from the current state.

I have two special conditions

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

I want to find all the paths in the beginning from the initial state to the final state and is populated in

 List<List<string>> paths 

For example, this chart is as follows

paths must contain the value {{"Start", "a", "final"}, {"start", "b", "final"}}

How can I easily achieve this in C # without recursion (since the graph can be large)?

Answer 1

Your algorithm might look like this:

• Create a queue Tuple<State, List<String>> .
• Enqueue { InitialState, new List<string> { InitialState.Name } }
• As long as there are any items in line
  • Discard first item
  • For all unconfigured states in the dequeued state, enqueue { ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
  • If the final state is forward state, add DequeuedList.ToList().Add(FinalState.Name) to your list of results.

In the end, you should have an empty queue and a list of lists of strings that you want.

Answer 2

Thanks for the comments, I am also using the suggestion here https://stackoverflow.com/a/166991/ ... (The key point is not to use visit state during BFS / DFS)

Here is the version using DFS without guest state

  List<List<string>> paths= new List<List<string>>(); Stack<Tuple<State, List<string>>> working = new Stack<Tuple<State, List<string>>>(); working.Push(new Tuple<State, List<string>>(initialNode, new List<string> { initialNode.stateName })); do { Tuple<State, List<string>> curr = working.Pop(); if (currNexts.stateName == "final") { res.Add(curr.Item2); } else { foreach (State currNext in curr.Item1.ForwardStates) { working.Push(new Tuple<State, List<string>>(rnext, curr.Item2.Union(new[] { rnext.stateName }).ToList())); } } } while (working.Count != 0);