title: Get a list of paths through a graph
body: <p>
  I am trying to get a list of lists of all possible paths through a graph with a given starting point and a destination. 
  The graph is given as follows:
  </p>
  
  <pre><code>data Node = N1 | N2 | N3 | N4 | N5 deriving (Show, Eq)
  
  neighbor :: Node -&gt; [Node]
  neighbor N1 = [N2, N4, N5]
  neighbor N2 = [N1, N3]
  neighbor N3 = [N1, N4, N5]
  neighbor N4 = [N5]
  neighbor N5 = [N1]
  </code></pre>
  
  <p>The problem is: given a start node and a destination node (e.g. start node = N1 and destination = N4) all possible routes, without cycles, leading from start to destination shall be the result. In the example given it would be: </p>
  
  <pre><code>[[N1, N2, N3, N4],[N1, N4]]
  </code></pre>
  
  <p>The function I am trying to solve this problem with is: </p>
  
  <pre><code>generatePaths :: (Node -&gt; [Node]) -&gt; Node -&gt; Node -&gt; [[Node]]
  </code></pre>
  
  <p>Here the first argument shall be the neighbor function, the second the start node and the third the destinaion node. </p>
  
  <p>My main problem is that I find now way on how to iterate through all neighbors and call <code>generatePaths</code> with every neighbor as new start node. </p>
  
  <p>Any help is highly appreciated</p>
  
  <p>EDIT:
  Thx to Krom and RoadRunner I came up with an implementation. </p>
  
  <pre><code>dfs_h :: (Node -&gt; [Node]) -&gt; [Node] -&gt; [Node] -&gt; Node -&gt; [[Node]]
  dfs_h graph visited [] _ = [visited]
  dfs_h graph visited (n:ns) end 
      | elem n visited = (dfs_h graph visited ns end)
      | elem end ns = [reverse (end:visited)] ++ (dfs_h graph visited (n:[neigh|neigh &lt;- ns, neigh /= end]) end)
      | n == end = [reverse (end:visited)] ++ (dfs_h graph visited ns end)
      | otherwise = dfs_h graph (n:visited) ((graph n) ++ ns) end
  
  dfs start end = filter (\x -&gt; elem end x) (dfs_h neighbor [start] (neighbor start) end                         
  </code></pre>
  
  <p>I am aware that this isn't the most beautiful solution, just the first I came up with. </p>
  
  <p>EDIT2: 
  But a problem with this algorithm is when the graph looks like this: </p>
  
  <pre><code>neighbor :: Node -&gt; [Node]
  neighbor N1 = [N2, N3]
  neighbor N2 = [N5]
  neighbor N3 = [N4]
  neighbor N4 = [N2, N1]
  neighbor N5 = [N1]
  </code></pre>
  
  <p>and a path from <code>N1</code> to <code>N4</code> shall be found then the result of the function is </p>
  
  <pre><code>[[N1, N2, N5, N3, N4]]
  </code></pre>
  
  <p>Now I don't what to implement so that the <code>N2</code> and <code>N5</code>, which should not be part of the solution, don't get included. 
  Any suggenstions?</p>