<p>I am trying to determine the best time efficient algorithm to accomplish the task described below.</p>

<p>I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another. This basically represents an undirected graph, with the records being the vertices and the connection data the edges.</p>

<p>All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).</p>

<p>I want to choose any two records from the set and be able to show all simple paths between the chosen records. By "simple paths" I mean the paths which do not have repeated records in the path (i.e. finite paths only).</p>

<p>Note: The two chosen records will always be different (i.e. start and end vertex will never be the same; no cycles).</p>

<p>For example:</p>

<pre>
    If I have the following records:
        A, B, C, D, E

    and the following represents the connections: 
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]
</pre>

<p>If I chose B as my starting record and E as my ending record, I would want to find all simple paths through the record connections that would connect record B to record E.</p>

<pre>
   All paths connecting B to E:
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E
</pre>

<p>This is an example, in practice I may have sets containing hundreds of thousands of records.</p>

[{'answer_id': 58321, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': "<p>I have solved a similar problem to this recently, instead of all solutions I was only interested in the shortest.</p>\n\n<p>I used a 'breadth first' iterative search which used a queue of status' each of which held a record containing a current point on the graph and the path taken to get there.</p>\n\n<p>you start with a single record in the queue, which has the starting node and an empty path.</p>\n\n<p>Each iteration through the code takes the item off the head of the list, and checks to see if it is a solution (the node arrived at is the one you want, if it is, we are done), otherwise, it constructs a new queue item with the nodes connecting to the current node, and amended paths that are based on the path of the previous node, with the new jump attached at the end.</p>\n\n<p>Now, you could use something similar, but when you find a solution, instead of stopping, add that solution to your 'found list' and continue.</p>\n\n<p>You need to keep track of a visited nodes list, so that you never backtrack on yourself otherwise you have an infinite loop.</p>\n\n<p>if you want a bit more pseudocode post a comment or something, and I will elaborate.</p>\n"}, {'answer_id': 58343, 'author': 'Ryan Fox', 'author_id': 55, 'author_profile': 'https://Stackoverflow.com/users/55', 'pm_score': 0, 'selected': False, 'text': "<p>Here's a thought off the top of my head:</p>\n\n<ol>\n<li>Find one connection. (Depth-first search is probably a good algorithm for this, since the path length doesn't matter.)</li>\n<li>Disable the last segment.</li>\n<li>Try to find another connection from the last node before the previously disabled connection.</li>\n<li>Goto 2 until there are no more connections.</li>\n</ol>\n"}, {'answer_id': 58444, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': "<p>I think you should describe your real problem behind this. I say this because you ask for something time efficient, yet the answer set to the problem seems to grow exponentially!</p>\n\n<p>Therefore I wouldn't expect a better algorithm than something exponential.</p>\n\n<p>I'd do backtracking and going through the whole graph. In order to avoid cycles, save all visited nodes along the way. When you go back, unmark the node.</p>\n\n<p>Using recursion:</p>\n\n<pre><code>static bool[] visited;//all false\nStack&lt;int&gt; currentway; initialize empty\n\nfunction findnodes(int nextnode)\n{\nif (nextnode==destnode)\n{\n  print currentway \n  return;\n}\nvisited[nextnode]=true;\nPush nextnode to the end of currentway.\nfor each node n accesible from nextnode:\n  findnodes(n);\nvisited[nextnode]=false; \npop from currenteay\n}\n</code></pre>\n\n<p>Or is that wrong?</p>\n\n<p>edit:\nOh, and I forgot:\nYou should eliminate the recursive calls by utilizing that node stack</p>\n"}, {'answer_id': 58446, 'author': 'Casey Watson', 'author_id': 4682, 'author_profile': 'https://Stackoverflow.com/users/4682', 'pm_score': 8, 'selected': True, 'text': '<p>It appears that this can be accomplished with a depth-first search of the graph. <strong>The depth-first search will find all non-cyclical paths between two nodes.</strong> This algorithm should be very fast and scale to large graphs (The graph data structure is sparse so it only uses as much memory as it needs to).</p>\n\n<p>I noticed that the graph you specified above has only one edge that is directional (B,E). Was this a typo or is it really a directed graph? This solution works regardless. Sorry I was unable to do it in C, I\'m a bit weak in that area. I expect that you will be able to translate this Java code without too much trouble though.</p>\n\n<p><strong>Graph.java:</strong></p>\n\n\n\n<pre class="lang-java prettyprint-override"><code>import java.util.HashMap;\nimport java.util.LinkedHashSet;\nimport java.util.LinkedList;\nimport java.util.Map;\nimport java.util.Set;\n\npublic class Graph {\n    private Map&lt;String, LinkedHashSet&lt;String&gt;&gt; map = new HashMap();\n\n    public void addEdge(String node1, String node2) {\n        LinkedHashSet&lt;String&gt; adjacent = map.get(node1);\n        if(adjacent==null) {\n            adjacent = new LinkedHashSet();\n            map.put(node1, adjacent);\n        }\n        adjacent.add(node2);\n    }\n\n    public void addTwoWayVertex(String node1, String node2) {\n        addEdge(node1, node2);\n        addEdge(node2, node1);\n    }\n\n    public boolean isConnected(String node1, String node2) {\n        Set adjacent = map.get(node1);\n        if(adjacent==null) {\n            return false;\n        }\n        return adjacent.contains(node2);\n    }\n\n    public LinkedList&lt;String&gt; adjacentNodes(String last) {\n        LinkedHashSet&lt;String&gt; adjacent = map.get(last);\n        if(adjacent==null) {\n            return new LinkedList();\n        }\n        return new LinkedList&lt;String&gt;(adjacent);\n    }\n}\n</code></pre>\n\n<p><strong>Search.java:</strong></p>\n\n<pre class="lang-java prettyprint-override"><code>import java.util.LinkedList;\n\npublic class Search {\n\n    private static final String START = "B";\n    private static final String END = "E";\n\n    public static void main(String[] args) {\n        // this graph is directional\n        Graph graph = new Graph();\n        graph.addEdge("A", "B");\n        graph.addEdge("A", "C");\n        graph.addEdge("B", "A");\n        graph.addEdge("B", "D");\n        graph.addEdge("B", "E"); // this is the only one-way connection\n        graph.addEdge("B", "F");\n        graph.addEdge("C", "A");\n        graph.addEdge("C", "E");\n        graph.addEdge("C", "F");\n        graph.addEdge("D", "B");\n        graph.addEdge("E", "C");\n        graph.addEdge("E", "F");\n        graph.addEdge("F", "B");\n        graph.addEdge("F", "C");\n        graph.addEdge("F", "E");\n        LinkedList&lt;String&gt; visited = new LinkedList();\n        visited.add(START);\n        new Search().depthFirst(graph, visited);\n    }\n\n    private void depthFirst(Graph graph, LinkedList&lt;String&gt; visited) {\n        LinkedList&lt;String&gt; nodes = graph.adjacentNodes(visited.getLast());\n        // examine adjacent nodes\n        for (String node : nodes) {\n            if (visited.contains(node)) {\n                continue;\n            }\n            if (node.equals(END)) {\n                visited.add(node);\n                printPath(visited);\n                visited.removeLast();\n                break;\n            }\n        }\n        for (String node : nodes) {\n            if (visited.contains(node) || node.equals(END)) {\n                continue;\n            }\n            visited.addLast(node);\n            depthFirst(graph, visited);\n            visited.removeLast();\n        }\n    }\n\n    private void printPath(LinkedList&lt;String&gt; visited) {\n        for (String node : visited) {\n            System.out.print(node);\n            System.out.print(" ");\n        }\n        System.out.println();\n    }\n}\n</code></pre>\n\n<p>Program Output:</p>\n\n<pre class="lang-java prettyprint-override"><code>B E \nB A C E \nB A C F E \nB F E \nB F C E \n</code></pre>\n'}, {'answer_id': 58461, 'author': 'Robert Groves', 'author_id': 3534, 'author_profile': 'https://Stackoverflow.com/users/3534', 'pm_score': 4, 'selected': False, 'text': '<p>Here is the pseudocode I came up with. This is not any particular pseudocode dialect, but should be simple enough to follow.</p>\n\n<p>Anyone want to pick this apart.</p>\n\n<ul>\n<li><p>[p] is a list of vertices representing the current path.</p></li>\n<li><p>[x] is a list of paths where meet the criteria</p></li>\n<li><p>[s] is the source vertex</p></li>\n<li><p>[d] is the destination vertex</p></li>\n<li><p>[c] is the current vertex (argument to the PathFind routine)</p></li>\n</ul>\n\n<p>Assume there is an efficient way to look up the adjacent vertices (line 6).</p>\n\n<pre>\n     1 PathList [p]\n     2 ListOfPathLists [x]\n     3 Vertex [s], [d]\n\n     4 PathFind ( Vertex [c] )\n     5     Add [c] to tail end of list [p]\n     6     For each Vertex [v] adjacent to [c]\n     7         If [v] is equal to [d] then\n     8             Save list [p] in [x]\n     9         Else If [v] is not in list [p]\n    10             PathFind([v])\n    11     Next For\n    12     Remove tail from [p]\n    13 Return\n</pre>\n'}, {'answer_id': 58507, 'author': 'mweerden', 'author_id': 4285, 'author_profile': 'https://Stackoverflow.com/users/4285', 'pm_score': 0, 'selected': False, 'text': '<p>As far as I can tell the solutions given by Ryan Fox (<a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices#58343">58343</a>, Christian (<a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices#58444">58444</a>), and yourself (<a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices#58461">58461</a>) are about as good as it get. I do not believe that breadth-first traversal helps in this case, as you will not get all paths. For example, with edges <code>(A,B)</code>, <code>(A,C)</code>, <code>(B,C)</code>, <code>(B,D)</code> and <code>(C,D)</code> you will get paths <code>ABD</code> and <code>ACD</code>, but not <code>ABCD</code>.</p>\n'}, {'answer_id': 75941, 'author': 'Michael Dorfman', 'author_id': 6741, 'author_profile': 'https://Stackoverflow.com/users/6741', 'pm_score': 5, 'selected': False, 'text': '<p>The National Institute of Standards and Technology (NIST) online Dictionary of Algorithms and Data Structures lists this problem as "<a href="https://xlinux.nist.gov/dads/HTML/allSimplePaths.html" rel="noreferrer">all simple paths"</a> and recommends a <a href="https://xlinux.nist.gov/dads/HTML/depthfirst.html" rel="noreferrer">depth-first search</a>.  CLRS supplies the relevant algorithms.</p>\n\n<p>A clever technique using Petri Nets is found <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1084515" rel="noreferrer">here</a></p>\n'}, {'answer_id': 4375881, 'author': 'Vjeux', 'author_id': 232122, 'author_profile': 'https://Stackoverflow.com/users/232122', 'pm_score': 0, 'selected': False, 'text': '<p>I found a way to enumerate all the paths including the infinite ones containing loops.</p>\n\n<p><a href="http://blog.vjeux.com/2009/project/project-shortest-path.html" rel="nofollow">http://blog.vjeux.com/2009/project/project-shortest-path.html</a></p>\n\n<p><strong>Finding Atomic Paths &amp; Cycles</strong></p>\n\n<pre><code>Definition\n</code></pre>\n\n<p>What we want to do is find all the possible paths going from point A to point B. Since there are cycles involved, you can\'t just go through and enumerate them all. Instead, you will have to find atomic path that doesn\'t loop and the smallest possible cycles (you don\'t want your cycle to repeat itself).</p>\n\n<p>The first definition I took of an atomic path is a path that does not go through the same node twice. However, I found out that is was not taking all possibilities. After some reflexion, I figured out that nodes aren\'t important, however edges are! So an atomic path is a path that does not go through the same edge twice.</p>\n\n<p>This definition is handy, it also works for cycles: an atomic cycle of point A is an atomic path that goes from point A and ends to point A.</p>\n\n<p><strong>Implementation</strong></p>\n\n<pre><code>Atomic Paths A -&gt; B\n</code></pre>\n\n<p>In order to get all the path starting from point A, we are going to traverse the graph recursively from the point A. While going through a child, we are going to make a link child -> parent in order to know all the edges we have already crossed. Before we go to that child, we must traverse that linked list and make sure the specified edge has not been already walked through.</p>\n\n<p>When we arrive to the destination point, we can store the path we found.</p>\n\n<pre><code>Freeing the list\n</code></pre>\n\n<p>A problem occurs when you want to free the linked list. It is basically a tree chained in the reverse order. A solution would be to double-link that list and when all the atomic paths been found, free the tree from the starting point.</p>\n\n<p>But a clever solution is to use a reference counting (inspired from Garbage Collection). Each time you add a link to a parent you adds one to its reference count. Then, when you arrive at the end of a path, you go backward and free while the reference count equals to 1. If it is higher, you just remove one and stop.</p>\n\n<pre><code>Atomic Cycle A\n</code></pre>\n\n<p>Looking for the atomic cycle of A is the same as looking for the atomic path from A to A. However there are several optimizations we can do. First, when we arrive at the destination point, we want to save the path only if the sum of the edges cost is negative: we only want to go through absorbing cycles.</p>\n\n<p>As you have seen previously, the whole graph is being traversed when looking for an atomic path. Instead, we can limit the search area to the strongly connected component containing A. Finding these components requires a simple traverse of the graph with Tarjan\'s algorithm.</p>\n\n<p><strong>Combining Atomic Paths and Cycles</strong></p>\n\n<p>At this point, we have all the atomic paths that goes from A to B and all the atomic cycles of each node, left to us to organize everything to get the shortest path. From now on we are going to study how to find the best combination of atomic cycles in an atomic path.</p>\n'}, {'answer_id': 7521818, 'author': 'AndyUK', 'author_id': 6795, 'author_profile': 'https://Stackoverflow.com/users/6795', 'pm_score': 0, 'selected': False, 'text': '<p>As ably described by some of the other posters, the problem in a nutshell is that of using a depth-first search algorithm to recursively search the graph for all combinations of paths between the communicating end nodes.</p>\n\n<p>The algorithm itself commences with the start node you give it, examines all its outgoing links and progresses by expanding the first child node of the search tree that appears, searching progressively deeper and deeper until a target node is found, or until it encounters a node that has no children. </p>\n\n<p>The search then backtracks, returning to the most recent node it hasn’t yet finished exploring.</p>\n\n<p>I <a href="http://technical-recipes.com/?p=1142" rel="nofollow">blogged</a> about this very topic quite recently, posting an example C++ implementation in the process.</p>\n'}, {'answer_id': 8263753, 'author': 'Haibin Liu', 'author_id': 1064820, 'author_profile': 'https://Stackoverflow.com/users/1064820', 'pm_score': 3, 'selected': False, 'text': '<p>Here is a logically better-looking recursive version as compared to the second floor.</p>\n\n<pre><code>public class Search {\n\nprivate static final String START = "B";\nprivate static final String END = "E";\n\npublic static void main(String[] args) {\n    // this graph is directional\n    Graph graph = new Graph();\n    graph.addEdge("A", "B");\n    graph.addEdge("A", "C");\n    graph.addEdge("B", "A");\n    graph.addEdge("B", "D");\n    graph.addEdge("B", "E"); // this is the only one-way connection\n    graph.addEdge("B", "F");\n    graph.addEdge("C", "A");\n    graph.addEdge("C", "E");\n    graph.addEdge("C", "F");\n    graph.addEdge("D", "B");\n    graph.addEdge("E", "C");\n    graph.addEdge("E", "F");\n    graph.addEdge("F", "B");\n    graph.addEdge("F", "C");\n    graph.addEdge("F", "E");\n    List&lt;ArrayList&lt;String&gt;&gt; paths = new ArrayList&lt;ArrayList&lt;String&gt;&gt;();\n    String currentNode = START;\n    List&lt;String&gt; visited = new ArrayList&lt;String&gt;();\n    visited.add(START);\n    new Search().findAllPaths(graph, seen, paths, currentNode);\n    for(ArrayList&lt;String&gt; path : paths){\n        for (String node : path) {\n            System.out.print(node);\n            System.out.print(" ");\n        }\n        System.out.println();\n    }   \n}\n\nprivate void findAllPaths(Graph graph, List&lt;String&gt; visited, List&lt;ArrayList&lt;String&gt;&gt; paths, String currentNode) {        \n    if (currentNode.equals(END)) { \n        paths.add(new ArrayList(Arrays.asList(visited.toArray())));\n        return;\n    }\n    else {\n        LinkedList&lt;String&gt; nodes = graph.adjacentNodes(currentNode);    \n        for (String node : nodes) {\n            if (visited.contains(node)) {\n                continue;\n            } \n            List&lt;String&gt; temp = new ArrayList&lt;String&gt;();\n            temp.addAll(visited);\n            temp.add(node);          \n            findAllPaths(graph, temp, paths, node);\n        }\n    }\n}\n}\n</code></pre>\n\n<p>Program Output</p>\n\n<pre><code>B A C E \n\nB A C F E \n\nB E\n\nB F C E\n\nB F E \n</code></pre>\n'}, {'answer_id': 9247432, 'author': 'Leon Chang', 'author_id': 1204860, 'author_profile': 'https://Stackoverflow.com/users/1204860', 'pm_score': 2, 'selected': False, 'text': '<p>Solution in C code. It is based on DFS which uses minimum memory. </p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdbool.h&gt;\n\n#define maxN    20  \n\nstruct  nodeLink\n{\n\n    char node1;\n    char node2;\n\n};\n\nstruct  stack\n{   \n    int sp;\n    char    node[maxN];\n};   \n\nvoid    initStk(stk)\nstruct  stack   *stk;\n{\n    int i;\n    for (i = 0; i &lt; maxN; i++)\n        stk-&gt;node[i] = \' \';\n    stk-&gt;sp = -1;   \n}\n\nvoid    pushIn(stk, node)\nstruct  stack   *stk;\nchar    node;\n{\n\n    stk-&gt;sp++;\n    stk-&gt;node[stk-&gt;sp] = node;\n\n}    \n\nvoid    popOutAll(stk)\nstruct  stack   *stk;\n{\n\n    char    node;\n    int i, stkN = stk-&gt;sp;\n\n    for (i = 0; i &lt;= stkN; i++)\n    {\n        node = stk-&gt;node[i];\n        if (i == 0)\n            printf("src node : %c", node);\n        else if (i == stkN)\n            printf(" =&gt; %c : dst node.\\n", node);\n        else\n            printf(" =&gt; %c ", node);\n    }\n\n}\n\n\n/* Test whether the node already exists in the stack    */\nbool    InStack(stk, InterN)\nstruct  stack   *stk;\nchar    InterN;\n{\n\n    int i, stkN = stk-&gt;sp;  /* 0-based  */\n    bool    rtn = false;    \n\n    for (i = 0; i &lt;= stkN; i++)\n    {\n        if (stk-&gt;node[i] == InterN)\n        {\n            rtn = true;\n            break;\n        }\n    }\n\n    return     rtn;\n\n}\n\nchar    otherNode(targetNode, lnkNode)\nchar    targetNode;\nstruct  nodeLink    *lnkNode;\n{\n\n    return  (lnkNode-&gt;node1 == targetNode) ? lnkNode-&gt;node2 : lnkNode-&gt;node1;\n\n}\n\nint entries = 8;\nstruct  nodeLink    topo[maxN]    =       \n    {\n        {\'b\', \'a\'}, \n        {\'b\', \'e\'}, \n        {\'b\', \'d\'}, \n        {\'f\', \'b\'}, \n        {\'a\', \'c\'},\n        {\'c\', \'f\'}, \n        {\'c\', \'e\'},\n        {\'f\', \'e\'},               \n    };\n\nchar    srcNode = \'b\', dstN = \'e\';      \n\nint reachTime;  \n\nvoid    InterNode(interN, stk)\nchar    interN;\nstruct  stack   *stk;\n{\n\n    char    otherInterN;\n    int i, numInterN = 0;\n    static  int entryTime   =   0;\n\n    entryTime++;\n\n    for (i = 0; i &lt; entries; i++)\n    {\n\n        if (topo[i].node1 != interN  &amp;&amp; topo[i].node2 != interN) \n        {\n            continue;   \n        }\n\n        otherInterN = otherNode(interN, &amp;topo[i]);\n\n        numInterN++;\n\n        if (otherInterN == stk-&gt;node[stk-&gt;sp - 1])\n        {\n            continue;   \n        }\n\n        /*  Loop avoidance: abandon the route   */\n        if (InStack(stk, otherInterN) == true)\n        {\n            continue;   \n        }\n\n        pushIn(stk, otherInterN);\n\n        if (otherInterN == dstN)\n        {\n            popOutAll(stk);\n            reachTime++;\n            stk-&gt;sp --;   /*    back trace one node  */\n            continue;\n        }\n        else\n            InterNode(otherInterN, stk);\n\n    }\n\n        stk-&gt;sp --;\n\n}\n\n\nint    main()\n\n{\n\n    struct  stack   stk;\n\n    initStk(&amp;stk);\n    pushIn(&amp;stk, srcNode);  \n\n    reachTime = 0;\n    InterNode(srcNode, &amp;stk);\n\n    printf("\\nNumber of all possible and unique routes = %d\\n", reachTime);\n\n}\n</code></pre>\n'}, {'answer_id': 25013511, 'author': 'Avinash', 'author_id': 3116634, 'author_profile': 'https://Stackoverflow.com/users/3116634', 'pm_score': 1, 'selected': False, 'text': '<p>The basic principle is you need not worry about graphs.This is standard problem known as Dynamic connectivity problem. There are following types of methods from which you can achieve nodes are connected or not:</p>\n\n<ol>\n<li>Quick Find</li>\n<li>Quick Union</li>\n<li>Improved Algorithm (Combination of both)</li>\n</ol>\n\n<p>Here is The C Code That I\'ve tried with minimum time complexity O(log*n) That means for 65536 list of edges, it requires 4 search and for 2^65536, it requires 5 search. I am sharing my implementation from the algorithm: <a href="https://www.coursera.org/course/algs4partI" rel="nofollow">Algorithm Course from Princeton university</a> </p>\n\n<p><strong>TIP: You can find Java solution from link shared above with proper explanations.</strong></p>\n\n<pre><code>/* Checking Connection Between Two Edges */\n\n#include&lt;stdio.h&gt;\n#include&lt;stdlib.h&gt;\n#define MAX 100\n\n/*\n  Data structure used\n\nvertex[] - used to Store The vertices\nsize - No. of vertices\nsz[] - size of child\'s\n*/\n\n/*Function Declaration */\nvoid initalize(int *vertex, int *sz, int size);\nint root(int *vertex, int i);\nvoid add(int *vertex, int *sz, int p, int q);\nint connected(int *vertex, int p, int q);\n\nint main() //Main Function\n{ \nchar filename[50], ch, ch1[MAX];\nint temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;\nFILE *fp;\n\n\nprintf("Enter the filename - "); //Accept File Name\nscanf("%s", filename);\nfp = fopen(filename, "r");\nif (fp == NULL)\n{\n    printf("File does not exist");\n    exit(1);\n}\nwhile (1)\n{\n    if (first == 0) //getting no. of vertices\n    {\n        ch = getc(fp);\n        if (temp == 0)\n        {\n            fseek(fp, -1, 1);\n            fscanf(fp, "%s", &amp;ch1);\n            fseek(fp, 1, 1);\n            temp = 1;\n        }\n        if (isdigit(ch))\n        {\n            size = atoi(ch1);\n            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size  \n            sz = (int*) malloc(size * sizeof(int));\n            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]\n        }\n        if (ch == \'\\n\')\n        {\n            first = 1;\n            temp = 0;\n        }\n    }\n    else\n    {\n        ch = fgetc(fp);\n        if (isdigit(ch))\n            temp = temp * 10 + (ch - 48);   //calculating value from ch\n        else\n        {\n            /* Validating the file  */\n\n            if (ch != \',\' &amp;&amp; ch != \'\\n\' &amp;&amp; ch != EOF)\n            {\n                printf("\\n\\nUnkwown Character Detected.. Exiting..!");\n\n                exit(1);\n            }\n            if (ch == \',\')\n                node1 = temp;\n            else\n            {\n                node2 = temp;\n                printf("\\n\\n%d\\t%d", node1, node2);\n                if (node1 &gt; node2)\n                {\n                    temp = node1;\n                    node1 = node2;\n                    node2 = temp;\n                }\n\n                /* Adding the input nodes */\n\n                if (!connected(vertex, node1, node2))\n                    add(vertex, sz, node1, node2);\n            }\n            temp = 0;\n        }\n\n        if (ch == EOF)\n        {\n            fclose(fp);\n            break;\n        }\n    }\n}\n\ndo\n{\n    printf("\\n\\n==== check if connected ===");\n    printf("\\nEnter First Vertex:");\n    scanf("%d", &amp;node1);\n    printf("\\nEnter Second Vertex:");\n    scanf("%d", &amp;node2);\n\n    /* Validating The Input */\n\n    if( node1 &gt; size || node2 &gt; size )\n    {\n        printf("\\n\\n Invalid Node Value..");\n        break;\n    }\n\n    /* Checking the connectivity of nodes */\n\n    if (connected(vertex, node1, node2))\n        printf("Vertex %d and %d are Connected..!", node1, node2);\n    else\n        printf("Vertex %d and %d are Not Connected..!", node1, node2);\n\n\n    printf("\\n 0/1:  ");\n\n    scanf("%d", &amp;temp);\n\n} while (temp != 0);\n\nfree((void*) vertex);\nfree((void*) sz);\n\n\nreturn 0;\n}\n\nvoid initalize(int *vertex, int *sz, int size) //Initialization of graph\n{\nint i;\nfor (i = 0; i &lt; size; i++)\n{\n    vertex[i] = i;\n    sz[i] = 0;\n}\n}\nint root(int *vertex, int i)    //obtaining the root\n{\nwhile (i != vertex[i])\n{\n    vertex[i] = vertex[vertex[i]];\n    i = vertex[i];\n}\nreturn i;\n}\n\n/* Time Complexity for Add --&gt; logn */\nvoid add(int *vertex, int *sz, int p, int q) //Adding of node\n{\nint i, j;\ni = root(vertex, p);\nj = root(vertex, q);\n\n/* Adding small subtree in large subtree  */\n\nif (sz[i] &lt; sz[j])\n{\n    vertex[i] = j;\n    sz[j] += sz[i];\n}\nelse\n{\n    vertex[j] = i;\n    sz[i] += sz[j];\n}\n\n}\n\n/* Time Complexity for Search --&gt;lg* n */\n\nint connected(int *vertex, int p, int q) //Checking of  connectivity of nodes\n{\n/* Checking if root is same  */\n\nif (root(vertex, p) == root(vertex, q))\n    return 1;\n\nreturn 0;\n}\n</code></pre>\n'}, {'answer_id': 26429707, 'author': 'batta', 'author_id': 444047, 'author_profile': 'https://Stackoverflow.com/users/444047', 'pm_score': 2, 'selected': False, 'text': '<p>This may be late, but here\'s the same C# version of DFS algorithm in Java from Casey to traverse for all paths between two nodes using a stack. Readability is better with recursive as always.</p>\n\n<pre class="lang-cs prettyprint-override"><code>    void DepthFirstIterative(T start, T endNode)\n    {\n        var visited = new LinkedList&lt;T&gt;();\n        var stack = new Stack&lt;T&gt;();\n\n        stack.Push(start);\n\n        while (stack.Count != 0)\n        {\n            var current = stack.Pop();\n\n            if (visited.Contains(current))\n                continue;\n\n            visited.AddLast(current);\n\n            var neighbours = AdjacentNodes(current);\n\n            foreach (var neighbour in neighbours)\n            {\n                if (visited.Contains(neighbour))\n                    continue;\n\n                if (neighbour.Equals(endNode))\n                {\n                    visited.AddLast(neighbour);\n                    printPath(visited));\n                    visited.RemoveLast();\n                    break;\n                }\n            }\n\n            bool isPushed = false;\n            foreach (var neighbour in neighbours.Reverse())\n            {\n                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))\n                {\n                    continue;\n                }\n\n                isPushed = true;\n                stack.Push(neighbour);\n            }\n\n            if (!isPushed)\n                visited.RemoveLast();\n        }\n    }\n</code></pre>\n\n<pre>\nThis is a sample graph to test:\n\n    // Sample graph. Numbers are edge ids\n    //       1     3       \n    //    A --- B --- C ----\n    //    |     |  2       |\n    //    | 4   ----- D    |\n    //    ------------------\n</pre>\n'}, {'answer_id': 35531270, 'author': 'Ilmari Karonen', 'author_id': 411022, 'author_profile': 'https://Stackoverflow.com/users/411022', 'pm_score': 3, 'selected': False, 'text': '<p>Since the existing non-recursive DFS implementation given in <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices/26429707#26429707">this answer</a> seems to be broken, let me provide one that actually works.</p>\n\n<p>I\'ve written this in Python, because I find it pretty readable and uncluttered by implementation details (and because it has the handy <code>yield</code> keyword for implementing <a href="https://wiki.python.org/moin/Generators" rel="nofollow noreferrer">generators</a>), but it should be fairly easy to port to other languages.</p>\n\n\n\n<pre class="lang-python prettyprint-override"><code># a generator function to find all simple paths between two nodes in a\n# graph, represented as a dictionary that maps nodes to their neighbors\ndef find_simple_paths(graph, start, end):\n    visited = set()\n    visited.add(start)\n\n    nodestack = list()\n    indexstack = list()\n    current = start\n    i = 0\n\n    while True:\n        # get a list of the neighbors of the current node\n        neighbors = graph[current]\n\n        # find the next unvisited neighbor of this node, if any\n        while i &lt; len(neighbors) and neighbors[i] in visited: i += 1\n\n        if i &gt;= len(neighbors):\n            # we\'ve reached the last neighbor of this node, backtrack\n            visited.remove(current)\n            if len(nodestack) &lt; 1: break  # can\'t backtrack, stop!\n            current = nodestack.pop()\n            i = indexstack.pop()\n        elif neighbors[i] == end:\n            # yay, we found the target node! let the caller process the path\n            yield nodestack + [current, end]\n            i += 1\n        else:\n            # push current node and index onto stacks, switch to neighbor\n            nodestack.append(current)\n            indexstack.append(i+1)\n            visited.add(neighbors[i])\n            current = neighbors[i]\n            i = 0\n</code></pre>\n\n<p>This code maintains two parallel stacks: one containing the earlier nodes in the current path, and one containing the current neighbor index for each node in the node stack (so that we can resume iterating through the neighbors of a node when we pop it back off the stack).  I could\'ve equally well used a single stack of (node, index) pairs, but I figured the two-stack method would be more readable, and perhaps easier to implement for users of other languages.</p>\n\n<p>This code also uses a separate <code>visited</code> set, which always contains the current node and any nodes on the stack, to let me efficiently check whether a node is already part of the current path.  If your language happens to have an "ordered set" data structure that provides both efficient stack-like push/pop operations <em>and</em> efficient membership queries, you can use that for the node stack and get rid of the separate <code>visited</code> set.</p>\n\n<p>Alternatively, if you\'re using a custom mutable class / structure for your nodes, you can just store a boolean flag in each node to indicate whether it has been visited as part of the current search path.  Of course, this method won\'t let you run two searches on the same graph in parallel, should you for some reason wish to do that.</p>\n\n<p>Here\'s some test code demonstrating how the function given above works:</p>\n\n<pre class="lang-python prettyprint-override"><code># test graph:\n#     ,---B---.\n#     A   |   D\n#     `---C---\'\ngraph = {\n    "A": ("B", "C"),\n    "B": ("A", "C", "D"),\n    "C": ("A", "B", "D"),\n    "D": ("B", "C"),\n}\n\n# find paths from A to D\nfor path in find_simple_paths(graph, "A", "D"): print " -&gt; ".join(path)\n</code></pre>\n\n<p>Running this code on the given example graph produces the following output:</p>\n\n<pre>\nA -> B -> C -> D\nA -> B -> D\nA -> C -> B -> D\nA -> C -> D\n</pre>\n\n<p>Note that, while this example graph is undirected (i.e. all its edges go both ways), the algorithm also works for arbitrary directed graphs.  For example, removing the <code>C -&gt; B</code> edge (by removing <code>B</code> from the neighbor list of <code>C</code>) yields the same output except for the third path (<code>A -&gt; C -&gt; B -&gt; D</code>), which is no longer possible.</p>\n\n<hr>\n\n<p><strong>Ps.</strong> It\'s easy to construct graphs for which simple search algorithms like this one (and the others given in this thread) perform very poorly.</p>\n\n<p>For example, consider the task of find all paths from A to B on an undirected graph where the starting node A has two neighbors: the target node B (which has no other neighbors than A) and a node C that is part of a <a href="https://en.wikipedia.org/wiki/Clique_%28graph_theory%29" rel="nofollow noreferrer">clique</a> of <em>n</em>+1 nodes, like this:</p>\n\n<pre class="lang-python prettyprint-override"><code>graph = {\n    "A": ("B", "C"),\n    "B": ("A"),\n    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),\n    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),\n    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),\n    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),\n    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),\n    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),\n    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),\n    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),\n    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),\n    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),\n    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),\n    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),\n    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),\n}\n</code></pre>\n\n<p>It\'s easy to see that the only path between A and B is the direct one, but a naïve DFS started from node A will waste O(<em>n</em>!) time uselessly exploring paths within the clique, even though it\'s obvious (to a human) that none of those paths can possibly lead to B.</p>\n\n<p>One can also construct <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">DAGs</a> with similar properties, e.g. by having the starting node A connect target node B and to two other nodes C<sub>1</sub> and C<sub>2</sub>, both of which connect to the nodes D<sub>1</sub> and D<sub>2</sub>, both of which connect to E<sub>1</sub> and E<sub>2</sub>, and so on.  For <em>n</em> layers of nodes arranged like this, a naïve search for all paths from A to B will end up wasting O(2<sup><em>n</em></sup>) time examining all the possible dead ends before giving up.</p>\n\n<p>Of course, adding an edge to the target node B from one of the nodes in the clique (other than C), or from the last layer of the DAG, <em>would</em> create an exponentially large number of possible paths from A to B, and a purely local search algorithm can\'t really tell in advance whether it will find such an edge or not.  Thus, in a sense, the poor <a href="https://en.wikipedia.org/wiki/Output-sensitive_algorithm" rel="nofollow noreferrer">output sensitivity</a> of such naïve searches is due to their lack of awareness of the global structure of the graph.</p>\n\n<p>While there are various preprocessing methods (such as iteratively eliminating leaf nodes, searching for single-node vertex separators, etc.) that could be used to avoid some of these "exponential-time dead ends", I don\'t know of any general preprocessing trick that could eliminate them in <em>all</em> cases.  A general solution would be to check at every step of the search whether the target node is still reachable (using a sub-search), and backtrack early if it isn\'t &mdash; but alas, that would significantly slow down the search (at worst, proportionally to the size of the graph) for many graphs that <em>don\'t</em> contain such pathological dead ends.</p>\n'}, {'answer_id': 39172826, 'author': 'Jamshed Katta', 'author_id': 4314880, 'author_profile': 'https://Stackoverflow.com/users/4314880', 'pm_score': 0, 'selected': False, 'text': '<p>Adding to Casey Watson\'s answer, here is another Java implementation,. \nInitializing the visited node with the start node.</p>\n\n<pre class="lang-java prettyprint-override"><code>private void getPaths(Graph graph, LinkedList&lt;String&gt; visitedNodes) {\n                LinkedList&lt;String&gt; adjacent = graph.getAdjacent(visitedNodes.getLast());\n                for(String node : adjacent){\n                    if(visitedNodes.contains(node)){\n                        continue;\n                    }\n                    if(node.equals(END)){\n                        visitedNodes.add(node);\n                        printPath(visitedNodes);\n                        visitedNodes.removeLast();\n                    }\n                    visitedNodes.add(node);\n                    getPaths(graph, visitedNodes);\n                    visitedNodes.removeLast();  \n                }\n            }\n</code></pre>\n'}, {'answer_id': 42600378, 'author': 'SumNeuron', 'author_id': 5623899, 'author_profile': 'https://Stackoverflow.com/users/5623899', 'pm_score': 1, 'selected': False, 'text': '<h1>find_paths[s, t, d, k]</h1>\n\n<p>This question is old and answered already. However, none show perhaps a more flexible algorithm for accomplishing the same thing. So I\'ll throw my hat into the ring.</p>\n\n<p>I personally find an algorithm of the form <code>find_paths[s, t, d, k]</code> useful, where:</p>\n\n<ul>\n<li>s is the starting node</li>\n<li>t is the target node</li>\n<li>d is the maximum depth to search</li>\n<li>k is the number of paths to find</li>\n</ul>\n\n<p>Using your programming language\'s form of infinity for <code>d</code> and <code>k</code> will give you all paths§.</p>\n\n<p>§ obviously if you are using a directed graph and you want all <em>undirected</em> paths between <code>s</code> and <code>t</code> you will have to run this both ways:</p>\n\n<pre><code>find_paths[s, t, d, k] &lt;join&gt; find_paths[t, s, d, k]\n</code></pre>\n\n<hr>\n\n<h3>Helper Function</h3>\n\n<p>I personally like recursion, although it can difficult some times, anyway first lets define our helper function:</p>\n\n<pre><code>def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)\n  current_path.append(current)\n\n  if current_depth &gt; max_depth:\n    return\n\n  if current == goal:\n    if len(paths_found) &lt;= number_of_paths_to_find:\n      paths_found.append(copy(current_path))\n\n    current_path.pop()\n    return\n\n  else:\n    for successor in graph[current]:\n    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)\n\n  current_path.pop()\n</code></pre>\n\n<h3>Main Function</h3>\n\n<p>With that out of the way, the core function is trivial:</p>\n\n<pre><code>def find_paths[s, t, d, k]:\n  paths_found = [] # PASSING THIS BY REFERENCE  \n  find_paths_recursion(s, t, 0, d, k, [], paths_found)\n</code></pre>\n\n<hr>\n\n<p>First, lets notice a few thing:</p>\n\n<ul>\n<li>the above pseudo-code is a mash-up of languages - but most strongly resembling python (since I was just coding in it). A strict copy-paste will not work.</li>\n<li><code>[]</code> is an uninitialized list, replace this with the equivalent for your programming language of choice</li>\n<li><code>paths_found</code> is passed by <strong>reference</strong>. It is clear that the recursion function doesn\'t return anything. Handle this appropriately.</li>\n<li>here <code>graph</code> is assuming some form of <code>hashed</code> structure. There are a plethora of ways to implement a graph. Either way, <code>graph[vertex]</code> gets you a list of adjacent vertices in a <em>directed</em> graph - adjust accordingly.</li>\n<li>this assumes you have pre-processed to remove "buckles" (self-loops),  cycles and multi-edges</li>\n</ul>\n'}]
['https://Stackoverflow.com/questions/58306', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/3534/']