module Data.Graph.Class.Bidirectional
( BidirectionalGraph(..)
, module Data.Graph.Class.AdjacencyList
) 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.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
class AdjacencyListGraph g => BidirectionalGraph g where
inEdges :: Vertex g -> g [Edge g]
inDegree :: Vertex g -> g Int
inDegree v = length `liftM` inEdges v
incidentEdges :: Vertex g -> g [Edge g]
incidentEdges v = liftM2 (++) (inEdges v) (outEdges v)
degree :: Vertex g -> g Int
degree v = liftM2 (+) (inDegree v) (outDegree v)
instance BidirectionalGraph g => BidirectionalGraph (Strict.StateT s g) where
inEdges = lift . inEdges
inDegree = lift . inDegree
incidentEdges = lift . incidentEdges
degree = lift . degree
instance BidirectionalGraph g => BidirectionalGraph (Lazy.StateT s g) where
inEdges = lift . inEdges
inDegree = lift . inDegree
incidentEdges = lift . incidentEdges
degree = lift . degree
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (Strict.WriterT m g) where
inEdges = lift . inEdges
inDegree = lift . inDegree
incidentEdges = lift . incidentEdges
degree = lift . degree
instance (BidirectionalGraph g, Monoid m) => BidirectionalGraph (Lazy.WriterT m g) where
inEdges = lift . inEdges
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