Is it possible to implement linear temporary BFS in Haskell?

Question

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

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

G has n vertices and m edges. I am trying to implement the BFS algorithm in Haskell, which works in O (m) time (perhaps amortized), but the best solution I could find in O (m * log n) was using the data structure from the Data.Map module.

My idea of ​​a linear solution is this: use the structure from Data.Sequence as an efficient FIFO queue and do whatever it takes to execute BFS, but I'm stuck at the point where I need to mark nodes as visited.

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

Answer 1

I assume your problem is that you cannot implement a good queue.

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

Once it's your turn, it should work just as well as DFS.

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

To mark marked nodes, you can use 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 

Please note that the way to create this list is completely lazy! Therefore, if you need only the first half of BFS, this will not calculate the rest.