haskellfunctional-programminginfinite-loopdepth-first-search# Haskell Depth-First Graph Traversal has Infinite Loop

I have spent some time recently trying to make a depth-first traversal algorithm in Haskell. However, with my one I would like the function to return a 'visited' list, which has every node visited in order.

Demonstration: with the graph `[('A', "BC"), ('B', "ACD"), ('C', "AB"), ('D', "B")]`

the output should be `"ABCBD"`

since I am starting on `A`

and finishing on `D`

.

Here is my code:

```
import Data.List (elemIndex)
trav :: [(Char, String)] -> Char -> Char -> String -> String
trav [] _ _ _ = []
trav graph node endNode visited
| not (elem node visited) = trav graph node endNode (visited ++ [node]) -- repeat but after adding this node to visited list.
| node == endNode = visited
| not (null unvisitedNodes) = trav graph (head unvisitedNodes) endNode visited
| not (null visited) = if (length prevIndex) > 1 then (trav graph (visited !! (getIndex (head prevIndex) visited)) endNode (visited ++ [(visited !! (getIndex (head prevIndex) visited))])) else (trav graph (head (tail (reverse visited))) endNode (visited ++ [(head (tail (reverse visited)))]))
| otherwise = visited
where
unvisitedNodes = [x | x <- getAttachedVertexes graph node, not (elem x visited)]
prevIndex = [x | x <- (reverse visited), x < (head (reverse visited))]
getAttachedVertexes :: [(Char, String)] -> Char -> [Char]
getAttachedVertexes graph node = case lookup node graph of
Just value -> value
Nothing -> ""
getIndex :: Eq a => a -> [a] -> Int
getIndex item list = case elemIndex item list of
Just index -> index
Nothing -> error "help"
```

This code actually works fine and outputs the demonstrated ideal output which I wrote above when inputted with the following: `trav [('A', "BC"), ('B', "ACD"), ('C', "AB"), ('D', "B")] 'A' 'D' ""`

However, this code starts an infinite recursion loop when I enter the following input: `trav [('A', "CDE"), ('B', "D"), ('C', "AD"), ('D', "ABC"), ('E', "A")] 'A' 'E' ""`

There is obviously no error message as it's an infinite loop.

My thought process:

I have just edited this question with an updated Haskell code, which is the result of the below thinking:

I first thought that part of the problem was that, when backtracking, the node which was backtracked to was added to the `visited`

list, meaning that when I do `head (tail (reverse visited))`

the item that returns is actually the same node that is currently being traversed.

I 'translated' this code into Python 3, which is the language I have the most experience in, and kept it in Haskell format, i.e. a function containing a series of `if`

statements all with a `return`

line within them.

Next, I attempted to fix the above error. It returns the correct output for the first input I said above (`{"A":["B", "C"], "B":["A", "C", "D"], "C":["A", "B"], "D":["B"]}`

) however, when I try the second input above (`{"A":['C', 'D', 'E'], "B":['D'], "C":['A','D'], "D":['A','B','C'], "E":['A']}`

) it again starts an infinite loop (well, at least until the stack overflows).

Here is said Python code:

```
def trav(graph, node, endNode, visited):
if node not in visited:
return trav(graph, node, endNode, (visited + [node]))
if node == endNode:
return visited
unvisitedNodes = [x for x in getAttachedNodes(graph, node) if x not in visited]
if len(unvisitedNodes) > 0:
return trav(graph, unvisitedNodes[0], endNode, visited)
if len(visited) > 0:
prevIndex = [x for x in reversed(visited) if x < visited[-1]]
if len(prevIndex) > 1:
return trav(graph, visited[visited.index(prevIndex[0])], endNode, (visited + [visited[visited.index(prevIndex[0])]]))
else:
return trav(graph, visited[-2], endNode, (visited + [visited[-2]]))
return visited
if __name__ == '__main__':
graph1 = {"A":["B", "C"], "B":["A", "C", "D"], "C":["A", "B"], "D":["B"]}
node = input("Node: ")
endNode = input("EndNode: ")
graph2 = {"A":['C', 'D', 'E'], "B":['D'], "C":['A','D'], "D":['A','B','C'], "E":['A']}
visited = []
print(trav(graph2, node, endNode, visited))
```

