-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A simple monadic graph library
--   
--   A simple monadic graph library
@package graphs
@version 0.5


-- | Total transient monadic maps, used to track information about vertices
--   and edges in a graph
module Data.Graph.PropertyMap
data PropertyMap m k v
PropertyMap :: (k -> m v) -> (k -> v -> m (PropertyMap m k v)) -> PropertyMap m k v
getP :: PropertyMap m k v -> k -> m v
putP :: PropertyMap m k v -> k -> v -> m (PropertyMap m k v)
modifyP :: Monad m => PropertyMap m k v -> k -> (v -> v) -> m (PropertyMap m k v)
intPropertyMap :: Monad m => v -> PropertyMap m Int v
propertyMap :: (Monad m, Ord k) => v -> PropertyMap m k v
liftPropertyMap :: (MonadTrans t, Monad m, Monad (t m)) => PropertyMap m k v -> PropertyMap (t m) k v


module Data.Graph.Class
class (Monad g, Eq (Vertex g), Eq (Edge g)) => Graph g where type family Vertex g :: * type family Edge g :: *
vertexMap :: Graph g => a -> g (VertexMap g a)
edgeMap :: Graph g => a -> g (EdgeMap g a)
type VertexMap g = PropertyMap g (Vertex g)
type EdgeMap g = PropertyMap g (Edge g)
liftVertexMap :: (MonadTrans t, Graph (t g), Graph g, Vertex (t g) ~ Vertex g) => a -> t g (VertexMap (t g) a)
liftEdgeMap :: (MonadTrans t, Graph (t g), Graph g, Edge (t g) ~ Edge g) => a -> t g (EdgeMap (t g) a)
instance Graph Identity
instance (Graph g, Monoid w) => Graph (RWST r w s g)
instance (Graph g, Monoid w) => Graph (RWST r w s g)
instance (Graph g, Error e) => Graph (ErrorT e g)
instance Graph g => Graph (MaybeT g)
instance Graph g => Graph (IdentityT g)
instance Graph g => Graph (ReaderT m g)
instance (Graph g, Monoid m) => Graph (WriterT m g)
instance (Graph g, Monoid m) => Graph (WriterT m g)
instance Graph g => Graph (StateT s g)
instance Graph g => Graph (StateT s g)


module Data.Graph.Class.AdjacencyList

-- | Minimal definition: <a>source</a>, <a>target</a>, and either
--   <a>adjacentVertices</a> with <tt><a>outEdges</a> =
--   <a>defaultOutEdges</a></tt> or <a>outEdges</a>
class Graph g => AdjacencyListGraph g where outDegree v = liftM length (outEdges v) adjacentVertices = outEdges >=> mapM target
source :: AdjacencyListGraph g => Edge g -> g (Vertex g)
target :: AdjacencyListGraph g => Edge g -> g (Vertex g)
outEdges :: AdjacencyListGraph g => Vertex g -> g [Edge g]
outDegree :: AdjacencyListGraph g => Vertex g -> g Int
adjacentVertices :: AdjacencyListGraph g => Vertex g -> g [Vertex g]
defaultOutEdges :: AdjacencyListGraph g => Vertex g -> g [(Vertex g, Vertex g)]
instance AdjacencyListGraph Identity
instance AdjacencyListGraph g => AdjacencyListGraph (IdentityT g)
instance AdjacencyListGraph g => AdjacencyListGraph (MaybeT g)
instance (AdjacencyListGraph g, Error e) => AdjacencyListGraph (ErrorT e g)
instance AdjacencyListGraph g => AdjacencyListGraph (ReaderT e g)
instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (RWST r m s g)
instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (RWST r m s g)
instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (WriterT m g)
instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (WriterT m g)
instance AdjacencyListGraph g => AdjacencyListGraph (StateT s g)
instance AdjacencyListGraph g => AdjacencyListGraph (StateT s g)


