Weighters.hs

{-# LANGUAGE ScopedTypeVariables #-}

module Graph.DijkstraSimple.Weighters
  (
                                      -- * How weighters are used
                                      -- $use
    cumulativeWeighter
  , maximumWeightWeighter
  )
where

import           Graph.DijkstraSimple

-- | The classical weighter: the weight of a path is the sum of each edge
-- weight.
cumulativeWeighter :: Num e => Weighter v e e
cumulativeWeighter = Weighter 0 $ \e p -> pathWeight p + edgeToWeight e

-- | Here we are looking for the heaviest edge weight
maximumWeightWeighter :: (Bounded e, Ord e) => Weighter v e e
maximumWeightWeighter =
  Weighter minBound $ \e p -> max (pathWeight p) (edgeToWeight e)

-- $use
--
-- Weighters requires two components:
--
--  - a value for the initial weight of a @Path@
--  - a function which gives a new output weight from an input weight (the edge weight) and a @Path@
--
-- The algorithm will try to minimize the output weight of paths.
--
-- Be sure that the output weight is always positive, it is not checked,
-- but it will break the algorithm.