-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Common graph search algorithms
--
-- Library containing common graph search algorithms, including
-- depth-first and breadth-first searches, Dijkstra's algorithm, and A*
@package search-algorithms
@version 0.1.0
-- | This module contains a collection of generalized graph search
-- algorithms, for when you don't want to explicitly represent your data
-- as a graph. The general idea is to provide these algorithms with a way
-- of generating "next" states (and associated information), a way of
-- determining when you have found a solution, a way of pruning out "dead
-- ends", and an initial state.
module Algorithm.Search
-- | bfs next prunes found initial performs a breadth-first search
-- over a set of states, starting with initial, generating
-- neighboring states with next, and pruning out any state for
-- which a function in prunes returns True. It returns a
-- path to a state for which found returns True. Returns
-- Nothing if no path is possible.
--
-- Example: Making change problem
--
--
-- >>> :{
-- countChange target = bfs add_one_coin [(> target)] (== target) 0
-- where
-- add_one_coin amt = map (+ amt) coins
-- coins = [25, 10, 5, 1]
-- :}
--
--
--
-- >>> countChange 67
-- Just [25,50,60,65,66,67]
--
bfs :: Ord state => (state -> [state]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe [state]
-- | dfs next prunes found initial performs a depth-first search
-- over a set of states, starting with initial, generating
-- neighboring states with next, and pruning out any state for
-- which a function in prunes returns True. It returns a
-- depth-first path to a state for which found returns
-- True. Returns Nothing if no path is possible.
--
-- Example: Simple directed graph search
--
--
-- >>> import qualified Data.Map as Map
--
--
--
-- >>> graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]
--
--
--
-- >>> dfs (graph Map.!) [] (== 4) 1
-- Just [3,4]
--
dfs :: Ord state => (state -> [state]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe [state]
-- | dijkstra next prunes found initial performs a shortest-path
-- search over a set of states using Dijkstra's algorithm, starting with
-- initial, generating neighboring states and their incremental
-- costs with next, and pruning out any state for which a
-- function in prunes returns True. This will find the
-- least-costly path from an initial state to a state for which
-- found returns True. Returns Nothing if no path
-- to a solved state is possible.
--
-- Example: Making change problem, with a twist
--
--
-- >>> :{
-- -- Twist: dimes have a face value of 10 cents, but are actually rare
-- -- misprints which are worth 10 dollars
-- countChange target = dijkstra add_one_coin [(> target)] (== target) 0
-- where
-- add_one_coin amt =
-- map (\(true_val, face_val) -> (true_val, face_val + amt)) coin_values
-- coin_values = [(25, 25), (1000, 10), (5, 5), (1, 1)]
-- :}
--
--
--
-- >>> countChange 67
-- Just (67,[(1,1),(1,2),(5,7),(5,12),(5,17),(25,42),(25,67)])
--
dijkstra :: (Num cost, Ord cost, Ord state) => (state -> [(cost, state)]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe (cost, [(cost, state)])
-- | aStar next prunes found initial performs a best-first search
-- using the A* search algorithm, starting with the state
-- initial, generating neighboring states, their cost, and an
-- estimate of the remaining cost with next, and pruning out any
-- state for which a function in prunes returns True.
-- This returns a path to a state for which found returns
-- True. If the estimate is strictly a lower bound on the
-- remaining cost to reach a solved state, then the returned path is the
-- shortest path. Returns Nothing if no path to a solved state is
-- possible.
--
-- Example: Path finding in taxicab geometry
--
--
-- >>> :{
-- neighbors (x, y) = [(x, y + 1), (x - 1, y), (x + 1, y), (x, y - 1)]
-- dist (x1, y1) (x2, y2) = abs (y2 - y1) + abs (x2 - x1)
-- nextTowards dest pos = map (\p -> (1, dist p dest, p)) (neighbors pos)
-- :}
--
--
--
-- >>> aStar (nextTowards (0, 2)) [(== (0, 1))] (== (0, 2)) (0, 0)
-- Just (4,[(1,(1,0)),(1,(1,1)),(1,(1,2)),(1,(0,2))])
--
aStar :: (Num cost, Ord cost, Ord state) => (state -> [(cost, cost, state)]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe (cost, [(cost, state)])
instance Algorithm.Search.SearchContainer (Data.Sequence.Seq a) a
instance Algorithm.Search.SearchContainer [a] a
instance GHC.Classes.Ord k => Algorithm.Search.SearchContainer (Algorithm.Search.LIFOHeap k a) (k, a)