Collecting all paths of DAG with backward and forward links

Question

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

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

where ForwardStates is a list of states via forward links from the current state. and backStates is a list of states via backward links 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

Where backward links are represented by brown dotted arrow and forward links is represented by black concrete arrow, the possible paths are {{initial, b, a, final},{initial, c, final},{initial, b, initial,final}}

The rule is that from initial state, it must go through 1 or more backward links, before go through forward link, and once it switch to forward link, it will keep to forward links （i.e., it can't use the backward links anymore).

This question is an extension of this question(Collecting all paths of DAG).

Wo got the problem defintion but what is your question? *write it for me?* — I4V, Feb 01 '13 at 18:29
@I4V You can provide any details, as long it helps in tackling this :) — william007, Feb 01 '13 at 18:34
william007, I would, If it were a programming question and you had a specific one. What you are looking for is someone doing the research for you and maybe better write the code. — I4V, Feb 01 '13 at 18:37
@Keyser It is actually 2 different DAGs, one using "forward links" and one using "backward links" — amit, Feb 01 '13 at 18:39
@william007 - Out of curiosity, what's the use case for a search like this? — Bobson, Feb 01 '13 at 19:10
Possible duplicate of [Find all paths between two graph nodes](http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes) — SumNeuron, Mar 04 '17 at 19:27

amit · Answer 1 · 2013-02-02T08:18:04.113

2

Do a DFS from initial state using the graph which using only backward links. From each of the nodes discovered by during this DFS (except initialState) do another DFS until you find the path to the target (using forward links only).

For each node u you discovered during DFS on backward links, the path is

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

Where path(u,v) is the path found by the relevant DFS for this step.
Note that it might be invoked on a certain u more then once - you invoke it for each path you find from initialState to u, since it is a different required path.

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

edited Feb 02 '13 at 08:18

answered Feb 01 '13 at 18:36

amit

175,853
27
231
333

Is there any advantage to using DFS instead of BFS, given that he's looking for all solutions and thus has to walk the entire tree? – Bobson Feb 01 '13 at 19:08
@Bobson Yes. DFS only needs to remember the length of the current path, while using BFS you are going to need to remember all paths at a time. Unless I am missing something - I cannot think of a memory efficient (`O(n)` memory) implementation of it using BFS to get ALL paths in the DAG. – amit Feb 01 '13 at 19:10
That's a good point. I had forgotten about that aspect of DFS. – Bobson Feb 01 '13 at 19:15
@amit thanks!, may I know why number of paths to get to vertex i using backward links is=i^2? – william007 Feb 02 '13 at 02:15
@amit, I have an extension of the question here (which you have mentioned that it can be done more efficiently with some tricks): http://stackoverflow.com/q/14658214/1497720, thanks! – william007 Feb 02 '13 at 03:16
@william007 It is not, I'll remove this part. It is actually `O(2^i)` worst case. You need to chose subset of vertices to use in a complete DAG. – amit Feb 02 '13 at 08:17

Collecting all paths of DAG with backward and forward links

1 Answers1

Linked