packages feed

graphs 0.1 → 0.2

raw patch · 9 files changed

+274/−88 lines, 9 files

Files

Data/Graph/AdjacencyMatrix.hs view
@@ -53,3 +53,5 @@     then Just ix     else Nothing     where ix = (i, j)++
Data/Graph/Class.hs view
@@ -13,6 +13,10 @@  module Data.Graph.Class    ( Graph(..)+  , VertexMap+  , EdgeMap+  , liftVertexMap+  , liftEdgeMap   ) where  import Control.Monad@@ -20,36 +24,104 @@ import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Error+import Control.Monad.Trans.Reader  import Control.Monad.Trans.Class+import Data.Functor.Identity import Data.Monoid import Data.Graph.PropertyMap+import Data.Void +type VertexMap g = PropertyMap g (Vertex g)+type EdgeMap g = PropertyMap g (Edge g)+ class (Monad g, Eq (Vertex g), Eq (Edge g)) => Graph g where   type Vertex g :: *   type Edge g :: * -  vertexMap :: a -> g (PropertyMap g (Vertex g) a)-  edgeMap   :: a -> g (PropertyMap g (Edge g) a)+  vertexMap :: a -> g (VertexMap g a)+  edgeMap   :: a -> g (EdgeMap g a) +liftVertexMap :: (MonadTrans t, Graph (t g), Graph g, Vertex (t g) ~ Vertex g) +              => a -> t g (VertexMap (t g) a)+liftVertexMap = lift . liftM liftPropertyMap . vertexMap+{-# INLINE liftVertexMap #-}++liftEdgeMap :: (MonadTrans t, Graph (t g), Graph g, Edge (t g) ~ Edge g) +            => a -> t g (EdgeMap (t g) a)+liftEdgeMap = lift . liftM liftPropertyMap . edgeMap+{-# INLINE liftEdgeMap #-}+ instance Graph g => Graph (Strict.StateT s g) where   type Vertex (Strict.StateT s g) = Vertex g   type Edge (Strict.StateT s g) = Edge g-  vertexMap = lift . liftM liftPropertyMap . vertexMap-  edgeMap = lift . liftM liftPropertyMap . edgeMap+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap  instance Graph g => Graph (Lazy.StateT s g) where   type Vertex (Lazy.StateT s g) = Vertex g   type Edge (Lazy.StateT s g) = Edge g-  vertexMap = lift . liftM liftPropertyMap . vertexMap-  edgeMap = lift . liftM liftPropertyMap . edgeMap+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap  instance (Graph g, Monoid m) => Graph (Strict.WriterT m g) where   type Vertex (Strict.WriterT m g) = Vertex g   type Edge (Strict.WriterT m g) = Edge g-  vertexMap = lift . liftM liftPropertyMap . vertexMap-  edgeMap = lift . liftM liftPropertyMap . edgeMap+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap  instance (Graph g, Monoid m) => Graph (Lazy.WriterT m g) where   type Vertex (Lazy.WriterT m g) = Vertex g   type Edge (Lazy.WriterT m g) = Edge g-  vertexMap = lift . liftM liftPropertyMap . vertexMap-  edgeMap = lift . liftM liftPropertyMap . edgeMap+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance Graph g => Graph (ReaderT m g) where+  type Vertex (ReaderT m g) = Vertex g +  type Edge (ReaderT m g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance Graph g => Graph (IdentityT g) where+  type Vertex (IdentityT g) = Vertex g+  type Edge (IdentityT g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance Graph g => Graph (MaybeT g) where+  type Vertex (MaybeT g) = Vertex g+  type Edge (MaybeT g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance (Graph g, Error e) => Graph (ErrorT e g) where+  type Vertex (ErrorT e g) = Vertex g+  type Edge (ErrorT e g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance (Graph g, Monoid w) => Graph (Lazy.RWST r w s g) where+  type Vertex (Lazy.RWST r w s g) = Vertex g+  type Edge (Lazy.RWST r w s g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++instance (Graph g, Monoid w) => Graph (Strict.RWST r w s g) where+  type Vertex (Strict.RWST r w s g) = Vertex g+  type Edge (Strict.RWST r w s g) = Edge g+  vertexMap = liftVertexMap+  edgeMap = liftEdgeMap++voidMap :: PropertyMap Identity Void a+voidMap = PropertyMap (Identity . void) $ \_ _ -> Identity voidMap++-- | The empty graph+instance Graph Identity where+  type Vertex Identity = Void+  type Edge Identity = Void+  vertexMap _ = Identity voidMap +  edgeMap   _ = Identity voidMap+
Data/Graph/Class/AdjacencyList.hs view
@@ -17,12 +17,19 @@   , module Data.Graph.Class   ) where +import Control.Monad+import Control.Monad.Trans.Class import qualified Control.Monad.Trans.State.Strict as Strict import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy-import Control.Monad-import Control.Monad.Trans.Class+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Error+import Control.Monad.Trans.Reader+import Data.Functor.Identity import Data.Monoid import Data.Graph.Class @@ -73,3 +80,50 @@   outEdges = lift . outEdges   outDegree = lift . outDegree +instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Strict.RWST r m s g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Lazy.RWST r m s g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance AdjacencyListGraph g => AdjacencyListGraph (ReaderT e g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance (AdjacencyListGraph g, Error e) => AdjacencyListGraph (ErrorT e g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance AdjacencyListGraph g => AdjacencyListGraph (MaybeT g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance AdjacencyListGraph g => AdjacencyListGraph (IdentityT g) where+  adjacentVertices = lift . adjacentVertices+  source = lift . source+  target = lift . target+  outEdges = lift . outEdges+  outDegree = lift . outDegree++instance AdjacencyListGraph Identity where+  source = Identity+  target = Identity+  outEdges _ = Identity []+  outDegree _ = Identity 0
Data/Graph/Class/AdjacencyMatrix.hs view
@@ -20,7 +20,14 @@ import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Reader+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Error import Control.Monad.Trans.Class+import Data.Functor.Identity import Data.Monoid import Data.Graph.Class @@ -39,3 +46,23 @@ instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (Lazy.WriterT m g) where   edge a b = lift (edge a b) +instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (Strict.RWST r m s g) where+  edge a b = lift (edge a b)++instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (Lazy.RWST r m s g) where+  edge a b = lift (edge a b)++instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (MaybeT g) where+  edge a b = lift (edge a b)++instance (AdjacencyMatrixGraph g, Error e) => AdjacencyMatrixGraph (ErrorT e g) where+  edge a b = lift (edge a b)++instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (IdentityT g) where+  edge a b = lift (edge a b)++instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (ReaderT e g) where+  edge a b = lift (edge a b)++instance AdjacencyMatrixGraph Identity where+  edge _ _ = Identity Nothing
Data/Graph/Class/Bidirectional.hs view
@@ -17,11 +17,18 @@   ) where  import Control.Monad+import Control.Monad.Trans.Class import qualified Control.Monad.Trans.State.Strict as Strict import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy-import Control.Monad.Trans.Class+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Reader+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Error+import Data.Functor.Identity import Data.Monoid import Data.Graph.Class.AdjacencyList @@ -61,3 +68,46 @@   inDegree = lift . inDegree   incidentEdges = lift . incidentEdges   degree = lift . degree++instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (Strict.RWST r m s g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (Lazy.RWST r m s g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance BidirectionalGraph g => BidirectionalGraph (ReaderT e g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance BidirectionalGraph g => BidirectionalGraph (IdentityT g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance BidirectionalGraph g => BidirectionalGraph (MaybeT g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance (BidirectionalGraph g, Error e) => BidirectionalGraph (ErrorT e g) where+  inEdges  = lift . inEdges+  inDegree = lift . inDegree+  incidentEdges = lift . incidentEdges+  degree = lift . degree++instance BidirectionalGraph Identity where+  inEdges _ = Identity []+  inDegree _ = Identity 0+  incidentEdges _ = Identity []+  degree _  = Identity 0+
Data/Graph/Class/EdgeEnumerable.hs view
@@ -20,7 +20,14 @@ import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Reader+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Error import Control.Monad.Trans.Class+import Data.Functor.Identity import Data.Monoid import Data.Graph.Class @@ -39,3 +46,24 @@  instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (Lazy.WriterT m g) where   edges = lift edges++instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (Strict.RWST r m s g) where+  edges = lift edges++instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (Lazy.RWST r m s g) where+  edges = lift edges++instance EdgeEnumerableGraph g => EdgeEnumerableGraph (MaybeT g) where+  edges = lift edges++instance EdgeEnumerableGraph g => EdgeEnumerableGraph (IdentityT g) where+  edges = lift edges++instance (EdgeEnumerableGraph g, Error e) => EdgeEnumerableGraph (ErrorT e g) where+  edges = lift edges++instance EdgeEnumerableGraph g => EdgeEnumerableGraph (ReaderT e g) where+  edges = lift edges++instance EdgeEnumerableGraph Identity where+  edges = Identity []
Data/Graph/Class/VertexEnumerable.hs view
@@ -20,9 +20,16 @@ import qualified Control.Monad.Trans.State.Lazy as Lazy import qualified Control.Monad.Trans.Writer.Strict as Strict import qualified Control.Monad.Trans.Writer.Lazy as Lazy+import qualified Control.Monad.Trans.RWS.Strict as Strict+import qualified Control.Monad.Trans.RWS.Lazy as Lazy+import Control.Monad.Trans.Identity+import Control.Monad.Trans.Maybe+import Control.Monad.Trans.Error import Control.Monad.Trans.Class+import Control.Monad.Trans.Reader import Data.Monoid import Data.Graph.Class+import Data.Functor.Identity  class Graph g => VertexEnumerableGraph g where   -- | /O(v)/@@ -40,3 +47,23 @@ instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (Lazy.WriterT m g) where   vertices = lift vertices +instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (Strict.RWST r m s g) where+  vertices = lift vertices+  +instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (Lazy.RWST r m s g) where+  vertices = lift vertices++instance VertexEnumerableGraph g => VertexEnumerableGraph (MaybeT g) where+  vertices = lift vertices++instance VertexEnumerableGraph g => VertexEnumerableGraph (IdentityT g) where+  vertices = lift vertices++instance (VertexEnumerableGraph g, Error e) => VertexEnumerableGraph (ErrorT e g) where+  vertices = lift vertices++instance VertexEnumerableGraph g => VertexEnumerableGraph (ReaderT m g) where+  vertices = lift vertices++instance VertexEnumerableGraph Identity where+  vertices = Identity []
− Data/Graph/Empty.hs 
@@ -1,73 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--------------------------------------------------------------------------------- |--- Module      :  Data.Graph.Empty--- Copyright   :  (C) 2011 Edward Kmett--- License     :  BSD-style (see the file LICENSE)------ Maintainer  :  Edward Kmett <ekmett@gmail.com>--- Stability   :  experimental--- Portability :  type families----------------------------------------------------------------------------------module Data.Graph.Empty-  ( Empty(..)-  ) where--import Control.Applicative-import Control.Monad-import Data.Void-import Data.Graph.PropertyMap-import Data.Graph.Class.AdjacencyList-import Data.Graph.Class.AdjacencyMatrix-import Data.Graph.Class.VertexEnumerable-import Data.Graph.Class.EdgeEnumerable-import Data.Graph.Class.Bidirectional--newtype Empty a = Empty { runEmpty :: a }--instance Functor Empty where-  fmap f (Empty g) = Empty $ f g-  b <$ _ = Empty b--instance Applicative Empty where-  pure = Empty -  Empty f <*> Empty a = Empty (f a)-  a <* _ = a-  _ *> b = b--instance Monad Empty where-  return = Empty-  Empty g >>= k = k g-  _ >> b = b--voidMap :: PropertyMap Empty Void a-voidMap = PropertyMap (Empty . void) $ \_ _ -> Empty voidMap--instance Graph Empty where-  type Vertex Empty = Void-  type Edge Empty = Void-  vertexMap _ = Empty voidMap -  edgeMap   _ = Empty voidMap--instance AdjacencyMatrixGraph Empty where-  edge _ _ = Empty Nothing--instance AdjacencyListGraph Empty where-  source = Empty-  target = Empty-  outEdges _ = Empty []-  outDegree _ = Empty 0--instance BidirectionalGraph Empty where-  inEdges _ = Empty []-  inDegree _ = Empty 0-  incidentEdges _ = Empty []-  degree _  = Empty 0--instance EdgeEnumerableGraph Empty where-  edges = return []--instance VertexEnumerableGraph Empty where-  vertices = return []
graphs.cabal view
@@ -1,6 +1,6 @@ name:          graphs category:      Data Structures-version:       0.1+version:       0.2 license:       BSD3 cabal-version: >= 1.6 license-file:  LICENSE@@ -38,7 +38,6 @@     Data.Graph.Class.Bidirectional     Data.Graph.Class.VertexEnumerable     Data.Graph.Dual-    Data.Graph.Empty     Data.Graph.PropertyMap   other-modules     Data.Graph.Internal.Color