{-# LANGUAGE CPP, TypeFamilies, FlexibleInstances #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Graph.Class.AdjacencyList
-- 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.Class.AdjacencyList
  ( AdjacencyListGraph(..)
  , defaultOutEdges
  , 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 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
#if !(MIN_VERSION_transformers(0,6,0))
import Control.Monad.Trans.Error
#endif
import Control.Monad.Trans.Reader
import Data.Functor.Identity
#if __GLASGOW_HASKELL__ < 710
import Data.Monoid
#endif
import Data.Graph.Class

defaultOutEdges :: AdjacencyListGraph g => Vertex g -> g [(Vertex g, Vertex g)]
defaultOutEdges :: Vertex g -> g [(Vertex g, Vertex g)]
defaultOutEdges Vertex g
v = ([Vertex g] -> [(Vertex g, Vertex g)])
-> g [Vertex g] -> g [(Vertex g, Vertex g)]
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM ((Vertex g -> (Vertex g, Vertex g))
-> [Vertex g] -> [(Vertex g, Vertex g)]
forall a b. (a -> b) -> [a] -> [b]
map ((,) Vertex g
v)) (Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices Vertex g
v)

-- | Minimal definition: 'source', 'target', and either 'adjacentVertices' with @'outEdges' = 'defaultOutEdges'@ or 'outEdges'
class Graph g => AdjacencyListGraph g where
  -- /O(1)/
  source :: Edge g -> g (Vertex g)
  -- /O(1)/
  target :: Edge g -> g (Vertex g)
  -- /O(e)/ in the number of out edges
  outEdges :: Vertex g -> g [Edge g]

  -- /O(e)/
  outDegree :: Vertex g -> g Int
  outDegree Vertex g
v = ([Edge g] -> Int) -> g [Edge g] -> g Int
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM [Edge g] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges Vertex g
v)

  adjacentVertices :: Vertex g -> g [Vertex g]
  adjacentVertices = Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges (Vertex g -> g [Edge g])
-> ([Edge g] -> g [Vertex g]) -> Vertex g -> g [Vertex g]
forall (m :: * -> *) a b c.
Monad m =>
(a -> m b) -> (b -> m c) -> a -> m c
>=> (Edge g -> g (Vertex g)) -> [Edge g] -> g [Vertex g]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target

instance AdjacencyListGraph g => AdjacencyListGraph (Strict.StateT s g) where
  adjacentVertices :: Vertex (StateT s g) -> StateT s g [Vertex (StateT s g)]
adjacentVertices = g [Vertex g] -> StateT s g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> StateT s g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> StateT s g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (StateT s g) -> StateT s g (Vertex (StateT s g))
source = g (Vertex g) -> StateT s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> StateT s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> StateT s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (StateT s g) -> StateT s g (Vertex (StateT s g))
target = g (Vertex g) -> StateT s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> StateT s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> StateT s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (StateT s g) -> StateT s g [Edge (StateT s g)]
outEdges = g [Edge g] -> StateT s g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> StateT s g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> StateT s g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (StateT s g) -> StateT s g Int
outDegree = g Int -> StateT s g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> StateT s g Int)
-> (Vertex g -> g Int) -> Vertex g -> StateT s g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance AdjacencyListGraph g => AdjacencyListGraph (Lazy.StateT s g) where
  adjacentVertices :: Vertex (StateT s g) -> StateT s g [Vertex (StateT s g)]
adjacentVertices = g [Vertex g] -> StateT s g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> StateT s g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> StateT s g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (StateT s g) -> StateT s g (Vertex (StateT s g))
source = g (Vertex g) -> StateT s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> StateT s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> StateT s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (StateT s g) -> StateT s g (Vertex (StateT s g))
target = g (Vertex g) -> StateT s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> StateT s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> StateT s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (StateT s g) -> StateT s g [Edge (StateT s g)]
outEdges = g [Edge g] -> StateT s g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> StateT s g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> StateT s g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (StateT s g) -> StateT s g Int
outDegree = g Int -> StateT s g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> StateT s g Int)
-> (Vertex g -> g Int) -> Vertex g -> StateT s g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Strict.WriterT m g) where
  adjacentVertices :: Vertex (WriterT m g) -> WriterT m g [Vertex (WriterT m g)]
