-- | Enquiry of the graph structure. Note: In this module the term "node" is often used synonymously to "node reference" and "node value". The two can easily distinguished by their type: the former has type 'Node' the latter usually 'n'.
module GraphRewriting.Graph.Read
(module GraphRewriting.Graph.Read, module GraphRewriting.Graph.Types, module Data.View)
where
import Prelude.Unicode
import GraphRewriting.Graph.Types
import GraphRewriting.Graph.Internal
import Control.Monad.Reader
import qualified Data.IntMap as Map
import qualified Data.IntSet as Set
import Data.View
import Data.List (nub)
type WithGraph n = Reader (Graph n)
-- | This forces the use of the 'Reader' monad. Wrapping a sequence of monadic read-only operations (such as those defined below) into a read-only block can save much overhead e.g. in the state monad.
readOnly ∷ WithGraph n a → Rewrite n a
readOnly r = liftM (runReader r) ask
readNode ∷ MonadReader (Graph n) m ⇒ Node → m n
readNode (Node n) = readRef n =<< asks nodeMap
-- | a wrapper to 'inspect' the given node
inspectNode ∷ (View v n, MonadReader (Graph n) m) ⇒ Node → m v
inspectNode = liftM inspect . readNode
-- | a wrapper to 'examine' the given node
examineNode ∷ (View v n, MonadReader (Graph n) m) ⇒ (v → a) → Node → m a
examineNode f = liftM (examine f) . readNode
-- | all of the graph's nodes
readNodeList ∷ MonadReader (Graph n) m ⇒ m [Node]
readNodeList = liftM (map Node . Map.keys) (asks nodeMap)
-- | all of the graph's edges
readEdgeList ∷ MonadReader (Graph n) m ⇒ m [Edge]
readEdgeList = liftM (map Edge . Map.keys) (asks edgeMap)
-- | edges attached to the given node
attachedEdges ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Edge]
attachedEdges = liftM nub . inspectNode
-- | non-empty set of nodes attached to the given edge
attachedNodes ∷ MonadReader (Graph n) m ⇒ Edge → m [Node]
attachedNodes = liftM (map Node . Set.elems) . readEdge
-- | amount of ports the given hyperedge is connected to
edgeCardinality ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Edge → m Int
edgeCardinality e = liftM (length . filter (e ≡) . concat) (mapM inspectNode =<< attachedNodes e)
-- | list of nodes that are connected to the given node, not including the node itself
neighbours ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Node]
neighbours n@(Node i) = do
is ← liftM Set.unions $ mapM readEdge =<< inspectNode n
return $ map Node $ Set.elems $ Set.delete i is
-- | list of nodes that are connected to the given node, including the node itself
relatives ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Node]
relatives n@(Node i) = do
is ← liftM Set.unions $ mapM readEdge =<< inspectNode n
return $ map Node $ Set.elems is
-- | nodes connected to given port of the specified node, not including the node itself
adverseNodes ∷ MonadReader (Graph n) m ⇒ Node → Port → m [Node]
adverseNodes (Node n) p = liftM (map Node . Set.elems . Set.delete n) (readEdge p)
-- | whether two nodes are connected
connected ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → Node → m Bool
connected n1 n2 = liftM (n2 ∈) (relatives n2)
-- | whether the given ports features a dangling edge
free ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Port → m Bool
free p = do
c ← edgeCardinality p
return (c ≡ 1)
-- | Map node-relative enquiry over the nodes of the graph.
withNodes ∷ MonadReader (Graph n) m ⇒ (Node → m a) → m [a]
withNodes p = mapM p =<< readNodeList