I have since re-written the Haskell code, and it now runs exactly the same way in all tested cases as the above Python code. Obviously this only helps those who are capable in Python. I wrote it to hopefully be able to understand the problem. My next edit will be the result of the debugging of this Python code.

I apologise for it's messiness and inefficiency, but I want to mirror as closely as possible the above Haskell code.

Anyway, I included this to hopefully make clearer my algorithm.

In conclusion, the problem was not what I explained I thought it was just above.

Thanks again.

Solution

I have just solved this. Here is the updated Haskell code:

```
import Data.List (elemIndex)
trav :: [(Char, String)] -> Char -> Char -> String -> String
trav [] _ _ _ = []
trav graph node endNode visited
| not (elem node visited) = trav graph node endNode (visited ++ [node]) -- repeat but after adding this node to visited list.
| node == endNode = visited
| not (null unvisitedAttachedNodes) = trav graph (head unvisitedAttachedNodes) endNode visited
| not (null visited) = if not (null attachedNodesWithUnvisited) then (trav graph (head attachedNodesWithUnvisited) endNode (visited ++ [(head attachedNodesWithUnvisited)])) else (trav graph (head (tail (reverse visited))) endNode (visited ++ [head (tail (reverse visited))]))
| otherwise = visited
where
unvisitedAttachedNodes = [x | x <- getAttachedVertexes graph node, not (elem x visited)]
prevIndex = [x | x <- (reverse visited), x < (head (reverse visited))]
unvisitedPrevNodes = [x | x <- prevIndex, elem x [y | y <- (getAttachedVertexes graph x), not (elem y visited)]]
nodeToGoBackTo = visited !! (getIndex (head (reverse unvisitedPrevNodes)) visited)
attachedNodesWithUnvisited = [nb | nb <- (getAttachedVertexes graph node), (hasUnvisited graph nb visited)]
getAttachedVertexes :: [(Char, String)] -> Char -> [Char]
getAttachedVertexes graph node = case lookup node graph of
Just value -> value
Nothing -> ""
hasUnvisited :: [(Char, String)] -> Char -> String -> Bool
hasUnvisited graph node visited = not (null unvisited) where
unvisited = [x | x <- (getAttachedVertexes graph node), not (elem x visited)]
count :: Eq a => a -> [a] -> Int
count item list = length (filter (== item) list)
getIndex :: Eq a => a -> [a] -> Int
getIndex item list = case elemIndex item list of
Just index -> index
Nothing -> error "help"
```

and here is the updated equivalent Python code:

```
def trav(graph, node, endNode, visited):
if node not in visited:
return trav(graph, node, endNode, (visited + [node]))
if node == endNode:
return visited
unvisitedAttachedNodes = [x for x in getAttachedNodes(graph, node) if x not in visited]
if len(unvisitedAttachedNodes) > 0:
return trav(graph, unvisitedAttachedNodes[0], endNode, visited)
if len(visited) > 0: # needs to backtrack
attachedNodesWithUnvisited = [nb for nb in graph[node] if has_unvisited(graph, nb, visited)]
if len(attachedNodesWithUnvisited) > 0:
return trav(graph, attachedNodesWithUnvisited[0], endNode, visited + [attachedNodesWithUnvisited[0]])
else:
return trav(graph, visited[-2], endNode, visited + [visited[-2]])
return visited
```

I realised that the infinite loop was caused by, whenever backtracking was necessary, the program only went back by one node, but then added that node to the visited list, so `head (tail (reverse visited))`

(or Python equivalent `visited[-2]`

meant the program kept going between two nodes. As you can see clearly in the new Python translation, I am now going to `visited[-2]`

*unless* there is an attached nodes with unvisited neighbouring nodes.

this now works with all the graphs I have tested with it.

Thanks very much for everyone's help!

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code