adjacentVertices = g [Vertex g] -> WriterT m g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> WriterT m g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> WriterT m g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (WriterT m g) -> WriterT m g (Vertex (WriterT m g))
source = g (Vertex g) -> WriterT m g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> WriterT m g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> WriterT m g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (WriterT m g) -> WriterT m g (Vertex (WriterT m g))
target = g (Vertex g) -> WriterT m g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> WriterT m g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> WriterT m g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (WriterT m g) -> WriterT m g [Edge (WriterT m g)]
outEdges = g [Edge g] -> WriterT m g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> WriterT m g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> WriterT m g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (WriterT m g) -> WriterT m g Int
outDegree = g Int -> WriterT m g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> WriterT m g Int)
-> (Vertex g -> g Int) -> Vertex g -> WriterT m g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Lazy.WriterT m g) where
  adjacentVertices :: Vertex (WriterT m g) -> WriterT m g [Vertex (WriterT m g)]
adjacentVertices = g [Vertex g] -> WriterT m g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> WriterT m g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> WriterT m g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (WriterT m g) -> WriterT m g (Vertex (WriterT m g))
source = g (Vertex g) -> WriterT m g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> WriterT m g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> WriterT m g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (WriterT m g) -> WriterT m g (Vertex (WriterT m g))
target = g (Vertex g) -> WriterT m g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> WriterT m g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> WriterT m g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (WriterT m g) -> WriterT m g [Edge (WriterT m g)]
outEdges = g [Edge g] -> WriterT m g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> WriterT m g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> WriterT m g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (WriterT m g) -> WriterT m g Int
outDegree = g Int -> WriterT m g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> WriterT m g Int)
-> (Vertex g -> g Int) -> Vertex g -> WriterT m g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Strict.RWST r m s g) where
  adjacentVertices :: Vertex (RWST r m s g) -> RWST r m s g [Vertex (RWST r m s g)]
adjacentVertices = g [Vertex g] -> RWST r m s g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> RWST r m s g [Vertex g])
-> (Vertex g -> g [Vertex g])
-> Vertex g
-> RWST r m s g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (RWST r m s g) -> RWST r m s g (Vertex (RWST r m s g))
source = g (Vertex g) -> RWST r m s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> RWST r m s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> RWST r m s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (RWST r m s g) -> RWST r m s g (Vertex (RWST r m s g))
target = g (Vertex g) -> RWST r m s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> RWST r m s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> RWST r m s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (RWST r m s g) -> RWST r m s g [Edge (RWST r m s g)]
outEdges = g [Edge g] -> RWST r m s g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> RWST r m s g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> RWST r m s g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (RWST r m s g) -> RWST r m s g Int
outDegree = g Int -> RWST r m s g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> RWST r m s g Int)
-> (Vertex g -> g Int) -> Vertex g -> RWST r m s g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance (AdjacencyListGraph g, Monoid m) => AdjacencyListGraph (Lazy.RWST r m s g) where
  adjacentVertices :: Vertex (RWST r m s g) -> RWST r m s g [Vertex (RWST r m s g)]
adjacentVertices = g [Vertex g] -> RWST r m s g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> RWST r m s g [Vertex g])
-> (Vertex g -> g [Vertex g])
-> Vertex g
-> RWST r m s g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (RWST r m s g) -> RWST r m s g (Vertex (RWST r m s g))
source = g (Vertex g) -> RWST r m s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> RWST r m s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> RWST r m s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (RWST r m s g) -> RWST r m s g (Vertex (RWST r m s g))
target = g (Vertex g) -> RWST r m s g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> RWST r m s g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> RWST r m s g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (RWST r m s g) -> RWST r m s g [Edge (RWST r m s g)]
outEdges = g [Edge g] -> RWST r m s g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> RWST r m s g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> RWST r m s g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (RWST r m s g) -> RWST r m s g Int
outDegree = g Int -> RWST r m s g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> RWST r m s g Int)
-> (Vertex g -> g Int) -> Vertex g -> RWST r m s g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance AdjacencyListGraph g => AdjacencyListGraph (ReaderT e g) where
  adjacentVertices :: Vertex (ReaderT e g) -> ReaderT e g [Vertex (ReaderT e g)]
adjacentVertices = g [Vertex g] -> ReaderT e g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> ReaderT e g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> ReaderT e g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (ReaderT e g) -> ReaderT e g (Vertex (ReaderT e g))
source = g (Vertex g) -> ReaderT e g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> ReaderT e g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> ReaderT e g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (ReaderT e g) -> ReaderT e g (Vertex (ReaderT e g))
target = g (Vertex g) -> ReaderT e g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> ReaderT e g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> ReaderT e g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (ReaderT e g) -> ReaderT e g [Edge (ReaderT e g)]
outEdges = g [Edge g] -> ReaderT e g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> ReaderT e g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> ReaderT e g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (ReaderT e g) -> ReaderT e g Int
outDegree = g Int -> ReaderT e g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> ReaderT e g Int)
-> (Vertex g -> g Int) -> Vertex g -> ReaderT e g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

