Finding all paths on undirected graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:33:31Z http://mathoverflow.net/feeds/question/18603 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph Finding all paths on undirected graph JesseStimpson 2010-03-18T15:31:12Z 2012-04-27T06:02:25Z <p>I have an undirected, unweighted graph, and I'm trying to come up with an algorithm that, given 2 unique nodes on the graph, will find all paths connecting the two nodes, not including cycles. Here's an illustration of what I'd like to do: <a href="http://imgur.com/J3t5O.png" rel="nofollow">Graph example</a></p> <p>Does this algorithm have a name? Can it be done in polynomial time?</p> <p>Thanks,</p> <p>Jesse</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18634#18634 Answer by rgrig for Finding all paths on undirected graph rgrig 2010-03-18T18:31:29Z 2010-03-19T19:21:16Z <p>Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)</p> <p>The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.</p> <p>Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.</p> <p>Push s on the path stack and call search(s):</p> <pre><code>path // is a stack (initially empty) seen // is a set def stuck(x) if x == t return False for each neighbor y of x if y not in seen insert y in seen if !stuck(y) return False return True def search(x) if x == t print path seen = set(path) if stuck(x) return for each neighbor y of x push y on the path search(y) pop y from the path </code></pre> <p>Here <em>search</em> does the exhaustive search and <em>stuck</em> could be implemented in DFS style (as here) or in BFS style.</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18703#18703 Answer by Joseph Malkevitch for Finding all paths on undirected graph Joseph Malkevitch 2010-03-19T01:42:35Z 2010-03-19T01:42:35Z <p>For shortest paths look at:</p> <p><a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a></p> <p>and also:</p> <p><a href="http://www.springerlink.com/content/t53j31t5012v6605/" rel="nofollow">http://www.springerlink.com/content/t53j31t5012v6605/</a></p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18732#18732 Answer by MRA for Finding all paths on undirected graph MRA 2010-03-19T12:44:47Z 2010-03-19T12:44:47Z <p>If I'm not mistaken, I think an adaptation of a dynamic programming all-pairs-shortest-path algorithm (like the Floyd-Warshall algorithm, considering edge weights of 1) might find all paths. Consider the following scheme to find the <em>total number</em> of all paths leading from <em>u</em> to <em>v</em> (or, in fact, from any start node to any destination):</p> <p>A matrix $M_1$ is initialized as the adjacency matrix of the graph. That is, $M_1[u,v]$ containes the number of simple paths of length at most 1 from <em>u</em> to <em>v</em>. After that, for all $i$ from 2 to the number of nodes the matrix $M_i$ is updated as follows: $M_i[u,v]$ equals the sum of the entries $M_{i-1}[u,w]$ for all nodes <em>w</em> adjacent to <em>v</em>. Hence, $M_i[u,v]$ containes the number of simple paths of length at most <em>i</em> from <em>u</em> to <em>v</em>. This scheme runs in time polynomial in the input size, and it can also be modified easily to also store the actual paths in time (and space) polynomial in the output size.</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/18738#18738 Answer by Sangxia Huang for Finding all paths on undirected graph Sangxia Huang 2010-03-19T13:10:30Z 2010-03-19T13:10:30Z <p>I think this is not an easy problem, and may not be able to compute efficiently. Trying to work out a proof on it.</p> <p>By the way, I think there may be some problems with @MRA's dynamic programming solution, because it seems that in the M_i's, there is no way to memorize whether a path has visited certain vertices, while we are required to find all simple paths. Therefore, the dynamic programming solution might include those paths with cycles, and thus would be incorrect.</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/53411#53411 Answer by unknown (google) for Finding all paths on undirected graph unknown (google) 2011-01-26T22:00:07Z 2011-01-26T22:00:07Z <p>How would you do this iteratively? </p> <p>I'm trying to do the same thing, enumerate all paths from one node to every other node on the graph. No weights, bi-directional. </p> <p>On a simple graph like: I want all possible paths from u to every other node. </p> <p>u --o</p> <p>| X |</p> <p>q --e</p> <p>output would be: uoqe uoq uoeq uoe uo uqoe uqo uqeo uqe uq ueoq ueo ueqo ueq ue</p> <p>I was able to do it recursively but I can't figure out how to do it iteratively </p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/94533#94533 Answer by grdvnl for Finding all paths on undirected graph grdvnl 2012-04-19T14:24:22Z 2012-04-19T14:24:22Z <p>Say, I have an acyclic graph. Then can't I still use an adaptation of Floyed-Warshall algorithm to determine the paths. In the statement inside the innermost loop, all I would need is </p> <pre><code> for all k in 1 to n for all i in 1 to n for all j in 1 to n Aij = Aij + ( Aik * Akij). </code></pre> <p>I am not able to prove that this does not give me the count of paths between 2 vertices.</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/95307#95307 Answer by Paul Wollan for Finding all paths on undirected graph Paul Wollan 2012-04-26T21:33:57Z 2012-04-26T21:33:57Z <p>There is an easy way to partition the set of $s$-$t$ paths in a graph $G$. Fix an edge $tt'$ in $G$. Let $P_1$ be the set of paths from $s$ to $t$ which use the edge $tt'$, and let $P_2$ be the set of paths from $s$ to $t$ in $G-tt'$. Then $P_1 \cap P_2 = \emptyset$ and the set of $s$-$t$ paths $P = P_1 \cup P_2$. Moreover, there is a one to one correspondence between the set of paths $P_1$ and the set of $s$-$t'$ paths in the graph $G-t$. </p> <p>Thus, we get an easy recursive algorithm to find the set of paths $s$-$t$ paths in a graph $G$. Pick an edge $tt'$ incident the vertex $t$ and recursively calculate the sets $P_1$ and $P_2$. With a small amount of pre-processing, we can ensure that the runtime is $O(m(p+1))$ where $m$ is the number of edges and $p$ is the number of $s$-$t$ paths.</p> <p>To make the recurrence relation on the runtime work, consider the following. We can test in time $O(m)$ if a given graph $G$ and pair of vertices $s$ and $t$ if $G$ has 0, exactly one, or at least two distinct $s$-$t$ paths. To see this, simply find the block decomposition of the graph and, and check if there is any non-trivial block between $s$ and $t$ in the tree. </p> <p>We can push this slightly farther. Given an instance of the problem $G$ and vertices $s$ and $t$, we can reduce the problem in time $O(m)$ to a graph $\bar{G}$ and vertices $x$ and $y$ such that for all edges $xx'$ incident to $x$, we have that</p> <ol> <li>$xx'$ is in some $y$-$x$ path, </li> <li>there exists a $y$-$x'$ path in $\bar{G}-x$.</li> </ol> <p>To see this, again using the block decomposition, we contract any bridge in the graph and delete edges not contained in any $s$-$t$ path. As above, this can be done in $O(m)$ time.</p> <p>We give an $O(m(p-1))$ time algorithm to find the set of $s$-$t$ paths in a given graph $G$ with at least two $s$-$t$ paths. </p> <ol> <li>We may assume, as above, that every edge $tt'$ incident to $t$ is contained in some $s$-$t$ path and that there exists at least one $s$-$t'$ path in $G-t$. </li> <li>Check if the number of $s$-$t$ paths in $G-tt'$ is at least two, and if not, let $P_1$ be the set of the unique $s$-$t$ path in $G-tt'$. If there are at least two such paths, we recursively find the set of all such paths. Let $p_1 = |P_1|$. By choice of $tt'$, $p_1 \ge 1$.</li> <li>Check if the number of $s$-$t'$ paths in $G-t$ is at least two, and if not let $P_2$ be the set of the unique $s$-$t'$ path in $G-t$. Otherwise, we recursively find the set $P_2$ of $s$-$t'$ path in $G-t$. Let $p_2 = |P_2|$, and as above, we again have $p_2 \ge 1$.</li> </ol> <p>Step 1 can be performed in $c'm$ operations for some constant $c'$. The initial check in steps $2$ and $3$ can be performed in $c'(m-1)$ steps. If we must recursively run the algorithm, this will require another $c(m-1)(p_i - 1)$ operations for $i = 1, 2$ in Steps 2 and 3, respectively. As $p_i \ge 1$, we can bound the work in each of Steps 2 and 3 by $c'm + cm(p_i - 1)$. Thus, the total number of operations is at most $3c'm + c(m)(p_1 +p_2 - 2) \le cm(p-1)$ if we choose $c \ge 3c'$.</p> http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph/95324#95324 Answer by Ernest for Finding all paths on undirected graph Ernest 2012-04-27T05:53:29Z 2012-04-27T06:02:25Z <p>Let $G=(V,E)$ be a graph.<br></p> <p>$FindPaths(p,f)$ prints all paths which end in $f$ and can be obtained by adding nodes to path $p$. $p$ is for path, $f$ is for final (node).<br></p> <p>Def $FindPaths(p,f)$:<br> Let $x$ be the last node of $p$.<br> For each edge $xy$ for some $y$ in $E$<br> $\ \ \ \$If $y$ is not in $p$<br> $\ \ \ \ $$\ \ \ \ If y=f<br> \ \ \ \$$\ \ \ \ $$\ \ \ \ Print p-y<br> \ \ \ \$$\ \ \ \$Else<br> $\ \ \ \ $$\ \ \ \$$\ \ \ \$$FindPaths(p-y,f)$<br><br></p> <p>If $s$ is the start node and $t$ is the ending node, run $FindPaths(s,t)$.</p> <p>You can represent path and edges as strings. To check if a node is in a path $p$ you just have to check whether the string contains the character that represents the node. To get the final node of a path use the function to get the last character of a string.</p> <p>EDIT: My answer is not math research level, but introduction to programming.</p>