Collecting all paths of DAG

Question

I have a directed acyclic graph where each node is represent by a state

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

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

I have two special state

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

I wish to find all paths the start from initial state to final state, and populated in

List<List<string>> paths

For example given the graph like the following

enter image description here

paths should contain the value {{"initial","a","final"},{"initial","b","final"}}

How should I achieve this easily in C# without recursion (as the graph might be big)?

any algorithms course at all will teach you about search algorithms — im so confused, Jan 31 '13 at 17:43
look at http://en.wikipedia.org/wiki/Breadth-first_search for the first one you learn — im so confused, Jan 31 '13 at 17:45
if graph is really big, number of possible paths may grow exponentially, and it is possible that paths string would not fit into even disk, much less memory — mvp, Jan 31 '13 at 17:45
Check out this link for a good description of algorithms for processing graphs. Skip down about halfway for DAGs. (http://algs4.cs.princeton.edu/42directed/) — Jay Walker, Jan 31 '13 at 17:58

score 2 · Answer 1 · answered Jan 31 '13 at 17:47

Your algorithm might go like:

Create a queue of Tuple<State, List<String>>.
Enqueue { InitialState, new List<string> { InitialState.Name } }
While the queue has any items,
- Dequeue the first item
- For all non-final forward states in the dequeued state, enqueue { ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
- If final state is a forward state, add DequeuedList.ToList().Add(FinalState.Name) to your output list.

You should end up with an empty queue and a list of lists of strings as you desire.

score 1 · Answer 2 · edited May 23 '17 at 11:56

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

Here is a version using DFS without Visited 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);

Collecting all paths of DAG

2 Answers2

Linked