Is it possible to implement linear time BFS in Haskell?

Question

I have a directed graph G given as a list of adjacency lists:

newtype Graph Int = Graph [(Int, [Int])]

G has n vertices and m edges. I'm trying to implement BFS algorithm in Haskell that runs in O(m) time (maybe amortized), but best solution I was able to come up with runs in O(m * log n) and uses data structure from Data.Map module.

My idea of linear solution is as follows: Use structure from Data.Sequence as efficient FIFO queue and do everything as imperative BFS would do, but I'm stuck at point where I have to mark nodes as visited.

My question is: Is it possible to implement BFS in Haskell (or any other purely functional language) that runs in O(m)? And if It's not, what argument can you use to prove such statement?

Answer 1

I'm presuming your problem is that you can't implement a good queue.

Take a look at Data.Sequence - it should do fine for a double ended queue, because operations towards the end of a sequence are incredibly fast. Adding an element to either end is O(1) and removing an element from either end is O(1).

Once you have the queue, it should perform just as well as a DFS would.

Instead of using a Map Int [Int] you can probably get away with a Vector Int [Int] (if your vertices are integers from 1 to n)

To mark nodes as checked you can use an IntSet.

This should get you O(V + E).

bfs :: V.Vector [Int] -> Int -> [Int]
bfs graph start = go IS.empty graph $ S.singleton start

go :: IS.IntSet Int -> V.Vector [Int] -> S.Sequence Int -> [Int]
go seen graph queue = 
  case S.viewL queue of
    S.EmptyL -> []
    vertex S.:< rest = vertex:(go seen' graph queue')
      where neighbors = filter (not . IS.member seen) (graph V.! vertex)
            seen' = S.insert vertex seen
            queue' = queue S.>< S.fromList neighbors

Note that the way we build this list is totally lazy! So if you only needed for example the first half of the BFS it would not calculate the rest.