packages feed

dijkstra-simple (empty) → 0.1.0

raw patch · 9 files changed

+362/−0 lines, 9 filesdep +basedep +containersdep +dijkstra-simplesetup-changed

Dependencies added: base, containers, dijkstra-simple, fingertree, hspec

Files

+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Gautier DI FOLCO (c) 2020++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Gautier DI FOLCO nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,38 @@+# dijkstra-simple++A simpler Dijkstra shortest paths implementation++## Basic usage+This section contains basic step-by-step usage of the library.++The first step is to build a direct graph:++```+exampleGraph :: Graph Char Int+exampleGraph = Graph $ M.fromList [+                                    ('A', [EdgeTo 'B' 3, EdgeTo 'C' 1])+                                  , ('B', [EdgeTo 'A' 3, EdgeTo 'C' 7, EdgeTo 'D' 5, EdgeTo 'E' 1])+                                  , ('C', [EdgeTo 'A' 1, EdgeTo 'B' 7, EdgeTo 'D' 2])+                                  , ('D', [EdgeTo 'B' 5, EdgeTo 'C' 2, EdgeTo 'E' 5])+                                  , ('E', [EdgeTo 'B' 1, EdgeTo 'D' 7])+                                  ]+```++Then pick or create a weighter (see `Graph.DijkstraSimple.Weighters`)+and apply it all:++```+lightestPaths exampleGraph 'C' weighter+```++It will give all the reacheable vertices from `'C'` and associated shortest path:++```+Paths $ M.fromList [+                     ('A', Path (fromList "AC") 1)+                   , ('B', Path (fromList "BAC") 3)+                   , ('C', Path (fromList "CAC") 1)+                   , ('D', Path (fromList "DC") 2)+                   , ('E', Path (fromList "EBAC") 3)+                   ]+```
+ Setup.hs view
@@ -0,0 +1,2 @@+import           Distribution.Simple+main = defaultMain
+ changelog.md view
@@ -0,0 +1,3 @@+### 0.1.0++ - Introduce the library
+ dijkstra-simple.cabal view
@@ -0,0 +1,59 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.33.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: cf0803a47914ce38f8b1478f18cebd21c0666efecac0668508cf3839859c512f++name:           dijkstra-simple+version:        0.1.0+synopsis:       A simpler Dijkstra shortest paths implementation+description:    Provides a simplistic Dijkstra implementation with some useful variations and generalizations.+category:       graph, dijkstra+homepage:       https://github.com/blackheaven/dijkstra-simple#readme+bug-reports:    https://github.com/blackheaven/dijkstra-simple/issues+author:         Gautier DI FOLCO+maintainer:     gautier.difolco@gmail.com+copyright:      Gautier DI FOLCO+license:        BSD3+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    changelog.md+    README.md++source-repository head+  type: git+  location: https://github.com/blackheaven/dijkstra-simple++library+  exposed-modules:+      Graph.DijkstraSimple+      Graph.DijkstraSimple.Weighters+  other-modules:+      Paths_dijkstra_simple+  hs-source-dirs:+      src+  build-depends:+      base >=4.7 && <5+    , containers >=0.6.2.1 && <0.7+    , fingertree >=0.1.4.0 && <0.1.5+  default-language: Haskell2010++test-suite dijkstra-simple-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Graph.DijkstraSimpleSpec+      Paths_dijkstra_simple+  hs-source-dirs:+      test+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      base >=4.7 && <5+    , containers >=0.6.2.1 && <0.7+    , dijkstra-simple+    , fingertree >=0.1.4.0 && <0.1.5+    , hspec >=2.7.1 && <2.8+  default-language: Haskell2010
+ src/Graph/DijkstraSimple.hs view
@@ -0,0 +1,139 @@+{-# LANGUAGE ScopedTypeVariables #-}++module Graph.DijkstraSimple+  (+                            -- * How to use this library+                            -- $use+    lightestPaths+  , findPath+  , dijkstraSteps+  , EdgeTo(..)+  , Graph(..)+  , Weighter(..)+  , Path(..)+  , Paths(..)+  )+where++import qualified Data.Map.Lazy                 as M+import qualified Data.List.NonEmpty            as NE+import           Data.Maybe                     ( fromJust+                                                , isJust+                                                , isNothing+                                                )+import           Data.Ord                       ( comparing )+import qualified Data.PriorityQueue.FingerTree as P++-- | Edge to an arbitrary vertex and the associated input weight+data EdgeTo v e = EdgeTo { edgeTo :: v, edgeToWeight :: e } deriving (Eq, Show)++-- | All vertices and outgoing edges+newtype Graph v e = Graph { graphAsMap :: M.Map v [EdgeTo v e] } deriving (Eq, Show)++-- | Convert an input weight (edge-dependant) to an output weight+-- (path-dependant) for the algorithm work.+data Weighter v e a = Weighter { initialWeight :: a, weight :: EdgeTo v e -> Path v e a -> a }+-- | The lightest found path with reverse ordered list of traversed+-- vertices and output weight.+data Path v e a = Path { pathVertices :: NE.NonEmpty v, pathWeight :: a } deriving (Eq, Show)+-- | Reachable vertices and associated lightest paths+newtype Paths v e a = Paths { pathsAsMap :: M.Map v (Path v e a) } deriving (Eq, Show)++-- | Explore all the reachable edges+lightestPaths+  :: forall v e a+   . (Ord v, Ord a)+  => Graph v e+  -> v+  -> Weighter v e a+  -> Paths v e a+lightestPaths graph origin weighter =+  NE.last $ dijkstraSteps graph origin weighter++-- | Find the eventual path between two edges+findPath+  :: forall v e a+   . (Ord v, Ord a)+  => Graph v e+  -> v+  -> Weighter v e a+  -> v+  -> Maybe (Path v e a)+findPath graph origin weighter target =+  pathsAsMap (lightestPaths graph origin weighter) M.!? target++type StatePQ v e a = P.PQueue a (Path v e a, EdgeTo v e)+type State v e a+  = (M.Map v (Path v e a), ((a, (Path v e a, EdgeTo v e)), StatePQ v e a))++-- | Details each step of the Dijkstra algorithm+dijkstraSteps+  :: forall v e a+   . (Ord v, Ord a)+  => Graph v e+  -> v+  -> Weighter v e a+  -> NE.NonEmpty (Paths v e a)+dijkstraSteps graph origin weighter =+  Paths <$> maybe (M.empty NE.:| []) (NE.unfoldr nextStep) init+ where+  init :: Maybe (State v e a)+  init =+    (\p -> (M.empty, p))+      <$> (P.minViewWithKey $ findEdges+            (Path (origin NE.:| []) (initialWeight weighter))+            origin+          )+  nextStep :: State v e a -> (M.Map v (Path v e a), Maybe (State v e a))+  nextStep (paths, ((w, (path, e)), pq)) =+    let npq = if M.notMember (edgeTo e) paths+          then pq `P.union` findEdges path (edgeTo e)+          else pq+        nps = M.alter (updatePath path) (edgeTo e) paths+    in  (nps, (\q -> (nps, q)) <$> P.minViewWithKey npq)+  updatePath :: Path v e a -> Maybe (Path v e a) -> Maybe (Path v e a)+  updatePath p prev = case prev of+    Nothing -> Just p+    Just op -> Just $ if pathWeight op <= pathWeight p then op else p+  findEdges :: Path v e a -> v -> StatePQ v e a+  findEdges path vertice =+    P.fromList+      $ map (buildPath path)+      $ M.findWithDefault [] vertice+      $ graphAsMap graph+  buildPath :: Path v e a -> EdgeTo v e -> (a, (Path v e a, EdgeTo v e))+  buildPath path e = let np = addEdge e path in (pathWeight np, (np, e))+  addEdge :: EdgeTo v e -> Path v e a -> Path v e a+  addEdge e p = Path { pathVertices = edgeTo e NE.<| pathVertices p+                     , pathWeight   = weight weighter e p+                     }++-- $use+--+-- This section contains basic step-by-step usage of the library.+--+-- The first step is to build a direct graph:+--+-- > exampleGraph :: Graph Char Int+-- > exampleGraph = Graph $ M.fromList [+-- >                                     ('A', [EdgeTo 'B' 3, EdgeTo 'C' 1])+-- >                                   , ('B', [EdgeTo 'A' 3, EdgeTo 'C' 7, EdgeTo 'D' 5, EdgeTo 'E' 1])+-- >                                   , ('C', [EdgeTo 'A' 1, EdgeTo 'B' 7, EdgeTo 'D' 2])+-- >                                   , ('D', [EdgeTo 'B' 5, EdgeTo 'C' 2, EdgeTo 'E' 5])+-- >                                   , ('E', [EdgeTo 'B' 1, EdgeTo 'D' 7])+-- >                                   ]+--+-- Then pick or create a weighter (see @Graph.DijkstraSimple.Weighters@)+-- and apply it all:+--+-- > lightestPaths exampleGraph 'C' weighter+--+-- It will give all the reacheable vertices from @'C'@ and associated shortest path:+--+-- > Paths $ M.fromList [+-- >                      ('A', Path (fromList "AC") 1)+-- >                    , ('B', Path (fromList "BAC") 3)+-- >                    , ('C', Path (fromList "CAC") 1)+-- >                    , ('D', Path (fromList "DC") 2)+-- >                    , ('E', Path (fromList "EBAC") 3)+-- >                    ]
+ src/Graph/DijkstraSimple/Weighters.hs view
@@ -0,0 +1,34 @@+{-# 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.
+ test/Graph/DijkstraSimpleSpec.hs view
@@ -0,0 +1,56 @@+module Graph.DijkstraSimpleSpec+  ( main+  , spec+  )+where++import           Data.List.NonEmpty             ( fromList )+import qualified Data.Map.Lazy                 as M+import           Test.Hspec++import           Graph.DijkstraSimple+import           Graph.DijkstraSimple.Weighters++main :: IO ()+main = hspec spec++spec :: Spec+spec = describe "Graph.DijkstraSimple" $ do+  describe "lightestPaths" $ do+    it "classical cummulative weighter" $ do+      let paths = Paths $ M.fromList+            [ ('A', Path (fromList "AC") 1)+            , ('B', Path (fromList "BAC") 4)+            , ('C', Path (fromList "CAC") 2)+            , ('D', Path (fromList "DC") 2)+            , ('E', Path (fromList "EBAC") 5)+            ]+      lightestPaths exampleGraph 'C' cumulativeWeighter `shouldBe` paths+    it "maximal weighter" $ do+      let paths = Paths $ M.fromList+            [ ('A', Path (fromList "AC") 1)+            , ('B', Path (fromList "BAC") 3)+            , ('C', Path (fromList "CAC") 1)+            , ('D', Path (fromList "DC") 2)+            , ('E', Path (fromList "EBAC") 3)+            ]+      lightestPaths exampleGraph 'C' maximumWeightWeighter `shouldBe` paths+  describe "findPath" $ do+    it "unknown target"+      $          findPath exampleGraph 'C' cumulativeWeighter 'U'+      `shouldBe` Nothing+    it "classical cummulative weighter"+      $          findPath exampleGraph 'C' cumulativeWeighter 'E'+      `shouldBe` Just (Path (fromList "EBAC") 5)+    it "maximal weighter"+      $          findPath exampleGraph 'C' maximumWeightWeighter 'E'+      `shouldBe` Just (Path (fromList "EBAC") 3)++exampleGraph :: Graph Char Int+exampleGraph = Graph $ M.fromList+  [ ('A', [EdgeTo 'B' 3, EdgeTo 'C' 1])+  , ('B', [EdgeTo 'A' 3, EdgeTo 'C' 7, EdgeTo 'D' 5, EdgeTo 'E' 1])+  , ('C', [EdgeTo 'A' 1, EdgeTo 'B' 7, EdgeTo 'D' 2])+  , ('D', [EdgeTo 'B' 5, EdgeTo 'C' 2, EdgeTo 'E' 5])+  , ('E', [EdgeTo 'B' 1, EdgeTo 'D' 7])+  ]
+ test/Spec.hs view
@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF hspec-discover #-}