Traversing a graph breadth first, marking visited nodes in Haskell

Question

So the question is simple. Given a graph (I hope that the structure of the graph doesn't matter much in this problem), how do I go about doing a BFS on it?

I've recently asked a question about generating a list where each element appends many elements to the end of it. The answer should hopefully let me make a queue I need to do the BFS. But there's another key component that a search needs and it's marking the nodes as visited so we don't go over them again. This also needs to have no overhead on the execution of the algorithm. Neither marking or reading.

Since Haskell doesn't let me change state, how would I go about doing that?

(I'm not looking for a way to translate my imperative code to Haskell. An idiomatic Haskell solution would be great.)

Answer 1

As mentioned in the comments, a proper approach is to separate your graph from marking its nodes. You need to use some kind of a set container. There are basically two approaches you can take:

1. Use a functional set. Although at every modification a new version is created, functional data structures are designed so that only a very small part actually changes and most of the original one is shared. Insert/lookup operations take O(log n) for such structures. But HashSet from unordered-containers is optimized for speed and the base of the logarithm is large, so for most purposes the factor is like constant.
2. Use the ST monad (see also this question). Inside the monad you can use mutable data structures, while the result will be still referentially transparent. Then you can use for example ST-based hash tables from the hashtables package. This allows you to get rid of the log n factor and do operations on hash tables in constant time. But there are other drawbacks, for example that your traversal must be pure. If works within some other monad, you won't be able to interleave it with ST operations.

Answer 2

The paper Inductive Graphs and Functional Graph Algorithms discusses such problems and is quite readable. It is the basis of the fgl package, which has an entire module for BFS-like queries. I highly recommend the paper -- it was an eye-opening read for me (namely, the underlying core idea of "give an inductive interface even if your data isn't inductive" was an awesome one) -- and further recommend that if you can use the fgl package you do. But if you can't, the paper will tell you enough to write an algorithm for your custom data type, I'm sure.

Answer 3

I think, the simplest way to look at this is to look at any level in the tree graph.

• At any level, there are n nodes.
• The BF traversal at this level will traverse these n nodes, and
• BF traversal of children of these n nodes.

This is now easy to translate, (this code flattens the graph breadth first).

toBFSList :: [Graph a] -> [Graph a]
toBFSList [] = [] -- trivial case
toBFSList gs = ns ++ fs 
    where ns = map extract gs -- "extract" may extract a single node
          cs = concat $ map children gs   -- get all the child nodes for all above node
          fs = toBFSList cs   -- for all children, do traversal