module Data.Graph.Class.Bidirectional
class AdjacencyListGraph g => BidirectionalGraph g where inDegree v = length `liftM` inEdges v incidentEdges v = liftM2 (++) (inEdges v) (outEdges v) degree v = liftM2 (+) (inDegree v) (outDegree v)
inEdges :: BidirectionalGraph g => Vertex g -> g [Edge g]
inDegree :: BidirectionalGraph g => Vertex g -> g Int
incidentEdges :: BidirectionalGraph g => Vertex g -> g [Edge g]
degree :: BidirectionalGraph g => Vertex g -> g Int
instance BidirectionalGraph Identity
instance (BidirectionalGraph g, Error e) => BidirectionalGraph (ErrorT e g)
instance BidirectionalGraph g => BidirectionalGraph (MaybeT g)
instance BidirectionalGraph g => BidirectionalGraph (IdentityT g)
instance BidirectionalGraph g => BidirectionalGraph (ReaderT e g)
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (RWST r m s g)
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (RWST r m s g)
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (WriterT m g)
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (WriterT m g)
instance BidirectionalGraph g => BidirectionalGraph (StateT s g)
instance BidirectionalGraph g => BidirectionalGraph (StateT s g)


module Data.Graph.Class.AdjacencyMatrix
class Graph g => AdjacencyMatrixGraph g
edge :: AdjacencyMatrixGraph g => Vertex g -> Vertex g -> g (Maybe (Edge g))
instance AdjacencyMatrixGraph Identity
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (ReaderT e g)
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (IdentityT g)
instance (AdjacencyMatrixGraph g, Error e) => AdjacencyMatrixGraph (ErrorT e g)
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (MaybeT g)
instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (RWST r m s g)
instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (RWST r m s g)
instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (WriterT m g)
instance (AdjacencyMatrixGraph g, Monoid m) => AdjacencyMatrixGraph (WriterT m g)
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (StateT s g)
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (StateT s g)


module Data.Graph.Class.EdgeEnumerable
class Graph g => EdgeEnumerableGraph g
edges :: EdgeEnumerableGraph g => g [Edge g]
instance EdgeEnumerableGraph Identity
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (ReaderT e g)
instance (EdgeEnumerableGraph g, Error e) => EdgeEnumerableGraph (ErrorT e g)
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (IdentityT g)
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (MaybeT g)
instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (RWST r m s g)
instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (RWST r m s g)
instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (WriterT m g)
instance (EdgeEnumerableGraph g, Monoid m) => EdgeEnumerableGraph (WriterT m g)
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (StateT s g)
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (StateT s g)


module Data.Graph.Class.VertexEnumerable
class Graph g => VertexEnumerableGraph g
vertices :: VertexEnumerableGraph g => g [Vertex g]
instance VertexEnumerableGraph Identity
instance VertexEnumerableGraph g => VertexEnumerableGraph (ReaderT m g)
instance (VertexEnumerableGraph g, Error e) => VertexEnumerableGraph (ErrorT e g)
instance VertexEnumerableGraph g => VertexEnumerableGraph (IdentityT g)
instance VertexEnumerableGraph g => VertexEnumerableGraph (MaybeT g)
instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (RWST r m s g)
instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (RWST r m s g)
instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (WriterT m g)
instance (VertexEnumerableGraph g, Monoid m) => VertexEnumerableGraph (WriterT m g)
instance VertexEnumerableGraph g => VertexEnumerableGraph (StateT s g)
instance VertexEnumerableGraph g => VertexEnumerableGraph (StateT s g)


