graphs 0.4.1 → 0.5

raw patch · 8 files changed

+46/−9 lines, 8 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.markdown +10/−0
• LICENSE +1/−1
• README.markdown +15/−0
• graphs.cabal +4/−4
• src/Data/Graph/AdjacencyList.hs +1/−0
• src/Data/Graph/AdjacencyMatrix.hs +1/−0
• src/Data/Graph/Algorithm/BreadthFirstSearch.hs +7/−2
• src/Data/Graph/Algorithm/DepthFirstSearch.hs +7/−2

@@ -0,0 +1,10 @@+0.5+---+* Added `enterEdge` to `bfs` and `dfs`.+* Exported `AdjacencyListGraph` and `AdjacencyMatrixGraph`.++0.4.1+-----+* Added CHANGELOG+* Removed my intra-package dependency upper bounds+

@@ -1,4 +1,4 @@-Copyright 2011 Edward Kmett+Copyright 2011-2013 Edward Kmett  All rights reserved. 

@@ -0,0 +1,15 @@+graphs+==========++[![Build Status](https://secure.travis-ci.org/ekmett/graphs.png?branch=master)](http://travis-ci.org/ekmett/graphs)++This provides a "not-very-Haskelly" API for calculating traversals of graphs that may be too large to fit into memory.++Contact Information+-------------------++Contributions and bug reports are welcome!++Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.++-Edward Kmett

@@ -1,6 +1,6 @@ name:          graphs-category:      Data Structures-version:       0.4.1+category:      Algorithms, Data Structures, Graphs+version:       0.5 license:       BSD3 cabal-version: >= 1.6 license-file:  LICENSE@@ -9,12 +9,12 @@ stability:     experimental homepage:      http://github.com/ekmett/graphs bug-reports:   http://github.com/ekmett/graphs/issues-copyright:     Copyright (C) 2011 Edward A. Kmett+copyright:     Copyright (C) 2011-2013 Edward A. Kmett synopsis:      A simple monadic graph library description:   A simple monadic graph library build-type:    Simple -extra-source-files: .travis.yml+extra-source-files: .travis.yml CHANGELOG.markdown README.markdown  source-repository head   type: git

@@ -13,6 +13,7 @@  module Data.Graph.AdjacencyList   ( AdjacencyList(..)+  , AdjacencyListGraph   , ask   ) where 

@@ -13,6 +13,7 @@  module Data.Graph.AdjacencyMatrix   ( AdjacencyMatrix(..)+  , AdjacencyMatrixGraph   , ask   ) where 

@@ -32,17 +32,19 @@ -- | Breadth first search visitor  data Bfs g m = Bfs    { enterVertex :: Vertex g -> g m -- called the first time a vertex is discovered+  , enterEdge   :: Edge g   -> g m -- called the first time an edge is discovered, before enter   , grayTarget  :: Edge g   -> g m -- called when we encounter a back edge to a vertex we're still processing   , exitVertex  :: Vertex g -> g m -- called once we have processed all descendants of a vertex   , blackTarget :: Edge g   -> g m -- called when we encounter a cross edge to a vertex we've already finished   }   instance Graph g => Functor (Bfs g) where-  fmap f (Bfs a b c d) = Bfs +  fmap f (Bfs a b c d e) = Bfs     (liftM f . a)     (liftM f . b)     (liftM f . c)     (liftM f . d)+    (liftM f . e)  instance Graph g => Applicative (Bfs g) where   pure a = Bfs @@ -50,9 +52,11 @@     (const (return a))     (const (return a))     (const (return a))+    (const (return a))    m <*> n = Bfs     (\v -> enterVertex m v `ap` enterVertex n v)+    (\e -> enterEdge m e `ap`   enterEdge n e)     (\e -> grayTarget m e `ap`  grayTarget n e)     (\v -> exitVertex m v `ap`  exitVertex n v)     (\e -> blackTarget m e `ap` blackTarget n e)@@ -61,6 +65,7 @@   return = pure   m >>= f = Bfs     (\v -> enterVertex m v >>= ($ v) . enterVertex . f)+    (\e -> enterEdge m e >>= ($ e) . enterEdge . f)     (\e -> grayTarget m e >>= ($ e) . grayTarget . f)     (\v -> exitVertex m v >>= ($ v) . exitVertex . f)     (\e -> blackTarget m e >>= ($ e) . blackTarget . f)@@ -109,7 +114,7 @@         v' <- target e         color <- getS v'         liftM (`mappend` m) $ case color of-          White -> enqueue vis v' +          White -> (liftM2 mappend) (lift $ enterEdge vis e) (enqueue vis v')           Grey -> lift $ grayTarget vis e           Black -> lift $ blackTarget vis e       ) mempty adjs

@@ -30,17 +30,19 @@  data Dfs g m = Dfs    { enterVertex :: Vertex g -> g m -- called the first time a vertex is discovered+  , enterEdge   :: Edge g   -> g m -- called the first time an edge is discovered, before enterVertex   , grayTarget  :: Edge g   -> g m -- called when we encounter a back edge to a vertex we're still processing   , exitVertex  :: Vertex g -> g m -- called once we have processed all descendants of a vertex   , blackTarget :: Edge g   -> g m -- called when we encounter a cross edge to a vertex we've already finished   }  instance Graph g => Functor (Dfs g) where-  fmap f (Dfs a b c d) = Dfs +  fmap f (Dfs a b c d e) = Dfs     (liftM f . a)     (liftM f . b)     (liftM f . c)     (liftM f . d)+    (liftM f . e)  instance Graph g => Applicative (Dfs g) where   pure a = Dfs @@ -48,9 +50,11 @@     (const (return a))     (const (return a))     (const (return a))+    (const (return a))    m <*> n = Dfs     (\v -> enterVertex m v `ap` enterVertex n v)+    (\e -> enterEdge m e `ap`   enterEdge n e)     (\e -> grayTarget m e `ap`  grayTarget n e)     (\v -> exitVertex m v `ap`  exitVertex n v)     (\e -> blackTarget m e `ap` blackTarget n e)@@ -59,6 +63,7 @@   return = pure   m >>= f = Dfs     (\v -> enterVertex m v >>= ($ v) . enterVertex . f)+    (\e -> enterEdge m e >>= ($ e) . enterEdge . f)     (\e -> grayTarget m e >>= ($ e) . grayTarget . f)     (\v -> exitVertex m v >>= ($ v) . exitVertex . f)     (\e -> blackTarget m e >>= ($ e) . blackTarget . f)@@ -92,7 +97,7 @@         v' <- target e         color <- getS v'         liftM (`mappend` m) $ case color of-          White -> go v'+          White -> (liftM2 mappend) (lift $ enterEdge vis e) (go v')           Grey  -> lift $ grayTarget vis e           Black -> lift $ blackTarget vis e       )