#if !(MIN_VERSION_transformers(0,6,0))
instance (AdjacencyListGraph g, Error e) => AdjacencyListGraph (ErrorT e g) where
  adjacentVertices :: Vertex (ErrorT e g) -> ErrorT e g [Vertex (ErrorT e g)]
adjacentVertices = g [Vertex g] -> ErrorT e g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> ErrorT e g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> ErrorT e g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (ErrorT e g) -> ErrorT e g (Vertex (ErrorT e g))
source = g (Vertex g) -> ErrorT e g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> ErrorT e g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> ErrorT e g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (ErrorT e g) -> ErrorT e g (Vertex (ErrorT e g))
target = g (Vertex g) -> ErrorT e g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> ErrorT e g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> ErrorT e g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (ErrorT e g) -> ErrorT e g [Edge (ErrorT e g)]
outEdges = g [Edge g] -> ErrorT e g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> ErrorT e g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> ErrorT e g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (ErrorT e g) -> ErrorT e g Int
outDegree = g Int -> ErrorT e g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> ErrorT e g Int)
-> (Vertex g -> g Int) -> Vertex g -> ErrorT e g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree
#endif

instance AdjacencyListGraph g => AdjacencyListGraph (MaybeT g) where
  adjacentVertices :: Vertex (MaybeT g) -> MaybeT g [Vertex (MaybeT g)]
adjacentVertices = g [Vertex g] -> MaybeT g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> MaybeT g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> MaybeT g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (MaybeT g) -> MaybeT g (Vertex (MaybeT g))
source = g (Vertex g) -> MaybeT g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> MaybeT g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> MaybeT g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (MaybeT g) -> MaybeT g (Vertex (MaybeT g))
target = g (Vertex g) -> MaybeT g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> MaybeT g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> MaybeT g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (MaybeT g) -> MaybeT g [Edge (MaybeT g)]
outEdges = g [Edge g] -> MaybeT g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> MaybeT g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> MaybeT g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (MaybeT g) -> MaybeT g Int
outDegree = g Int -> MaybeT g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> MaybeT g Int)
-> (Vertex g -> g Int) -> Vertex g -> MaybeT g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance AdjacencyListGraph g => AdjacencyListGraph (IdentityT g) where
  adjacentVertices :: Vertex (IdentityT g) -> IdentityT g [Vertex (IdentityT g)]
adjacentVertices = g [Vertex g] -> IdentityT g [Vertex g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Vertex g] -> IdentityT g [Vertex g])
-> (Vertex g -> g [Vertex g]) -> Vertex g -> IdentityT g [Vertex g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Vertex g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Vertex g]
adjacentVertices
  source :: Edge (IdentityT g) -> IdentityT g (Vertex (IdentityT g))
source = g (Vertex g) -> IdentityT g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> IdentityT g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> IdentityT g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
source
  target :: Edge (IdentityT g) -> IdentityT g (Vertex (IdentityT g))
target = g (Vertex g) -> IdentityT g (Vertex g)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g (Vertex g) -> IdentityT g (Vertex g))
-> (Edge g -> g (Vertex g)) -> Edge g -> IdentityT g (Vertex g)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge g -> g (Vertex g)
forall (g :: * -> *).
AdjacencyListGraph g =>
Edge g -> g (Vertex g)
target
  outEdges :: Vertex (IdentityT g) -> IdentityT g [Edge (IdentityT g)]
outEdges = g [Edge g] -> IdentityT g [Edge g]
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g [Edge g] -> IdentityT g [Edge g])
-> (Vertex g -> g [Edge g]) -> Vertex g -> IdentityT g [Edge g]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g [Edge g]
forall (g :: * -> *).
AdjacencyListGraph g =>
Vertex g -> g [Edge g]
outEdges
  outDegree :: Vertex (IdentityT g) -> IdentityT g Int
outDegree = g Int -> IdentityT g Int
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (g Int -> IdentityT g Int)
-> (Vertex g -> g Int) -> Vertex g -> IdentityT g Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex g -> g Int
forall (g :: * -> *). AdjacencyListGraph g => Vertex g -> g Int
outDegree

instance AdjacencyListGraph Identity where
  source :: Edge Identity -> Identity (Vertex Identity)
source = Edge Identity -> Identity (Vertex Identity)
forall a. a -> Identity a
Identity
  target :: Edge Identity -> Identity (Vertex Identity)
target = Edge Identity -> Identity (Vertex Identity)
forall a. a -> Identity a
Identity
  outEdges :: Vertex Identity -> Identity [Edge Identity]
outEdges Vertex Identity
_ = [Void] -> Identity [Void]
forall a. a -> Identity a
Identity []
  outDegree :: Vertex Identity -> Identity Int
outDegree Vertex Identity
_ = Int -> Identity Int
forall a. a -> Identity a
Identity Int
0