{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE DeriveGeneric #-}
#endif

-- (c) 1999 - 2002 by Martin Erwig [see file COPYRIGHT]
-- | Tree-based implementation of 'Graph' and 'DynGraph'
--
--   You will probably have better performance using the
--   "Data.Graph.Inductive.PatriciaTree" implementation instead.

module Data.Graph.Inductive.Tree (Gr,UGr) where

import Data.Graph.Inductive.Graph

import           Control.Applicative (liftA2)
import           Data.List           (foldl', sort)
import           Data.Map            (Map)
import qualified Data.Map            as M
import           Data.Maybe          (fromMaybe)

#if MIN_VERSION_containers (0,4,2)
import Control.DeepSeq (NFData (..))
#endif

#if __GLASGOW_HASKELL__ >= 702
import GHC.Generics (Generic)
#endif

#if MIN_VERSION_base (4,8,0)
import Data.Bifunctor
#else
import Control.Arrow (first, second)
#endif

----------------------------------------------------------------------
-- GRAPH REPRESENTATION
----------------------------------------------------------------------

newtype Gr a b = Gr (GraphRep a b)
#if __GLASGOW_HASKELL__ >= 702
  deriving ((forall x. Gr a b -> Rep (Gr a b) x)
-> (forall x. Rep (Gr a b) x -> Gr a b) -> Generic (Gr a b)
forall x. Rep (Gr a b) x -> Gr a b
forall x. Gr a b -> Rep (Gr a b) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a b x. Rep (Gr a b) x -> Gr a b
forall a b x. Gr a b -> Rep (Gr a b) x
$cto :: forall a b x. Rep (Gr a b) x -> Gr a b
$cfrom :: forall a b x. Gr a b -> Rep (Gr a b) x
Generic)
#endif

type GraphRep a b = Map Node (Context' a b)
type Context' a b = (Adj b,a,Adj b)

type UGr = Gr () ()

----------------------------------------------------------------------
-- CLASS INSTANCES
----------------------------------------------------------------------

instance (Eq a, Ord b) => Eq (Gr a b) where
  (Gr GraphRep a b
g1) == :: Gr a b -> Gr a b -> Bool
== (Gr GraphRep a b
g2) = (([(b, Node)], a, [(b, Node)]) -> ([(b, Node)], a, [(b, Node)]))
-> GraphRep a b -> GraphRep a b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([(b, Node)], a, [(b, Node)]) -> ([(b, Node)], a, [(b, Node)])
forall a a b. (Ord a, Ord a) => ([a], b, [a]) -> ([a], b, [a])
sortAdj GraphRep a b
g1 GraphRep a b -> GraphRep a b -> Bool
forall a. Eq a => a -> a -> Bool
== (([(b, Node)], a, [(b, Node)]) -> ([(b, Node)], a, [(b, Node)]))
-> GraphRep a b -> GraphRep a b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([(b, Node)], a, [(b, Node)]) -> ([(b, Node)], a, [(b, Node)])
forall a a b. (Ord a, Ord a) => ([a], b, [a]) -> ([a], b, [a])
sortAdj GraphRep a b
g2
    where
      sortAdj :: ([a], b, [a]) -> ([a], b, [a])
sortAdj ([a]
p,b
n,[a]
s) = ([a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
p,b
n,[a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
s)

instance (Show a, Show b) => Show (Gr a b) where
  showsPrec :: Node -> Gr a b -> ShowS
showsPrec Node
d Gr a b
g = Bool -> ShowS -> ShowS
showParen (Node
d Node -> Node -> Bool
forall a. Ord a => a -> a -> Bool
> Node
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
                    String -> ShowS
showString String
"mkGraph "
                    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [LNode a] -> ShowS
forall a. Show a => a -> ShowS
shows (Gr a b -> [LNode a]
forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LNode a]
labNodes Gr a b
g)
                    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" "
                    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [LEdge b] -> ShowS
forall a. Show a => a -> ShowS
shows (Gr a b -> [LEdge b]
forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LEdge b]
labEdges Gr a b
g)

instance (Read a, Read b) => Read (Gr a b) where
  readsPrec :: Node -> ReadS (Gr a b)
readsPrec Node
p = Bool -> ReadS (Gr a b) -> ReadS (Gr a b)
forall a. Bool -> ReadS a -> ReadS a
readParen (Node
p Node -> Node -> Bool
forall a. Ord a => a -> a -> Bool
> Node
10) (ReadS (Gr a b) -> ReadS (Gr a b))
-> ReadS (Gr a b) -> ReadS (Gr a b)
forall a b. (a -> b) -> a -> b
$ \ String
r -> do
    (String
"mkGraph", String
s) <- ReadS String
lex String
r
    ([LNode a]
ns,String
t) <- ReadS [LNode a]
forall a. Read a => ReadS a
reads String
s
    ([LEdge b]
es,String
u) <- ReadS [LEdge b]
forall a. Read a => ReadS a
reads String
t
    (Gr a b, String) -> [(Gr a b, String)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([LNode a] -> [LEdge b] -> Gr a b
forall (gr :: * -> * -> *) a b.
Graph gr =>
[LNode a] -> [LEdge b] -> gr a b
mkGraph [LNode a]
ns [LEdge b]
es, String
u)

-- Graph
--
instance Graph Gr where
  empty :: Gr a b
empty             = GraphRep a b -> Gr a b
forall a b. GraphRep a b -> Gr a b
Gr GraphRep a b
forall k a. Map k a
M.empty

  isEmpty :: Gr a b -> Bool
isEmpty (Gr GraphRep a b
g)    = GraphRep a b -> Bool
forall k a. Map k a -> Bool
M.null GraphRep a b
g

  match :: Node -> Gr a b -> Decomp Gr a b
match Node
v gr :: Gr a b
gr@(Gr GraphRep a b
g) = Decomp Gr a b
-> ((Context' a b, GraphRep a b) -> Decomp Gr a b)
-> Maybe (Context' a b, GraphRep a b)
-> Decomp Gr a b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Maybe (Context a b)
forall a. Maybe a
Nothing, Gr a b
gr)
                            ((Context a b -> Maybe (Context a b))
-> (Context a b, Gr a b) -> Decomp Gr a b
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Context a b -> Maybe (Context a b)
forall a. a -> Maybe a
Just ((Context a b, Gr a b) -> Decomp Gr a b)
-> ((Context' a b, GraphRep a b) -> (Context a b, Gr a b))
-> (Context' a b, GraphRep a b)
-> Decomp Gr a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Context' a b -> GraphRep a b -> (Context a b, Gr a b))
-> (Context' a b, GraphRep a b) -> (Context a b, Gr a b)
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Node -> Context' a b -> GraphRep a b -> (Context a b, Gr a b)
forall a b.
Node -> Context' a b -> GraphRep a b -> (Context a b, Gr a b)
cleanSplit Node
v))
                      (Maybe (Context' a b, GraphRep a b) -> Decomp Gr a b)
-> ((Maybe (Context' a b), GraphRep a b)
    -> Maybe (Context' a b, GraphRep a b))
-> (Maybe (Context' a b), GraphRep a b)
-> Decomp Gr a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (\(Maybe (Context' a b)
m,GraphRep a b
g') -> (Context' a b -> (Context' a b, GraphRep a b))
-> Maybe (Context' a b) -> Maybe (Context' a b, GraphRep a b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Context' a b -> GraphRep a b -> (Context' a b, GraphRep a b))
-> GraphRep a b -> Context' a b -> (Context' a b, GraphRep a b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) GraphRep a b
g') Maybe (Context' a b)
m)
                      ((Maybe (Context' a b), GraphRep a b) -> Decomp Gr a b)
-> (Maybe (Context' a b), GraphRep a b) -> Decomp Gr a b
forall a b. (a -> b) -> a -> b
$ (Node -> Context' a b -> Maybe (Context' a b))
-> Node -> GraphRep a b -> (Maybe (Context' a b), GraphRep a b)
forall k a.
Ord k =>
(k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
M.updateLookupWithKey ((Context' a b -> Maybe (Context' a b))
-> Node -> Context' a b -> Maybe (Context' a b)
forall a b. a -> b -> a
const (Maybe (Context' a b) -> Context' a b -> Maybe (Context' a b)
forall a b. a -> b -> a
const Maybe (Context' a b)
forall a. Maybe a
Nothing)) Node
v GraphRep a b
g

  mkGraph :: [LNode a] -> [LEdge b] -> Gr a b
mkGraph [LNode a]
vs [LEdge b]
es     = [LEdge b] -> Gr a b -> Gr a b
forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
insEdges [LEdge b]
es
                      (Gr a b -> Gr a b) -> ([LNode a] -> Gr a b) -> [LNode a] -> Gr a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GraphRep a b -> Gr a b
forall a b. GraphRep a b -> Gr a b
Gr
                      (GraphRep a b -> Gr a b)
-> ([LNode a] -> GraphRep a b) -> [LNode a] -> Gr a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Node, ([(b, Node)], a, [(b, Node)]))] -> GraphRep a b
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList
                      ([(Node, ([(b, Node)], a, [(b, Node)]))] -> GraphRep a b)
-> ([LNode a] -> [(Node, ([(b, Node)], a, [(b, Node)]))])
-> [LNode a]
-> GraphRep a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (LNode a -> (Node, ([(b, Node)], a, [(b, Node)])))
-> [LNode a] -> [(Node, ([(b, Node)], a, [(b, Node)]))]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> ([(b, Node)], a, [(b, Node)]))
-> LNode a -> (Node, ([(b, Node)], a, [(b, Node)]))
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (\a
l -> ([],a
l,[])))
                      ([LNode a] -> Gr a b) -> [LNode a] -> Gr a b
forall a b. (a -> b) -> a -> b
$ [LNode a]
vs

  labNodes :: Gr a b -> [LNode a]
labNodes (Gr GraphRep a b
g)   = ((Node, (Adj b, a, Adj b)) -> LNode a)
-> [(Node, (Adj b, a, Adj b))] -> [LNode a]
forall a b. (a -> b) -> [a] -> [b]
map (\(Node
v,(Adj b
_,a
l,Adj b
_))->(Node
v,a
l)) (GraphRep a b -> [(Node, (Adj b, a, Adj b))]
forall k a. Map k a -> [(k, a)]
M.toList GraphRep a b
g)

  matchAny :: Gr a b -> GDecomp Gr a b
matchAny (Gr GraphRep a b
g)   = GDecomp Gr a b
-> (((Node, Context' a b), GraphRep a b) -> GDecomp Gr a b)
-> Maybe ((Node, Context' a b), GraphRep a b)
-> GDecomp Gr a b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (String -> GDecomp Gr a b
forall a. HasCallStack => String -> a
error String
"Match Exception, Empty Graph")
                            (((Node, Context' a b) -> GraphRep a b -> GDecomp Gr a b)
-> ((Node, Context' a b), GraphRep a b) -> GDecomp Gr a b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((Node -> Context' a b -> GraphRep a b -> GDecomp Gr a b)
-> (Node, Context' a b) -> GraphRep a b -> GDecomp Gr a b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Node -> Context' a b -> GraphRep a b -> GDecomp Gr a b
forall a b.
Node -> Context' a b -> GraphRep a b -> (Context a b, Gr a b)
cleanSplit))
                            (GraphRep a b -> Maybe ((Node, Context' a b), GraphRep a b)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.minViewWithKey GraphRep a b
g)

  noNodes :: Gr a b -> Node
noNodes   (Gr GraphRep a b
g)  = GraphRep a b -> Node
forall k a. Map k a -> Node
M.size GraphRep a b
g

  nodeRange :: Gr a b -> (Node, Node)
nodeRange (Gr GraphRep a b
g)  = (Node, Node) -> Maybe (Node, Node) -> (Node, Node)
forall a. a -> Maybe a -> a
fromMaybe (String -> (Node, Node)
forall a. HasCallStack => String -> a
error String
"nodeRange of empty graph")
                      (Maybe (Node, Node) -> (Node, Node))
-> Maybe (Node, Node) -> (Node, Node)
forall a b. (a -> b) -> a -> b
$ (Node -> Node -> (Node, Node))
-> Maybe Node -> Maybe Node -> Maybe (Node, Node)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (,) (Maybe ((Node, Context' a b), GraphRep a b) -> Maybe Node
forall b b b. Maybe ((b, b), b) -> Maybe b
ix (GraphRep a b -> Maybe ((Node, Context' a b), GraphRep a b)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.minViewWithKey GraphRep a b
g))
                                   (Maybe ((Node, Context' a b), GraphRep a b) -> Maybe Node
forall b b b. Maybe ((b, b), b) -> Maybe b
ix (GraphRep a b -> Maybe ((Node, Context' a b), GraphRep a b)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.maxViewWithKey GraphRep a b
g))
    where
      ix :: Maybe ((b, b), b) -> Maybe b
ix            = (((b, b), b) -> b) -> Maybe ((b, b), b) -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((b, b) -> b
forall a b. (a, b) -> a
fst ((b, b) -> b) -> (((b, b), b) -> (b, b)) -> ((b, b), b) -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b, b), b) -> (b, b)
forall a b. (a, b) -> a
fst)

  labEdges :: Gr a b -> [LEdge b]
labEdges  (Gr GraphRep a b
g)  = ((Node, (Adj b, a, Adj b)) -> [LEdge b])
-> [(Node, (Adj b, a, Adj b))] -> [LEdge b]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\(Node
v,(Adj b
_,a
_,Adj b
s))->((b, Node) -> LEdge b) -> Adj b -> [LEdge b]
forall a b. (a -> b) -> [a] -> [b]
map (\(b
l,Node
w)->(Node
v,Node
w,b
l)) Adj b
s) (GraphRep a b -> [(Node, (Adj b, a, Adj b))]
forall k a. Map k a -> [(k, a)]
M.toList GraphRep a b
g)

-- After a Node (with its corresponding Context') are split out of a
-- GraphRep, clean up the remainders.
cleanSplit :: Node -> Context' a b -> GraphRep a b
              -> (Context a b, Gr a b)
cleanSplit :: Node -> Context' a b -> GraphRep a b -> (Context a b, Gr a b)
cleanSplit Node
v (Adj b
p,a
l,Adj b
s) GraphRep a b
g = (Context a b
c, GraphRep a b -> Gr a b
forall a b. GraphRep a b -> Gr a b
Gr GraphRep a b
g')
  where
    -- Note: loops are kept only in successor list
    c :: Context a b
c = (Adj b
p', Node
v, a
l, Adj b
s)
    p' :: Adj b
p' = Adj b -> Adj b
forall a. [(a, Node)] -> [(a, Node)]
rmLoops Adj b
p
    s' :: Adj b
s' = Adj b -> Adj b
forall a. [(a, Node)] -> [(a, Node)]
rmLoops Adj b
s
    rmLoops :: [(a, Node)] -> [(a, Node)]
rmLoops = ((a, Node) -> Bool) -> [(a, Node)] -> [(a, Node)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Node -> Node -> Bool
forall a. Eq a => a -> a -> Bool
/=Node
v) (Node -> Bool) -> ((a, Node) -> Node) -> (a, Node) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Node) -> Node
forall a b. (a, b) -> b
snd)

    g' :: GraphRep a b
g' = Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
forall b a.
Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
updAdj Adj b
s' (Node -> b -> Context' a b -> Context' a b
forall b a. Node -> b -> Context' a b -> Context' a b
clearPred Node
v) (GraphRep a b -> GraphRep a b)
-> (GraphRep a b -> GraphRep a b) -> GraphRep a b -> GraphRep a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
forall b a.
Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
updAdj Adj b
p' (Node -> b -> Context' a b -> Context' a b
forall b a. Node -> b -> Context' a b -> Context' a b
clearSucc Node
v) (GraphRep a b -> GraphRep a b) -> GraphRep a b -> GraphRep a b
forall a b. (a -> b) -> a -> b
$ GraphRep a b
g

-- DynGraph
--
instance DynGraph Gr where
  (Adj b
p,Node
v,a
l,Adj b
s) & :: Context a b -> Gr a b -> Gr a b
& (Gr GraphRep a b
g) = GraphRep a b -> Gr a b
forall a b. GraphRep a b -> Gr a b
Gr
                       (GraphRep a b -> Gr a b)
-> (GraphRep a b -> GraphRep a b) -> GraphRep a b -> Gr a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
forall b a.
Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
updAdj Adj b
p (Node -> b -> Context' a b -> Context' a b
forall b a. Node -> b -> Context' a b -> Context' a b
addSucc Node
v)
                       (GraphRep a b -> GraphRep a b)
-> (GraphRep a b -> GraphRep a b) -> GraphRep a b -> GraphRep a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
forall b a.
Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
updAdj Adj b
s (Node -> b -> Context' a b -> Context' a b
forall b a. Node -> b -> Context' a b -> Context' a b
addPred Node
v)
                       (GraphRep a b -> Gr a b) -> GraphRep a b -> Gr a b
forall a b. (a -> b) -> a -> b
$ (Maybe (Context' a b) -> Maybe (Context' a b))
-> Node -> GraphRep a b -> GraphRep a b
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
M.alter Maybe (Context' a b) -> Maybe (Context' a b)
forall b. Maybe b -> Maybe (Context' a b)
addCntxt Node
v GraphRep a b
g
    where
      addCntxt :: Maybe b -> Maybe (Context' a b)
addCntxt = Maybe (Context' a b)
-> (b -> Maybe (Context' a b)) -> Maybe b -> Maybe (Context' a b)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Context' a b -> Maybe (Context' a b)
forall a. a -> Maybe a
Just Context' a b
cntxt')
                       (Maybe (Context' a b) -> b -> Maybe (Context' a b)
forall a b. a -> b -> a
const (String -> Maybe (Context' a b)
forall a. HasCallStack => String -> a
error (String
"Node Exception, Node: "String -> ShowS
forall a. [a] -> [a] -> [a]
++Node -> String
forall a. Show a => a -> String
show Node
v)))
      cntxt' :: Context' a b
cntxt' = (Adj b
p,a
l,Adj b
s)

#if MIN_VERSION_containers (0,4,2)
instance (NFData a, NFData b) => NFData (Gr a b) where
  rnf :: Gr a b -> ()
rnf (Gr GraphRep a b
g) = GraphRep a b -> ()
forall a. NFData a => a -> ()
rnf GraphRep a b
g
#endif

#if MIN_VERSION_base (4,8,0)
instance Bifunctor Gr where
  bimap :: (a -> b) -> (c -> d) -> Gr a c -> Gr b d
bimap = (a -> b) -> (c -> d) -> Gr a c -> Gr b d
forall (gr :: * -> * -> *) a c b d.
DynGraph gr =>
(a -> c) -> (b -> d) -> gr a b -> gr c d
nemap

  first :: (a -> b) -> Gr a c -> Gr b c
first = (a -> b) -> Gr a c -> Gr b c
forall (gr :: * -> * -> *) a c b.
DynGraph gr =>
(a -> c) -> gr a b -> gr c b
nmap

  second :: (b -> c) -> Gr a b -> Gr a c
second = (b -> c) -> Gr a b -> Gr a c
forall (gr :: * -> * -> *) b c a.
DynGraph gr =>
(b -> c) -> gr a b -> gr a c
emap
#endif

----------------------------------------------------------------------
-- UTILITIES
----------------------------------------------------------------------

addSucc :: Node -> b -> Context' a b -> Context' a b
addSucc :: Node -> b -> Context' a b -> Context' a b
addSucc Node
v b
l (Adj b
p,a
l',Adj b
s) = (Adj b
p,a
l',(b
l,Node
v)(b, Node) -> Adj b -> Adj b
forall a. a -> [a] -> [a]
:Adj b
s)

addPred :: Node -> b -> Context' a b -> Context' a b
addPred :: Node -> b -> Context' a b -> Context' a b
addPred Node
v b
l (Adj b
p,a
l',Adj b
s) = ((b
l,Node
v)(b, Node) -> Adj b -> Adj b
forall a. a -> [a] -> [a]
:Adj b
p,a
l',Adj b
s)

clearSucc :: Node -> b -> Context' a b -> Context' a b
clearSucc :: Node -> b -> Context' a b -> Context' a b
clearSucc Node
v b
_ (Adj b
p,a
l,Adj b
s) = (Adj b
p,a
l,((b, Node) -> Bool) -> Adj b -> Adj b
forall a. (a -> Bool) -> [a] -> [a]
filter ((Node -> Node -> Bool
forall a. Eq a => a -> a -> Bool
/=Node
v)(Node -> Bool) -> ((b, Node) -> Node) -> (b, Node) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(b, Node) -> Node
forall a b. (a, b) -> b
snd) Adj b
s)

clearPred :: Node -> b -> Context' a b -> Context' a b
clearPred :: Node -> b -> Context' a b -> Context' a b
clearPred Node
v b
_ (Adj b
p,a
l,Adj b
s) = (((b, Node) -> Bool) -> Adj b -> Adj b
forall a. (a -> Bool) -> [a] -> [a]
filter ((Node -> Node -> Bool
forall a. Eq a => a -> a -> Bool
/=Node
v)(Node -> Bool) -> ((b, Node) -> Node) -> (b, Node) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(b, Node) -> Node
forall a b. (a, b) -> b
snd) Adj b
p,a
l,Adj b
s)

updAdj :: Adj b -> (b -> Context' a b -> Context' a b) -> GraphRep a b -> GraphRep a b
updAdj :: Adj b
-> (b -> Context' a b -> Context' a b)
-> GraphRep a b
-> GraphRep a b
updAdj Adj b
adj b -> Context' a b -> Context' a b
f GraphRep a b
g = (GraphRep a b -> (b, Node) -> GraphRep a b)
-> GraphRep a b -> Adj b -> GraphRep a b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\GraphRep a b
g' (b
l,Node
v) -> (Context' a b -> Context' a b)
-> Node -> GraphRep a b -> GraphRep a b
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
M.adjust (b -> Context' a b -> Context' a b
f b
l) Node
v GraphRep a b
g') GraphRep a b
g Adj b
adj