# search-algorithms: Common graph search algorithms

[ algorithm, bsd3, library ] [ Propose Tags ]

Library containing common graph search algorithms, including depth-first and breadth-first searches, Dijkstra's algorithm, and A*

Versions [RSS] [faq] 0.1.0, 0.2.0, 0.3.0, 0.3.1 base (>=4.7 && <5), containers (>=0.5) [details] BSD-3-Clause 2017 Devon Hollowood Devon Hollowood devonhollowood@gmail.com Algorithm https://github.com/devonhollowood/search-algorithms#readme head: git clone https://github.com/devonhollowood/search-algorithms by devonhollowood at 2017-03-08T21:47:16Z LTSHaskell:0.3.1, NixOS:0.3.1, Stackage:0.3.1 2575 total (33 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2017-03-08

## Modules

[Index]

#### Maintainer's Corner

For package maintainers and hackage trustees

Candidates

• No Candidates

[back to package description]

# search-algorithms

Haskell library containing common graph search algorithms

Lots of problems can be modeled as graphs, but oftentimes one doesn't want to use an explicit graph structure to represent the problem. Maybe the graph would be too big (or is infinite), maybe making an explicit graph is unwieldy for the problem at hand, or maybe one just wants to generalize over graph implementations. That's where this library comes in: this is a collection of generalized search algorithms, so that one doesn't have to make the graphs explicit. In general, this means that one provides each search function with a function to generate neighboring states, a list of predicates which tell whether a "dead end" has been reached, a predicate which tells when the search is complete, and an initial state to start from. The result is a path from the initial state to a "solved" state, or Nothing if no such path is possible.

## Examples

### Change-making problem

import Algorithm.Search (bfs)

countChange target = bfs add_one_coin [(> target)] (== target) 0
where
add_one_coin amt = map (+ amt) coins
coins = [1, 5, 10, 25]

-- countChange gives the subtotals along the way to the end:
-- >>> countChange 67
-- Just [1, 2, 7, 17, 42, 67]


### Simple directed acyclic graph:

import Algorithm.Search (dfs)
import qualified Data.Map as Map

graph = Map.fromList [
(1, [2, 3]),
(2, [4]),
(3, [4]),
(4, [])
]

-- Run dfs on the graph:
-- >>> dfs (graph Map.!) [] (== 4) 1
-- Just [3,4]


### Using A* to find a path in an area with a wall:

import Algorithm.Search (aStar)

taxicabNeighbors :: (Int, Int) -> [(Int, Int)]
taxicabNeighbors (x, y) = [(x, y + 1), (x - 1, y), (x + 1, y), (x, y - 1)]

isWall :: (Int, Int) -> Bool
isWall (x, y) = x == 1 && (-2) <= y && y <= 1

taxicabDistance :: (Int, Int) -> (Int, Int) -> Int
taxicabDistance (x1, y1) (x2, y2) = abs (x2 - x1) + abs (y2 - y1)

findPath :: (Int, Int) -> (Int, Int) -> Maybe (Int, [(Int, (Int, Int))])
findPath start end =
let next =
map (\pt -> (1, taxicabDistance pt end, pt))
. taxicabNeighbors
in aStar next [isWall] (== end) start

-- findPath p1 p2 finds a path between p1 and p2, avoiding the wall
-- >>> findPath (0, 0) (2, 0)
-- Just (6,[(1,(0,1)),(1,(0,2)),(1,(1,2)),(1,(2,2)),(1,(2,1)),(1,(2,0))])
--
-- This correctly goes up and around the wall