Book Image

Haskell Data Analysis cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis cookbook

By: Nishant Shukla

Overview of this book

Step-by-step recipes filled with practical code samples and engaging examples demonstrate Haskell in practice, and then the concepts behind the code. This book shows functional developers and analysts how to leverage their existing knowledge of Haskell specifically for high-quality data analysis. A good understanding of data sets and functional programming is assumed.
Table of Contents (14 chapters)
13
Index

Traversing a graph breadth-first


Using breadth-first search, one can traverse a graph to view the nodes in the desired order. In an infinite graph, a depth-first traversal may never return back to the starting node. One of the most notable examples of a breadth-first traversal algorithm is finding the shortest path between two nodes.

In this recipe, we will print out the breadth-first traversal of the nodes in a graph.

How to do it...

Insert the following code in a new file, which can be called Main.hs:

  1. Import the required packages:

    import Data.Graph
    import Data.Array ((!))
  2. Construct the graph from a list of edges:

    graph :: Graph
    graph = buildG bounds edges
      where  bounds = (1,7)
             edges = [ (1,2), (1,5)
                     , (2,3), (2,4) 
                     , (5,6), (5,7) 
                     , (3,1) ]
  3. Scan the graph breadth-first:

    breadth g i = bf [] [i]
      where bf :: [Int] -> [Int] -> [Int]
            bf seen forest | null forest = []
                           | otherwise   = forest ++ 
         ...