module Data.Graph.AdjacencyMatrix
newtype AdjacencyMatrix arr i a
AdjacencyMatrix :: (arr (i, i) Bool -> a) -> AdjacencyMatrix arr i a
runAdjacencyMatrix :: AdjacencyMatrix arr i a -> arr (i, i) Bool -> a
class Graph g => AdjacencyMatrixGraph g
ask :: AdjacencyMatrix arr i (arr (i, i) Bool)
instance (IArray arr Bool, Ix i) => AdjacencyMatrixGraph (AdjacencyMatrix arr i)
instance Ord i => Graph (AdjacencyMatrix arr i)
instance Monad (AdjacencyMatrix arr i)
instance Applicative (AdjacencyMatrix arr i)
instance Functor (AdjacencyMatrix arr i)


-- | Depth-first search
module Data.Graph.Algorithm.DepthFirstSearch
dfs :: (AdjacencyListGraph g, Monoid m) => Dfs g m -> Vertex g -> g m
data Dfs g m
Dfs :: (Vertex g -> g m) -> (Edge g -> g m) -> (Edge g -> g m) -> (Vertex g -> g m) -> (Edge g -> g m) -> Dfs g m
enterVertex :: Dfs g m -> Vertex g -> g m
enterEdge :: Dfs g m -> Edge g -> g m
grayTarget :: Dfs g m -> Edge g -> g m
exitVertex :: Dfs g m -> Vertex g -> g m
blackTarget :: Dfs g m -> Edge g -> g m
instance (Graph g, Monoid m) => Monoid (Dfs g m)
instance Graph g => Monad (Dfs g)
instance Graph g => Applicative (Dfs g)
instance Graph g => Functor (Dfs g)


-- | Breadth-first search
module Data.Graph.Algorithm.BreadthFirstSearch
bfs :: (AdjacencyListGraph g, Monoid m) => Bfs g m -> Vertex g -> g m

-- | Breadth first search visitor
data Bfs g m
Bfs :: (Vertex g -> g m) -> (Edge g -> g m) -> (Edge g -> g m) -> (Vertex g -> g m) -> (Edge g -> g m) -> Bfs g m
enterVertex :: Bfs g m -> Vertex g -> g m
enterEdge :: Bfs g m -> Edge g -> g m
grayTarget :: Bfs g m -> Edge g -> g m
exitVertex :: Bfs g m -> Vertex g -> g m
blackTarget :: Bfs g m -> Edge g -> g m
instance (Graph g, Monoid m) => Monoid (Bfs g m)
instance Graph g => Monad (Bfs g)
instance Graph g => Applicative (Bfs g)
instance Graph g => Functor (Bfs g)


module Data.Graph.Dual
newtype Dual g a
Dual :: g a -> Dual g a
runDual :: Dual g a -> g a
instance VertexEnumerableGraph g => VertexEnumerableGraph (Dual g)
instance EdgeEnumerableGraph g => EdgeEnumerableGraph (Dual g)
instance BidirectionalGraph g => BidirectionalGraph (Dual g)
instance BidirectionalGraph g => AdjacencyListGraph (Dual g)
instance AdjacencyMatrixGraph g => AdjacencyMatrixGraph (Dual g)
instance Graph g => Graph (Dual g)
instance Monad g => Monad (Dual g)
instance Applicative g => Applicative (Dual g)
instance Functor g => Functor (Dual g)
instance MonadTrans Dual


module Data.Graph.AdjacencyList
newtype AdjacencyList i a
AdjacencyList :: (Array i [i] -> a) -> AdjacencyList i a
runAdjacencyList :: AdjacencyList i a -> Array i [i] -> a

-- | Minimal definition: <a>source</a>, <a>target</a>, and either
--   <a>adjacentVertices</a> with <tt><a>outEdges</a> =
--   <a>defaultOutEdges</a></tt> or <a>outEdges</a>
class Graph g => AdjacencyListGraph g where outDegree v = liftM length (outEdges v) adjacentVertices = outEdges >=> mapM target
ask :: AdjacencyList i (Array i [i])
instance Ix i => AdjacencyListGraph (AdjacencyList i)
instance Ord i => Graph (AdjacencyList i)
instance Monad (AdjacencyList i)
instance Applicative (AdjacencyList i)
instance Functor (AdjacencyList i)