module Data.Graph.Comfort (
   -- * Types
   Graph,
   LabeledNode,
   LabeledEdge,
   Edge(from, to), defaultEdgeFoldMap,
   DirEdge(DirEdge),
   UndirEdge(UndirEdge), undirEdge,
   EitherEdge(EDirEdge,EUndirEdge),

   -- * Construction
   empty, fromList, fromMap,

   -- * Extract large portions of the graph
   graphMap,
   nodeLabels, nodeSet, nodes, nodeEdges,
   edgeLabels, edgeSet, edges,

   -- * Queries
   isEmpty,
   lookupNode, lookupEdge,
   predecessors, successors,
   adjacentEdgeSet, adjacentEdges,
   isLoop,
   pathExists,
   isConsistent,

   -- * Manipulate labels
   mapNode, mapNodeWithKey,
   mapEdge, mapEdgeWithKey,
   mapNodeWithInOut, InOut,
   filterEdgeWithKey,
   traverseNode, traverseEdge, traverse,

   -- * Combine graphs
   checkedZipWith,
   union,

   -- * Manipulate indices
   Reverse,
   reverse,
   reverseEdge,
   mapKeys,
   mapMaybeEdgeKeys,
   mapEdgeKeys,

   -- * Insertion and removal
   deleteNode, deleteNodeSet, deleteEdge,
   insertNode, insertEdge, insertEdgeSet,
   ) where

import qualified Data.Graph.Comfort.Map as MapU
import qualified Data.Graph.Comfort.TotalMap as TMap

import Control.Monad.Trans.Identity (IdentityT(IdentityT, runIdentityT))
import Data.Functor.Classes
         (Eq1(liftEq), Ord1(liftCompare), Show1(liftShowsPrec))

import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Traversable as Trav
import qualified Data.Foldable as Fold
import Control.Monad (liftM2, (=<<))
import Control.Applicative (Applicative, liftA2, liftA3)
import Data.Foldable (Foldable, foldMap)
import Data.Set (Set)
import Data.Map (Map)
import Data.Monoid
         (Monoid, mempty, mappend, All(All), getAll, Endo(Endo), appEndo)
import Data.Semigroup (Semigroup((<>)), )
import Data.Tuple.HT (mapFst, fst3, snd3, thd3, mapFst3, mapThd3)

import qualified Test.QuickCheck as QC

import Data.Functor (Functor, fmap)
import Data.List (map, any, all, (++))
import Data.String (String)
import Data.Maybe (Maybe)
import Data.Bool (Bool(False), not, (&&), (||))
import Data.Eq (Eq, (==))
import Data.Ord (Ord, Ordering(LT,GT), (<), (>))
import Data.Tuple (uncurry)
import Data.Function (flip, (.), ($))
import Data.Int (Int)
import Text.Show
         (Show, ShowS, showParen, showString, showChar, shows, showsPrec)

import Prelude (error)


{- $setup
>>> import Test.Base
>>>
>>> import qualified Data.Graph.Comfort as Graph
>>> import qualified Data.Map as Map
>>> import qualified Data.Set as Set
>>> import qualified Data.Char as Char
>>>
>>> import qualified Control.Monad.Trans.Class as MT
>>> import qualified Control.Monad.Trans.State as MS
>>> import Control.Applicative (pure)
>>> import Data.Functor.Identity (Identity(Identity), runIdentity)
>>>
>>> import qualified Test.QuickCheck as QC
>>> import Test.QuickCheck ((==>))
>>>
>>> deleteNodeIfExists :: Node -> MonoGraph -> MonoGraph
>>> deleteNodeIfExists n gr =
>>>    maybe gr (const $ Graph.deleteNode n gr) $ Graph.lookupNode n gr
>>>
>>> isolated :: (Graph.Edge e, Ord n) => Graph.Graph e n el nl -> n -> Bool
>>> isolated gr n = Set.null (Graph.adjacentEdgeSet gr n)
>>>
>>> nodeAction :: (Monad m) => NodeLabel -> MS.StateT NodeLabel m NodeLabel
>>> nodeAction x = do y <- MS.get; MS.put x; return y
>>>
>>> evalTraverseNode :: NodeLabel -> MonoGraph -> MonoGraph
>>> evalTraverseNode nl =
>>>    flip MS.evalState nl . Graph.traverseNode nodeAction
>>>
>>> edgeAction :: (Monad m) => EdgeLabel -> MS.StateT EdgeLabel m EdgeLabel
>>> edgeAction x = MS.modify (x+) >> MS.get
>>>
>>> evalTraverseEdge :: EdgeLabel -> MonoGraph -> MonoGraph
>>> evalTraverseEdge el =
>>>    flip MS.evalState el . Graph.traverseEdge edgeAction
>>>
>>> evalTraverse :: NodeLabel -> EdgeLabel -> MonoGraph -> MonoGraph
>>> evalTraverse nl el =
>>>    flip MS.evalState el . flip MS.evalStateT nl .
>>>    Graph.traverse nodeAction (MT.lift . edgeAction)
-}

{-
For all 'Graph's the 'isConsistent' predicate must be 'True'.
-}
newtype Graph edge node edgeLabel nodeLabel =
   Graph {
      Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap ::
         Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
   } deriving (Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
(Graph edge node edgeLabel nodeLabel
 -> Graph edge node edgeLabel nodeLabel -> Bool)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Bool)
-> Eq (Graph edge node edgeLabel nodeLabel)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Eq1 edge, Eq node, Eq edgeLabel, Eq nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
/= :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c/= :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Eq1 edge, Eq node, Eq edgeLabel, Eq nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
== :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c== :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Eq1 edge, Eq node, Eq edgeLabel, Eq nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
Eq, Eq (Graph edge node edgeLabel nodeLabel)
Eq (Graph edge node edgeLabel nodeLabel)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Ordering)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Bool)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Bool)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Bool)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel -> Bool)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel)
-> (Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel
    -> Graph edge node edgeLabel nodeLabel)
-> Ord (Graph edge node edgeLabel nodeLabel)
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Ordering
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Eq (Graph edge node edgeLabel nodeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Ordering
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
min :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
$cmin :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
max :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
$cmax :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
>= :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c>= :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
> :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c> :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
<= :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c<= :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
< :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
$c< :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Bool
compare :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Ordering
$ccompare :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel -> Ordering
$cp1Ord :: forall (edge :: * -> *) node edgeLabel nodeLabel.
(Ord1 edge, Ord node, Ord edgeLabel, Ord nodeLabel) =>
Eq (Graph edge node edgeLabel nodeLabel)
Ord)

instance
   (Edge e, Ord n, Show1 e, Show n, Show el, Show nl) =>
      Show (Graph e n el nl) where
   showsPrec :: Int -> Graph e n el nl -> ShowS
showsPrec Int
prec Graph e n el nl
g =
      Bool -> ShowS -> ShowS
showParen (Int
precInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
         String -> ShowS
showString String
"Graph.fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         [(n, nl)] -> ShowS
forall a. Show a => a -> ShowS
shows (Map n nl -> [(n, nl)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map n nl -> [(n, nl)]) -> Map n nl -> [(n, nl)]
forall a b. (a -> b) -> a -> b
$ Graph e n el nl -> Map n nl
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Graph e n el nl -> Map n nl
nodeLabels Graph e n el nl
g) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         Char -> ShowS
showChar Char
' ' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         [(Wrap e n, el)] -> ShowS
forall a. Show a => a -> ShowS
shows (Map (Wrap e n) el -> [(Wrap e n, el)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map (Wrap e n) el -> [(Wrap e n, el)])
-> Map (Wrap e n) el -> [(Wrap e n, el)]
forall a b. (a -> b) -> a -> b
$ Graph e n el nl -> Map (Wrap e n) el
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel
-> Map (Wrap edge node) edgeLabel
edgeLabelsWrap Graph e n el nl
g)


isConsistent :: (Ord n, Eq el) => Graph DirEdge n el nl -> Bool
isConsistent :: Graph DirEdge n el nl -> Bool
isConsistent (Graph Map n (InOutMap (Wrap DirEdge) n el nl)
ns) =
   (InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el)
-> Map n (InOutMap (Wrap DirEdge) n el nl)
-> Map (Wrap DirEdge n) el
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el
forall a b c. (a, b, c) -> a
fst3 Map n (InOutMap (Wrap DirEdge) n el nl)
ns Map (Wrap DirEdge n) el -> Map (Wrap DirEdge n) el -> Bool
forall a. Eq a => a -> a -> Bool
== (InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el)
-> Map n (InOutMap (Wrap DirEdge) n el nl)
-> Map (Wrap DirEdge n) el
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el
forall a b c. (a, b, c) -> c
thd3 Map n (InOutMap (Wrap DirEdge) n el nl)
ns
   Bool -> Bool -> Bool
&&
   Set n -> Set n -> Bool
forall a. Ord a => Set a -> Set a -> Bool
Set.isSubsetOf
      ((InOutMap (Wrap DirEdge) n el nl -> Set n)
-> Map n (InOutMap (Wrap DirEdge) n el nl) -> Set n
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((Wrap DirEdge n -> Set n) -> [Wrap DirEdge n] -> Set n
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((n -> Set n) -> Wrap DirEdge n -> Set n
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap n -> Set n
forall a. a -> Set a
Set.singleton) ([Wrap DirEdge n] -> Set n)
-> (InOutMap (Wrap DirEdge) n el nl -> [Wrap DirEdge n])
-> InOutMap (Wrap DirEdge) n el nl
-> Set n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Wrap DirEdge n) el -> [Wrap DirEdge n]
forall k a. Map k a -> [k]
Map.keys (Map (Wrap DirEdge n) el -> [Wrap DirEdge n])
-> (InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el)
-> InOutMap (Wrap DirEdge) n el nl
-> [Wrap DirEdge n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InOutMap (Wrap DirEdge) n el nl -> Map (Wrap DirEdge n) el
forall a b c. (a, b, c) -> a
fst3) Map n (InOutMap (Wrap DirEdge) n el nl)
ns)
      (Map n (InOutMap (Wrap DirEdge) n el nl) -> Set n
forall k a. Map k a -> Set k
Map.keysSet Map n (InOutMap (Wrap DirEdge) n el nl)
ns)
   Bool -> Bool -> Bool
&&
   (Map n Bool -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
Fold.and (Map n Bool -> Bool) -> Map n Bool -> Bool
forall a b. (a -> b) -> a -> b
$ ((n -> InOutMap (Wrap DirEdge) n el nl -> Bool)
 -> Map n (InOutMap (Wrap DirEdge) n el nl) -> Map n Bool)
-> Map n (InOutMap (Wrap DirEdge) n el nl)
-> (n -> InOutMap (Wrap DirEdge) n el nl -> Bool)
-> Map n Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip (n -> InOutMap (Wrap DirEdge) n el nl -> Bool)
-> Map n (InOutMap (Wrap DirEdge) n el nl) -> Map n Bool
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey Map n (InOutMap (Wrap DirEdge) n el nl)
ns ((n -> InOutMap (Wrap DirEdge) n el nl -> Bool) -> Map n Bool)
-> (n -> InOutMap (Wrap DirEdge) n el nl -> Bool) -> Map n Bool
forall a b. (a -> b) -> a -> b
$
      \n
n (Map (Wrap DirEdge n) el
ins,nl
_nl,Map (Wrap DirEdge n) el
outs) ->
         (Wrap DirEdge n -> Bool) -> [Wrap DirEdge n] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((n
nn -> n -> Bool
forall a. Eq a => a -> a -> Bool
==) (n -> Bool) -> (Wrap DirEdge n -> n) -> Wrap DirEdge n -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap DirEdge n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
toWrap) (Map (Wrap DirEdge n) el -> [Wrap DirEdge n]
forall k a. Map k a -> [k]
Map.keys Map (Wrap DirEdge n) el
ins) Bool -> Bool -> Bool
&&
         (Wrap DirEdge n -> Bool) -> [Wrap DirEdge n] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((n
nn -> n -> Bool
forall a. Eq a => a -> a -> Bool
==) (n -> Bool) -> (Wrap DirEdge n -> n) -> Wrap DirEdge n -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap DirEdge n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
fromWrap) (Map (Wrap DirEdge n) el -> [Wrap DirEdge n]
forall k a. Map k a -> [k]
Map.keys Map (Wrap DirEdge n) el
outs))


type LabeledNode n label = (n, label)


defaultEdgeFoldMap :: (Edge edge, Monoid a) => edge a -> a
defaultEdgeFoldMap :: edge a -> a
defaultEdgeFoldMap edge a
e = a -> a -> a
forall a. Monoid a => a -> a -> a
mappend (edge a -> a
forall (edge :: * -> *) node. Edge edge => edge node -> node
from edge a
e) (edge a -> a
forall (edge :: * -> *) node. Edge edge => edge node -> node
to edge a
e)

class (Foldable edge, Ord1 edge) => Edge edge where
   from, to :: edge node -> node

instance Edge DirEdge where
   from :: DirEdge node -> node
from (DirEdge node
x node
_) = node
x
   to :: DirEdge node -> node
to (DirEdge node
_ node
x) = node
x

instance Edge UndirEdge where
   from :: UndirEdge node -> node
from (UndirEdge node
x node
_) = node
x
   to :: UndirEdge node -> node
to (UndirEdge node
_ node
x) = node
x

instance Edge EitherEdge where
   from :: EitherEdge node -> node
from EitherEdge node
ee =
      case EitherEdge node
ee of
         EDirEdge   DirEdge node
e -> DirEdge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
from DirEdge node
e
         EUndirEdge UndirEdge node
e -> UndirEdge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
from UndirEdge node
e
   to :: EitherEdge node -> node
to EitherEdge node
ee =
      case EitherEdge node
ee of
         EDirEdge   DirEdge node
e -> DirEdge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
to DirEdge node
e
         EUndirEdge UndirEdge node
e -> UndirEdge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
to UndirEdge node
e


{-
class (Edge edge) => ConsEdge edge where
   {- |
   The construction of an edge may fail
   and it is not warranted
   that @x == from (edge x y)@ or @y == to (edge x y)@.
   -}
   edge :: Ord node => node -> node -> Maybe (edge node)

instance ConsEdge DirEdge where
   edge x y = Just $ DirEdge x y

instance ConsEdge UndirEdge where
   edge x y = Just $ undirEdge x y
-}



type LabeledEdge edge node label = (edge node, label)


data DirEdge node = DirEdge node node
   deriving (DirEdge node -> DirEdge node -> Bool
(DirEdge node -> DirEdge node -> Bool)
-> (DirEdge node -> DirEdge node -> Bool) -> Eq (DirEdge node)
forall node. Eq node => DirEdge node -> DirEdge node -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: DirEdge node -> DirEdge node -> Bool
$c/= :: forall node. Eq node => DirEdge node -> DirEdge node -> Bool
== :: DirEdge node -> DirEdge node -> Bool
$c== :: forall node. Eq node => DirEdge node -> DirEdge node -> Bool
Eq, Eq (DirEdge node)
Eq (DirEdge node)
-> (DirEdge node -> DirEdge node -> Ordering)
-> (DirEdge node -> DirEdge node -> Bool)
-> (DirEdge node -> DirEdge node -> Bool)
-> (DirEdge node -> DirEdge node -> Bool)
-> (DirEdge node -> DirEdge node -> Bool)
-> (DirEdge node -> DirEdge node -> DirEdge node)
-> (DirEdge node -> DirEdge node -> DirEdge node)
-> Ord (DirEdge node)
DirEdge node -> DirEdge node -> Bool
DirEdge node -> DirEdge node -> Ordering
DirEdge node -> DirEdge node -> DirEdge node
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall node. Ord node => Eq (DirEdge node)
forall node. Ord node => DirEdge node -> DirEdge node -> Bool
forall node. Ord node => DirEdge node -> DirEdge node -> Ordering
forall node.
Ord node =>
DirEdge node -> DirEdge node -> DirEdge node
min :: DirEdge node -> DirEdge node -> DirEdge node
$cmin :: forall node.
Ord node =>
DirEdge node -> DirEdge node -> DirEdge node
max :: DirEdge node -> DirEdge node -> DirEdge node
$cmax :: forall node.
Ord node =>
DirEdge node -> DirEdge node -> DirEdge node
>= :: DirEdge node -> DirEdge node -> Bool
$c>= :: forall node. Ord node => DirEdge node -> DirEdge node -> Bool
> :: DirEdge node -> DirEdge node -> Bool
$c> :: forall node. Ord node => DirEdge node -> DirEdge node -> Bool
<= :: DirEdge node -> DirEdge node -> Bool
$c<= :: forall node. Ord node => DirEdge node -> DirEdge node -> Bool
< :: DirEdge node -> DirEdge node -> Bool
$c< :: forall node. Ord node => DirEdge node -> DirEdge node -> Bool
compare :: DirEdge node -> DirEdge node -> Ordering
$ccompare :: forall node. Ord node => DirEdge node -> DirEdge node -> Ordering
$cp1Ord :: forall node. Ord node => Eq (DirEdge node)
Ord, Int -> DirEdge node -> ShowS
[DirEdge node] -> ShowS
DirEdge node -> String
(Int -> DirEdge node -> ShowS)
-> (DirEdge node -> String)
-> ([DirEdge node] -> ShowS)
-> Show (DirEdge node)
forall node. Show node => Int -> DirEdge node -> ShowS
forall node. Show node => [DirEdge node] -> ShowS
forall node. Show node => DirEdge node -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DirEdge node] -> ShowS
$cshowList :: forall node. Show node => [DirEdge node] -> ShowS
show :: DirEdge node -> String
$cshow :: forall node. Show node => DirEdge node -> String
showsPrec :: Int -> DirEdge node -> ShowS
$cshowsPrec :: forall node. Show node => Int -> DirEdge node -> ShowS
Show)

data UndirEdge node = UndirEdge node node
   deriving (UndirEdge node -> UndirEdge node -> Bool
(UndirEdge node -> UndirEdge node -> Bool)
-> (UndirEdge node -> UndirEdge node -> Bool)
-> Eq (UndirEdge node)
forall node. Eq node => UndirEdge node -> UndirEdge node -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: UndirEdge node -> UndirEdge node -> Bool
$c/= :: forall node. Eq node => UndirEdge node -> UndirEdge node -> Bool
== :: UndirEdge node -> UndirEdge node -> Bool
$c== :: forall node. Eq node => UndirEdge node -> UndirEdge node -> Bool
Eq, Eq (UndirEdge node)
Eq (UndirEdge node)
-> (UndirEdge node -> UndirEdge node -> Ordering)
-> (UndirEdge node -> UndirEdge node -> Bool)
-> (UndirEdge node -> UndirEdge node -> Bool)
-> (UndirEdge node -> UndirEdge node -> Bool)
-> (UndirEdge node -> UndirEdge node -> Bool)
-> (UndirEdge node -> UndirEdge node -> UndirEdge node)
-> (UndirEdge node -> UndirEdge node -> UndirEdge node)
-> Ord (UndirEdge node)
UndirEdge node -> UndirEdge node -> Bool
UndirEdge node -> UndirEdge node -> Ordering
UndirEdge node -> UndirEdge node -> UndirEdge node
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall node. Ord node => Eq (UndirEdge node)
forall node. Ord node => UndirEdge node -> UndirEdge node -> Bool
forall node.
Ord node =>
UndirEdge node -> UndirEdge node -> Ordering
forall node.
Ord node =>
UndirEdge node -> UndirEdge node -> UndirEdge node
min :: UndirEdge node -> UndirEdge node -> UndirEdge node
$cmin :: forall node.
Ord node =>
UndirEdge node -> UndirEdge node -> UndirEdge node
max :: UndirEdge node -> UndirEdge node -> UndirEdge node
$cmax :: forall node.
Ord node =>
UndirEdge node -> UndirEdge node -> UndirEdge node
>= :: UndirEdge node -> UndirEdge node -> Bool
$c>= :: forall node. Ord node => UndirEdge node -> UndirEdge node -> Bool
> :: UndirEdge node -> UndirEdge node -> Bool
$c> :: forall node. Ord node => UndirEdge node -> UndirEdge node -> Bool
<= :: UndirEdge node -> UndirEdge node -> Bool
$c<= :: forall node. Ord node => UndirEdge node -> UndirEdge node -> Bool
< :: UndirEdge node -> UndirEdge node -> Bool
$c< :: forall node. Ord node => UndirEdge node -> UndirEdge node -> Bool
compare :: UndirEdge node -> UndirEdge node -> Ordering
$ccompare :: forall node.
Ord node =>
UndirEdge node -> UndirEdge node -> Ordering
$cp1Ord :: forall node. Ord node => Eq (UndirEdge node)
Ord, Int -> UndirEdge node -> ShowS
[UndirEdge node] -> ShowS
UndirEdge node -> String
(Int -> UndirEdge node -> ShowS)
-> (UndirEdge node -> String)
-> ([UndirEdge node] -> ShowS)
-> Show (UndirEdge node)
forall node. Show node => Int -> UndirEdge node -> ShowS
forall node. Show node => [UndirEdge node] -> ShowS
forall node. Show node => UndirEdge node -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [UndirEdge node] -> ShowS
$cshowList :: forall node. Show node => [UndirEdge node] -> ShowS
show :: UndirEdge node -> String
$cshow :: forall node. Show node => UndirEdge node -> String
showsPrec :: Int -> UndirEdge node -> ShowS
$cshowsPrec :: forall node. Show node => Int -> UndirEdge node -> ShowS
Show)

undirEdge :: (Ord node) => node -> node -> UndirEdge node
undirEdge :: node -> node -> UndirEdge node
undirEdge node
x node
y =
   if node
xnode -> node -> Bool
forall a. Ord a => a -> a -> Bool
<node
y
     then node -> node -> UndirEdge node
forall node. node -> node -> UndirEdge node
UndirEdge node
x node
y
     else node -> node -> UndirEdge node
forall node. node -> node -> UndirEdge node
UndirEdge node
y node
x

data
   EitherEdge node =
        EDirEdge (DirEdge node)
      | EUndirEdge (UndirEdge node)
   deriving (EitherEdge node -> EitherEdge node -> Bool
(EitherEdge node -> EitherEdge node -> Bool)
-> (EitherEdge node -> EitherEdge node -> Bool)
-> Eq (EitherEdge node)
forall node. Eq node => EitherEdge node -> EitherEdge node -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: EitherEdge node -> EitherEdge node -> Bool
$c/= :: forall node. Eq node => EitherEdge node -> EitherEdge node -> Bool
== :: EitherEdge node -> EitherEdge node -> Bool
$c== :: forall node. Eq node => EitherEdge node -> EitherEdge node -> Bool
Eq, Eq (EitherEdge node)
Eq (EitherEdge node)
-> (EitherEdge node -> EitherEdge node -> Ordering)
-> (EitherEdge node -> EitherEdge node -> Bool)
-> (EitherEdge node -> EitherEdge node -> Bool)
-> (EitherEdge node -> EitherEdge node -> Bool)
-> (EitherEdge node -> EitherEdge node -> Bool)
-> (EitherEdge node -> EitherEdge node -> EitherEdge node)
-> (EitherEdge node -> EitherEdge node -> EitherEdge node)
-> Ord (EitherEdge node)
EitherEdge node -> EitherEdge node -> Bool
EitherEdge node -> EitherEdge node -> Ordering
EitherEdge node -> EitherEdge node -> EitherEdge node
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall node. Ord node => Eq (EitherEdge node)
forall node. Ord node => EitherEdge node -> EitherEdge node -> Bool
forall node.
Ord node =>
EitherEdge node -> EitherEdge node -> Ordering
forall node.
Ord node =>
EitherEdge node -> EitherEdge node -> EitherEdge node
min :: EitherEdge node -> EitherEdge node -> EitherEdge node
$cmin :: forall node.
Ord node =>
EitherEdge node -> EitherEdge node -> EitherEdge node
max :: EitherEdge node -> EitherEdge node -> EitherEdge node
$cmax :: forall node.
Ord node =>
EitherEdge node -> EitherEdge node -> EitherEdge node
>= :: EitherEdge node -> EitherEdge node -> Bool
$c>= :: forall node. Ord node => EitherEdge node -> EitherEdge node -> Bool
> :: EitherEdge node -> EitherEdge node -> Bool
$c> :: forall node. Ord node => EitherEdge node -> EitherEdge node -> Bool
<= :: EitherEdge node -> EitherEdge node -> Bool
$c<= :: forall node. Ord node => EitherEdge node -> EitherEdge node -> Bool
< :: EitherEdge node -> EitherEdge node -> Bool
$c< :: forall node. Ord node => EitherEdge node -> EitherEdge node -> Bool
compare :: EitherEdge node -> EitherEdge node -> Ordering
$ccompare :: forall node.
Ord node =>
EitherEdge node -> EitherEdge node -> Ordering
$cp1Ord :: forall node. Ord node => Eq (EitherEdge node)
Ord, Int -> EitherEdge node -> ShowS
[EitherEdge node] -> ShowS
EitherEdge node -> String
(Int -> EitherEdge node -> ShowS)
-> (EitherEdge node -> String)
-> ([EitherEdge node] -> ShowS)
-> Show (EitherEdge node)
forall node. Show node => Int -> EitherEdge node -> ShowS
forall node. Show node => [EitherEdge node] -> ShowS
forall node. Show node => EitherEdge node -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [EitherEdge node] -> ShowS
$cshowList :: forall node. Show node => [EitherEdge node] -> ShowS
show :: EitherEdge node -> String
$cshow :: forall node. Show node => EitherEdge node -> String
showsPrec :: Int -> EitherEdge node -> ShowS
$cshowsPrec :: forall node. Show node => Int -> EitherEdge node -> ShowS
Show)


liftBin ::
   (Edge edge, Monoid a) =>
   (node0 -> node1 -> a) -> edge node0 -> edge node1 -> a
liftBin :: (node0 -> node1 -> a) -> edge node0 -> edge node1 -> a
liftBin node0 -> node1 -> a
op edge node0
e0 edge node1
e1 = a -> a -> a
forall a. Monoid a => a -> a -> a
mappend (node0 -> node1 -> a
op (edge node0 -> node0
forall (edge :: * -> *) node. Edge edge => edge node -> node
from edge node0
e0) (edge node1 -> node1
forall (edge :: * -> *) node. Edge edge => edge node -> node
from edge node1
e1)) (node0 -> node1 -> a
op (edge node0 -> node0
forall (edge :: * -> *) node. Edge edge => edge node -> node
to edge node0
e0) (edge node1 -> node1
forall (edge :: * -> *) node. Edge edge => edge node -> node
to edge node1
e1))

liftEdgeEq ::
   Edge edge => (node0 -> node1 -> Bool) -> edge node0 -> edge node1 -> Bool
liftEdgeEq :: (node0 -> node1 -> Bool) -> edge node0 -> edge node1 -> Bool
liftEdgeEq node0 -> node1 -> Bool
eq = (All -> Bool
getAll (All -> Bool) -> (edge node1 -> All) -> edge node1 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((edge node1 -> All) -> edge node1 -> Bool)
-> (edge node0 -> edge node1 -> All)
-> edge node0
-> edge node1
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (node0 -> node1 -> All) -> edge node0 -> edge node1 -> All
forall (edge :: * -> *) a node0 node1.
(Edge edge, Monoid a) =>
(node0 -> node1 -> a) -> edge node0 -> edge node1 -> a
liftBin (\node0
a node1
b -> Bool -> All
All (Bool -> All) -> Bool -> All
forall a b. (a -> b) -> a -> b
$ node0 -> node1 -> Bool
eq node0
a node1
b)

liftEdgeShowsPrec ::
   (Foldable edge) =>
   String -> (Int -> node -> ShowS) -> showList -> Int -> edge node -> ShowS
liftEdgeShowsPrec :: String
-> (Int -> node -> ShowS) -> showList -> Int -> edge node -> ShowS
liftEdgeShowsPrec String
name Int -> node -> ShowS
showsPrc showList
_showsList Int
p edge node
e =
   Bool -> ShowS -> ShowS
showParen (Int
pInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      String -> ShowS
showString String
name ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      Endo String -> ShowS
forall a. Endo a -> a -> a
appEndo ((node -> Endo String) -> edge node -> Endo String
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (\node
n -> ShowS -> Endo String
forall a. (a -> a) -> Endo a
Endo (ShowS -> Endo String) -> ShowS -> Endo String
forall a b. (a -> b) -> a -> b
$ Char -> ShowS
showChar Char
' ' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> node -> ShowS
showsPrc Int
11 node
n) edge node
e)

instance Eq1 DirEdge where liftEq :: (a -> b -> Bool) -> DirEdge a -> DirEdge b -> Bool
liftEq = (a -> b -> Bool) -> DirEdge a -> DirEdge b -> Bool
forall (edge :: * -> *) node0 node1.
Edge edge =>
(node0 -> node1 -> Bool) -> edge node0 -> edge node1 -> Bool
liftEdgeEq
instance Ord1 DirEdge where liftCompare :: (a -> b -> Ordering) -> DirEdge a -> DirEdge b -> Ordering
liftCompare = (a -> b -> Ordering) -> DirEdge a -> DirEdge b -> Ordering
forall (edge :: * -> *) a node0 node1.
(Edge edge, Monoid a) =>
(node0 -> node1 -> a) -> edge node0 -> edge node1 -> a
liftBin
instance Show1 DirEdge where liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> DirEdge a -> ShowS
liftShowsPrec = String
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> DirEdge a
-> ShowS
forall (edge :: * -> *) node showList.
Foldable edge =>
String
-> (Int -> node -> ShowS) -> showList -> Int -> edge node -> ShowS
liftEdgeShowsPrec String
"DirEdge"

instance Eq1 UndirEdge where liftEq :: (a -> b -> Bool) -> UndirEdge a -> UndirEdge b -> Bool
liftEq = (a -> b -> Bool) -> UndirEdge a -> UndirEdge b -> Bool
forall (edge :: * -> *) node0 node1.
Edge edge =>
(node0 -> node1 -> Bool) -> edge node0 -> edge node1 -> Bool
liftEdgeEq
instance Ord1 UndirEdge where liftCompare :: (a -> b -> Ordering) -> UndirEdge a -> UndirEdge b -> Ordering
liftCompare = (a -> b -> Ordering) -> UndirEdge a -> UndirEdge b -> Ordering
forall (edge :: * -> *) a node0 node1.
(Edge edge, Monoid a) =>
(node0 -> node1 -> a) -> edge node0 -> edge node1 -> a
liftBin
instance Show1 UndirEdge where liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> UndirEdge a -> ShowS
liftShowsPrec = String
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> UndirEdge a
-> ShowS
forall (edge :: * -> *) node showList.
Foldable edge =>
String
-> (Int -> node -> ShowS) -> showList -> Int -> edge node -> ShowS
liftEdgeShowsPrec String
"UndirEdge"

instance Eq1 EitherEdge where
   liftEq :: (a -> b -> Bool) -> EitherEdge a -> EitherEdge b -> Bool
liftEq a -> b -> Bool
eq EitherEdge a
ee0 EitherEdge b
ee1 =
      case (EitherEdge a
ee0, EitherEdge b
ee1) of
         (EDirEdge DirEdge a
e0, EDirEdge DirEdge b
e1) -> (a -> b -> Bool) -> DirEdge a -> DirEdge b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq a -> b -> Bool
eq DirEdge a
e0 DirEdge b
e1
         (EUndirEdge UndirEdge a
e0, EUndirEdge UndirEdge b
e1) -> (a -> b -> Bool) -> UndirEdge a -> UndirEdge b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq a -> b -> Bool
eq UndirEdge a
e0 UndirEdge b
e1
         (EitherEdge a, EitherEdge b)
_ -> Bool
False

instance Ord1 EitherEdge where
   liftCompare :: (a -> b -> Ordering) -> EitherEdge a -> EitherEdge b -> Ordering
liftCompare a -> b -> Ordering
cmp EitherEdge a
ee0 EitherEdge b
ee1 =
      case (EitherEdge a
ee0, EitherEdge b
ee1) of
         (EDirEdge DirEdge a
e0, EDirEdge DirEdge b
e1) -> (a -> b -> Ordering) -> DirEdge a -> DirEdge b -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare a -> b -> Ordering
cmp DirEdge a
e0 DirEdge b
e1
         (EUndirEdge UndirEdge a
e0, EUndirEdge UndirEdge b
e1) -> (a -> b -> Ordering) -> UndirEdge a -> UndirEdge b -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare a -> b -> Ordering
cmp UndirEdge a
e0 UndirEdge b
e1
         (EDirEdge DirEdge a
_, EUndirEdge UndirEdge b
_) -> Ordering
LT
         (EUndirEdge UndirEdge a
_, EDirEdge DirEdge b
_) -> Ordering
GT

instance Show1 EitherEdge where
   liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> EitherEdge a -> ShowS
liftShowsPrec Int -> a -> ShowS
showsPrc [a] -> ShowS
showsList Int
p EitherEdge a
ee =
      case EitherEdge a
ee of
         EDirEdge DirEdge a
e ->
            Bool -> ShowS -> ShowS
showParen (Int
pInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
            String -> ShowS
showString String
"EDirEdge " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> DirEdge a -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
showsPrc [a] -> ShowS
showsList Int
11 DirEdge a
e
         EUndirEdge UndirEdge a
e ->
            Bool -> ShowS -> ShowS
showParen (Int
pInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
            String -> ShowS
showString String
"EUndirEdge " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> UndirEdge a -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
showsPrc [a] -> ShowS
showsList Int
11 UndirEdge a
e


instance Functor DirEdge where
   fmap :: (a -> b) -> DirEdge a -> DirEdge b
fmap a -> b
f (DirEdge a
x a
y) = b -> b -> DirEdge b
forall node. node -> node -> DirEdge node
DirEdge (a -> b
f a
x) (a -> b
f a
y)

instance Foldable DirEdge where
   foldMap :: (a -> m) -> DirEdge a -> m
foldMap a -> m
f (DirEdge a
x a
y) = m -> m -> m
forall a. Monoid a => a -> a -> a
mappend (a -> m
f a
x) (a -> m
f a
y)

instance Foldable UndirEdge where
   foldMap :: (a -> m) -> UndirEdge a -> m
foldMap a -> m
f (UndirEdge a
x a
y) = m -> m -> m
forall a. Monoid a => a -> a -> a
mappend (a -> m
f a
x) (a -> m
f a
y)

instance Foldable EitherEdge where
   foldMap :: (a -> m) -> EitherEdge a -> m
foldMap a -> m
f EitherEdge a
ee =
      case EitherEdge a
ee of
         EDirEdge   DirEdge a
e -> (a -> m) -> DirEdge a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f DirEdge a
e
         EUndirEdge UndirEdge a
e -> (a -> m) -> UndirEdge a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f UndirEdge a
e

instance (QC.Arbitrary n) => QC.Arbitrary (DirEdge n) where
   arbitrary :: Gen (DirEdge n)
arbitrary = (n -> n -> DirEdge n) -> Gen n -> Gen n -> Gen (DirEdge n)
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 n -> n -> DirEdge n
forall node. node -> node -> DirEdge node
DirEdge Gen n
forall a. Arbitrary a => Gen a
QC.arbitrary Gen n
forall a. Arbitrary a => Gen a
QC.arbitrary
   shrink :: DirEdge n -> [DirEdge n]
shrink (DirEdge n
x n
y) = ((n, n) -> DirEdge n) -> [(n, n)] -> [DirEdge n]
forall a b. (a -> b) -> [a] -> [b]
map ((n -> n -> DirEdge n) -> (n, n) -> DirEdge n
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry n -> n -> DirEdge n
forall node. node -> node -> DirEdge node
DirEdge) ([(n, n)] -> [DirEdge n]) -> [(n, n)] -> [DirEdge n]
forall a b. (a -> b) -> a -> b
$ (n, n) -> [(n, n)]
forall a. Arbitrary a => a -> [a]
QC.shrink (n
x,n
y)

instance (QC.Arbitrary n, Ord n) => QC.Arbitrary (UndirEdge n) where
   arbitrary :: Gen (UndirEdge n)
arbitrary = (n -> n -> UndirEdge n) -> Gen n -> Gen n -> Gen (UndirEdge n)
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 n -> n -> UndirEdge n
forall node. Ord node => node -> node -> UndirEdge node
undirEdge Gen n
forall a. Arbitrary a => Gen a
QC.arbitrary Gen n
forall a. Arbitrary a => Gen a
QC.arbitrary
   shrink :: UndirEdge n -> [UndirEdge n]
shrink (UndirEdge n
x n
y) =
      Set (UndirEdge n) -> [UndirEdge n]
forall a. Set a -> [a]
Set.toList (Set (UndirEdge n) -> [UndirEdge n])
-> Set (UndirEdge n) -> [UndirEdge n]
forall a b. (a -> b) -> a -> b
$ [UndirEdge n] -> Set (UndirEdge n)
forall a. Ord a => [a] -> Set a
Set.fromList ([UndirEdge n] -> Set (UndirEdge n))
-> [UndirEdge n] -> Set (UndirEdge n)
forall a b. (a -> b) -> a -> b
$ ((n, n) -> UndirEdge n) -> [(n, n)] -> [UndirEdge n]
forall a b. (a -> b) -> [a] -> [b]
map ((n -> n -> UndirEdge n) -> (n, n) -> UndirEdge n
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry n -> n -> UndirEdge n
forall node. Ord node => node -> node -> UndirEdge node
undirEdge) ([(n, n)] -> [UndirEdge n]) -> [(n, n)] -> [UndirEdge n]
forall a b. (a -> b) -> a -> b
$ (n, n) -> [(n, n)]
forall a. Arbitrary a => a -> [a]
QC.shrink (n
x,n
y)


graphMap ::
   Graph edge node edgeLabel nodeLabel ->
   Map node (InOutMap edge node edgeLabel nodeLabel)
graphMap :: Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap edge node edgeLabel nodeLabel)
graphMap = (InOutMap (Wrap edge) node edgeLabel nodeLabel
 -> InOutMap edge node edgeLabel nodeLabel)
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Map node (InOutMap edge node edgeLabel nodeLabel)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap InOutMap (Wrap edge) node edgeLabel nodeLabel
-> InOutMap edge node edgeLabel nodeLabel
forall (e :: * -> *) n el nl.
InOutMap (Wrap e) n el nl -> InOutMap e n el nl
unwrapInOut (Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
 -> Map node (InOutMap edge node edgeLabel nodeLabel))
-> (Graph edge node edgeLabel nodeLabel
    -> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel))
-> Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap edge node edgeLabel nodeLabel)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

nodes ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel ->
   [node]
nodes :: Graph edge node edgeLabel nodeLabel -> [node]
nodes = Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel) -> [node]
forall k a. Map k a -> [k]
Map.keys (Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
 -> [node])
-> (Graph edge node edgeLabel nodeLabel
    -> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel))
-> Graph edge node edgeLabel nodeLabel
-> [node]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

nodeEdges ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel ->
   Map node (Set (edge node), nodeLabel, Set (edge node))
nodeEdges :: Graph edge node edgeLabel nodeLabel
-> Map node (Set (edge node), nodeLabel, Set (edge node))
nodeEdges =
   ((Map (Wrap edge node) edgeLabel, nodeLabel,
  Map (Wrap edge node) edgeLabel)
 -> (Set (edge node), nodeLabel, Set (edge node)))
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
-> Map node (Set (edge node), nodeLabel, Set (edge node))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap edge node) edgeLabel
ins,nodeLabel
n,Map (Wrap edge node) edgeLabel
outs) ->
         (Set (Wrap edge node) -> Set (edge node)
forall (f :: * -> *) a. Set (Wrap f a) -> Set (f a)
unwrapSet (Set (Wrap edge node) -> Set (edge node))
-> Set (Wrap edge node) -> Set (edge node)
forall a b. (a -> b) -> a -> b
$ Map (Wrap edge node) edgeLabel -> Set (Wrap edge node)
forall k a. Map k a -> Set k
Map.keysSet Map (Wrap edge node) edgeLabel
ins, nodeLabel
n, Set (Wrap edge node) -> Set (edge node)
forall (f :: * -> *) a. Set (Wrap f a) -> Set (f a)
unwrapSet (Set (Wrap edge node) -> Set (edge node))
-> Set (Wrap edge node) -> Set (edge node)
forall a b. (a -> b) -> a -> b
$ Map (Wrap edge node) edgeLabel -> Set (Wrap edge node)
forall k a. Map k a -> Set k
Map.keysSet Map (Wrap edge node) edgeLabel
outs)) (Map
   node
   (Map (Wrap edge node) edgeLabel, nodeLabel,
    Map (Wrap edge node) edgeLabel)
 -> Map node (Set (edge node), nodeLabel, Set (edge node)))
-> (Graph edge node edgeLabel nodeLabel
    -> Map
         node
         (Map (Wrap edge node) edgeLabel, nodeLabel,
          Map (Wrap edge node) edgeLabel))
-> Graph edge node edgeLabel nodeLabel
-> Map node (Set (edge node), nodeLabel, Set (edge node))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph edge node edgeLabel nodeLabel
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap


edgeLabels ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel ->
   Map (edge node) edgeLabel
edgeLabels :: Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
edgeLabels = Map (Wrap edge node) edgeLabel -> Map (edge node) edgeLabel
forall (e :: * -> *) n a. Map (Wrap e n) a -> Map (e n) a
unwrapMap (Map (Wrap edge node) edgeLabel -> Map (edge node) edgeLabel)
-> (Graph edge node edgeLabel nodeLabel
    -> Map (Wrap edge node) edgeLabel)
-> Graph edge node edgeLabel nodeLabel
-> Map (edge node) edgeLabel
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel
-> Map (Wrap edge node) edgeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel
-> Map (Wrap edge node) edgeLabel
edgeLabelsWrap

edgeLabelsWrap ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel ->
   Map (Wrap edge node) edgeLabel
edgeLabelsWrap :: Graph edge node edgeLabel nodeLabel
-> Map (Wrap edge node) edgeLabel
edgeLabelsWrap = ((Map (Wrap edge node) edgeLabel, nodeLabel,
  Map (Wrap edge node) edgeLabel)
 -> Map (Wrap edge node) edgeLabel)
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
-> Map (Wrap edge node) edgeLabel
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Map (Wrap edge node) edgeLabel, nodeLabel,
 Map (Wrap edge node) edgeLabel)
-> Map (Wrap edge node) edgeLabel
forall a b c. (a, b, c) -> a
fst3 (Map
   node
   (Map (Wrap edge node) edgeLabel, nodeLabel,
    Map (Wrap edge node) edgeLabel)
 -> Map (Wrap edge node) edgeLabel)
-> (Graph edge node edgeLabel nodeLabel
    -> Map
         node
         (Map (Wrap edge node) edgeLabel, nodeLabel,
          Map (Wrap edge node) edgeLabel))
-> Graph edge node edgeLabel nodeLabel
-> Map (Wrap edge node) edgeLabel
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

edgeSet ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel -> Set (edge node)
edgeSet :: Graph edge node edgeLabel nodeLabel -> Set (edge node)
edgeSet = Set (Wrap edge node) -> Set (edge node)
forall (f :: * -> *) a. Set (Wrap f a) -> Set (f a)
unwrapSet (Set (Wrap edge node) -> Set (edge node))
-> (Graph edge node edgeLabel nodeLabel -> Set (Wrap edge node))
-> Graph edge node edgeLabel nodeLabel
-> Set (edge node)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Map (Wrap edge node) edgeLabel, nodeLabel,
  Map (Wrap edge node) edgeLabel)
 -> Set (Wrap edge node))
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
-> Set (Wrap edge node)
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Map (Wrap edge node) edgeLabel -> Set (Wrap edge node)
forall k a. Map k a -> Set k
Map.keysSet (Map (Wrap edge node) edgeLabel -> Set (Wrap edge node))
-> ((Map (Wrap edge node) edgeLabel, nodeLabel,
     Map (Wrap edge node) edgeLabel)
    -> Map (Wrap edge node) edgeLabel)
-> (Map (Wrap edge node) edgeLabel, nodeLabel,
    Map (Wrap edge node) edgeLabel)
-> Set (Wrap edge node)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map (Wrap edge node) edgeLabel, nodeLabel,
 Map (Wrap edge node) edgeLabel)
-> Map (Wrap edge node) edgeLabel
forall a b c. (a, b, c) -> a
fst3) (Map
   node
   (Map (Wrap edge node) edgeLabel, nodeLabel,
    Map (Wrap edge node) edgeLabel)
 -> Set (Wrap edge node))
-> (Graph edge node edgeLabel nodeLabel
    -> Map
         node
         (Map (Wrap edge node) edgeLabel, nodeLabel,
          Map (Wrap edge node) edgeLabel))
-> Graph edge node edgeLabel nodeLabel
-> Set (Wrap edge node)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel
-> Map
     node
     (Map (Wrap edge node) edgeLabel, nodeLabel,
      Map (Wrap edge node) edgeLabel)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

edges ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel -> [edge node]
edges :: Graph edge node edgeLabel nodeLabel -> [edge node]
edges = Map (edge node) edgeLabel -> [edge node]
forall k a. Map k a -> [k]
Map.keys (Map (edge node) edgeLabel -> [edge node])
-> (Graph edge node edgeLabel nodeLabel
    -> Map (edge node) edgeLabel)
-> Graph edge node edgeLabel nodeLabel
-> [edge node]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
edgeLabels


{- |
prop> \(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr)
prop> \(TestGraph gr) -> Graph.reverse (Graph.reverse gr) == gr
-}
reverse ::
   (Reverse e, Ord n) =>
   Graph e n el nl -> Graph e n el nl
reverse :: Graph e n el nl -> Graph e n el nl
reverse =
   (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl -> Graph e n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e) n el nl)
  -> Map n (InOutMap (Wrap e) n el nl))
 -> Graph e n el nl -> Graph e n el nl)
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall a b. (a -> b) -> a -> b
$
   (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap e n) el
ins, nl
nl, Map (Wrap e n) el
outs) ->
         ((Wrap e n -> Wrap e n) -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys Wrap e n -> Wrap e n
forall (edge :: * -> *) node.
Reverse edge =>
Wrap edge node -> Wrap edge node
reverseEdgeWrap Map (Wrap e n) el
outs,
          nl
nl,
          (Wrap e n -> Wrap e n) -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys Wrap e n -> Wrap e n
forall (edge :: * -> *) node.
Reverse edge =>
Wrap edge node -> Wrap edge node
reverseEdgeWrap Map (Wrap e n) el
ins))

reverseEdgeWrap :: Reverse edge => Wrap edge node -> Wrap edge node
reverseEdgeWrap :: Wrap edge node -> Wrap edge node
reverseEdgeWrap = edge node -> Wrap edge node
forall (f :: * -> *) a. f a -> Wrap f a
wrap (edge node -> Wrap edge node)
-> (Wrap edge node -> edge node)
-> Wrap edge node
-> Wrap edge node
forall b c a. (b -> c) -> (a -> b) -> a -> c
. edge node -> edge node
forall (edge :: * -> *) node.
Reverse edge =>
edge node -> edge node
reverseEdge (edge node -> edge node)
-> (Wrap edge node -> edge node) -> Wrap edge node -> edge node
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap edge node -> edge node
forall (f :: * -> *) a. Wrap f a -> f a
unwrap


class Edge edge => Reverse edge where
   reverseEdge :: edge node -> edge node

instance Reverse DirEdge where
   reverseEdge :: DirEdge node -> DirEdge node
reverseEdge (DirEdge node
x node
y) = node -> node -> DirEdge node
forall node. node -> node -> DirEdge node
DirEdge node
y node
x


{- |
The index map must be an injection,
that is, nodes must not collaps.
Also the node and edge index maps must be consistent, i.e.

> from (edgeMap e) == nodeMap (from e)
> to   (edgeMap e) == nodeMap (to   e)

Strictly spoken, we would need the node map only for isolated nodes,
but we use it for all nodes for simplicity.
-}
mapKeys ::
   (Edge edge1, Ord node0, Ord node1) =>
   (node0 -> node1) ->
   (edge0 node0 -> edge1 node1) ->
   Graph edge0 node0 edgeLabel nodeLabel ->
   Graph edge1 node1 edgeLabel nodeLabel
mapKeys :: (node0 -> node1)
-> (edge0 node0 -> edge1 node1)
-> Graph edge0 node0 edgeLabel nodeLabel
-> Graph edge1 node1 edgeLabel nodeLabel
mapKeys node0 -> node1
f edge0 node0 -> edge1 node1
g =
   (Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
 -> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel))
-> Graph edge0 node0 edgeLabel nodeLabel
-> Graph edge1 node1 edgeLabel nodeLabel
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
  -> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel))
 -> Graph edge0 node0 edgeLabel nodeLabel
 -> Graph edge1 node1 edgeLabel nodeLabel)
-> (Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
    -> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel))
-> Graph edge0 node0 edgeLabel nodeLabel
-> Graph edge1 node1 edgeLabel nodeLabel
forall a b. (a -> b) -> a -> b
$
   (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
 -> InOutMap (Wrap edge1) node1 edgeLabel nodeLabel)
-> Map node1 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
-> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap edge0 node0) edgeLabel
ins,nodeLabel
nl,Map (Wrap edge0 node0) edgeLabel
outs) ->
         ((Wrap edge0 node0 -> Wrap edge1 node1)
-> Map (Wrap edge0 node0) edgeLabel
-> Map (Wrap edge1 node1) edgeLabel
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys (edge1 node1 -> Wrap edge1 node1
forall (f :: * -> *) a. f a -> Wrap f a
wrap (edge1 node1 -> Wrap edge1 node1)
-> (Wrap edge0 node0 -> edge1 node1)
-> Wrap edge0 node0
-> Wrap edge1 node1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. edge0 node0 -> edge1 node1
g (edge0 node0 -> edge1 node1)
-> (Wrap edge0 node0 -> edge0 node0)
-> Wrap edge0 node0
-> edge1 node1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap edge0 node0 -> edge0 node0
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap edge0 node0) edgeLabel
ins,
          nodeLabel
nl,
          (Wrap edge0 node0 -> Wrap edge1 node1)
-> Map (Wrap edge0 node0) edgeLabel
-> Map (Wrap edge1 node1) edgeLabel
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys (edge1 node1 -> Wrap edge1 node1
forall (f :: * -> *) a. f a -> Wrap f a
wrap (edge1 node1 -> Wrap edge1 node1)
-> (Wrap edge0 node0 -> edge1 node1)
-> Wrap edge0 node0
-> Wrap edge1 node1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. edge0 node0 -> edge1 node1
g (edge0 node0 -> edge1 node1)
-> (Wrap edge0 node0 -> edge0 node0)
-> Wrap edge0 node0
-> edge1 node1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap edge0 node0 -> edge0 node0
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap edge0 node0) edgeLabel
outs)) (Map node1 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
 -> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel))
-> (Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
    -> Map node1 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel))
-> Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
-> Map node1 (InOutMap (Wrap edge1) node1 edgeLabel nodeLabel)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
 -> InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
 -> InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
-> (node0 -> node1)
-> Map node0 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
-> Map node1 (InOutMap (Wrap edge0) node0 edgeLabel nodeLabel)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith (String
-> InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
-> InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
-> InOutMap (Wrap edge0) node0 edgeLabel nodeLabel
forall a. HasCallStack => String -> a
error String
"Graph.mapKeys: node map is not injective") node0 -> node1
f

{- |
prop> Graph.isEmpty (Graph.empty :: MonoGraph)
prop> Graph.isConsistent (Graph.empty :: MonoGraph)
-}
empty :: Graph edge node edgeLabel nodeLabel
empty :: Graph edge node edgeLabel nodeLabel
empty = Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
forall k a. Map k a
Map.empty

{- |
The node sets must be disjoint.
-}
union ::
   (Edge edge, Ord node) =>
   Graph edge node edgeLabel nodeLabel ->
   Graph edge node edgeLabel nodeLabel ->
   Graph edge node edgeLabel nodeLabel
union :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
union (Graph Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
ns0) (Graph Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
ns1) =
   Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph
      ((InOutMap (Wrap edge) node edgeLabel nodeLabel
 -> InOutMap (Wrap edge) node edgeLabel nodeLabel
 -> InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith (String
-> InOutMap (Wrap edge) node edgeLabel nodeLabel
-> InOutMap (Wrap edge) node edgeLabel nodeLabel
-> InOutMap (Wrap edge) node edgeLabel nodeLabel
forall a. HasCallStack => String -> a
error String
"Graph.union: node sets overlap") Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
ns0 Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
ns1)

instance
   (Edge edge, Ord node) =>
      Semigroup (Graph edge node edgeLabel nodeLabel) where
   <> :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
(<>) = Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
union

instance
   (Edge edge, Ord node) =>
      Monoid (Graph edge node edgeLabel nodeLabel) where
   mempty :: Graph edge node edgeLabel nodeLabel
mempty = Graph edge node edgeLabel nodeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
empty
   mappend :: Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
mappend = Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
-> Graph edge node edgeLabel nodeLabel
union


{- |
Node and edge sets must be equal.
-}
checkedZipWith ::
   (Edge edge, Ord node) =>
   MapU.Caller ->
   (nodeLabel0 -> nodeLabel1 -> nodeLabel2) ->
   (edgeLabel0 -> edgeLabel1 -> edgeLabel2) ->
   Graph edge node edgeLabel0 nodeLabel0 ->
   Graph edge node edgeLabel1 nodeLabel1 ->
   Graph edge node edgeLabel2 nodeLabel2
checkedZipWith :: String
-> (nodeLabel0 -> nodeLabel1 -> nodeLabel2)
-> (edgeLabel0 -> edgeLabel1 -> edgeLabel2)
-> Graph edge node edgeLabel0 nodeLabel0
-> Graph edge node edgeLabel1 nodeLabel1
-> Graph edge node edgeLabel2 nodeLabel2
checkedZipWith String
caller nodeLabel0 -> nodeLabel1 -> nodeLabel2
f edgeLabel0 -> edgeLabel1 -> edgeLabel2
g (Graph Map node (InOutMap (Wrap edge) node edgeLabel0 nodeLabel0)
ns0) (Graph Map node (InOutMap (Wrap edge) node edgeLabel1 nodeLabel1)
ns1) =
   Map node (InOutMap (Wrap edge) node edgeLabel2 nodeLabel2)
-> Graph edge node edgeLabel2 nodeLabel2
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map node (InOutMap (Wrap edge) node edgeLabel2 nodeLabel2)
 -> Graph edge node edgeLabel2 nodeLabel2)
-> Map node (InOutMap (Wrap edge) node edgeLabel2 nodeLabel2)
-> Graph edge node edgeLabel2 nodeLabel2
forall a b. (a -> b) -> a -> b
$
   String
-> (InOutMap (Wrap edge) node edgeLabel0 nodeLabel0
    -> InOutMap (Wrap edge) node edgeLabel1 nodeLabel1
    -> InOutMap (Wrap edge) node edgeLabel2 nodeLabel2)
-> Map node (InOutMap (Wrap edge) node edgeLabel0 nodeLabel0)
-> Map node (InOutMap (Wrap edge) node edgeLabel1 nodeLabel1)
-> Map node (InOutMap (Wrap edge) node edgeLabel2 nodeLabel2)
forall k a b c.
Ord k =>
String -> (a -> b -> c) -> Map k a -> Map k b -> Map k c
MapU.checkedZipWith (String
caller String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" node")
      (\(Map (Wrap edge node) edgeLabel0
ins0, nodeLabel0
n0, Map (Wrap edge node) edgeLabel0
outs0) (Map (Wrap edge node) edgeLabel1
ins1, nodeLabel1
n1, Map (Wrap edge node) edgeLabel1
outs1) ->
         (String
-> (edgeLabel0 -> edgeLabel1 -> edgeLabel2)
-> Map (Wrap edge node) edgeLabel0
-> Map (Wrap edge node) edgeLabel1
-> Map (Wrap edge node) edgeLabel2
forall k a b c.
Ord k =>
String -> (a -> b -> c) -> Map k a -> Map k b -> Map k c
MapU.checkedZipWith (String
caller String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" ins") edgeLabel0 -> edgeLabel1 -> edgeLabel2
g Map (Wrap edge node) edgeLabel0
ins0 Map (Wrap edge node) edgeLabel1
ins1,
          nodeLabel0 -> nodeLabel1 -> nodeLabel2
f nodeLabel0
n0 nodeLabel1
n1,
          String
-> (edgeLabel0 -> edgeLabel1 -> edgeLabel2)
-> Map (Wrap edge node) edgeLabel0
-> Map (Wrap edge node) edgeLabel1
-> Map (Wrap edge node) edgeLabel2
forall k a b c.
Ord k =>
String -> (a -> b -> c) -> Map k a -> Map k b -> Map k c
MapU.checkedZipWith (String
caller String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" outs") edgeLabel0 -> edgeLabel1 -> edgeLabel2
g Map (Wrap edge node) edgeLabel0
outs0 Map (Wrap edge node) edgeLabel1
outs1))
      Map node (InOutMap (Wrap edge) node edgeLabel0 nodeLabel0)
ns0 Map node (InOutMap (Wrap edge) node edgeLabel1 nodeLabel1)
ns1


nodeLabels :: (Edge e, Ord n) => Graph e n el nl -> Map n nl
nodeLabels :: Graph e n el nl -> Map n nl
nodeLabels = ((Map (Wrap e n) el, nl, Map (Wrap e n) el) -> nl)
-> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map n nl
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> nl
forall a b c. (a, b, c) -> b
snd3 (Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map n nl)
-> (Graph e n el nl
    -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Graph e n el nl
-> Map n nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
prop> \(GraphAndEdge gr e) -> Graph.lookupEdge e gr == Map.lookup e (Graph.edgeLabels gr)
-}
lookupEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Maybe el
lookupEdge :: e n -> Graph e n el nl -> Maybe el
lookupEdge e n
e (Graph Map n (InOutMap (Wrap e) n el nl)
g) =
   Wrap e n -> Map (Wrap e n) el -> Maybe el
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap e n
e) (Map (Wrap e n) el -> Maybe el)
-> (InOutMap (Wrap e) n el nl -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> Maybe el
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InOutMap (Wrap e) n el nl -> Map (Wrap e n) el
forall a b c. (a, b, c) -> c
thd3 (InOutMap (Wrap e) n el nl -> Maybe el)
-> Maybe (InOutMap (Wrap e) n el nl) -> Maybe el
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< n
-> Map n (InOutMap (Wrap e) n el nl)
-> Maybe (InOutMap (Wrap e) n el nl)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (e n -> n
forall (edge :: * -> *) node. Edge edge => edge node -> node
from e n
e) Map n (InOutMap (Wrap e) n el nl)
g

{- |
Alternative implementation for test:
-}
_lookupEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Maybe el
_lookupEdge :: e n -> Graph e n el nl -> Maybe el
_lookupEdge e n
e (Graph Map n (InOutMap (Wrap e) n el nl)
g) =
   Wrap e n -> Map (Wrap e n) el -> Maybe el
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap e n
e) (Map (Wrap e n) el -> Maybe el)
-> (InOutMap (Wrap e) n el nl -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> Maybe el
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InOutMap (Wrap e) n el nl -> Map (Wrap e n) el
forall a b c. (a, b, c) -> a
fst3 (InOutMap (Wrap e) n el nl -> Maybe el)
-> Maybe (InOutMap (Wrap e) n el nl) -> Maybe el
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< n
-> Map n (InOutMap (Wrap e) n el nl)
-> Maybe (InOutMap (Wrap e) n el nl)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup (e n -> n
forall (edge :: * -> *) node. Edge edge => edge node -> node
to e n
e) Map n (InOutMap (Wrap e) n el nl)
g


isEmpty :: Graph e n el nl -> Bool
isEmpty :: Graph e n el nl -> Bool
isEmpty = Map n (InOutMap (Wrap e) n el nl) -> Bool
forall k a. Map k a -> Bool
Map.null (Map n (InOutMap (Wrap e) n el nl) -> Bool)
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
prop> \(TestGraph gr) n -> Graph.lookupNode n gr == Map.lookup n (Graph.nodeLabels gr)
-}
lookupNode :: (Ord n) => n -> Graph e n el nl -> Maybe nl
lookupNode :: n -> Graph e n el nl -> Maybe nl
lookupNode n
n (Graph Map n (InOutMap (Wrap e) n el nl)
g) = (InOutMap (Wrap e) n el nl -> nl)
-> Maybe (InOutMap (Wrap e) n el nl) -> Maybe nl
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap InOutMap (Wrap e) n el nl -> nl
forall a b c. (a, b, c) -> b
snd3 (Maybe (InOutMap (Wrap e) n el nl) -> Maybe nl)
-> Maybe (InOutMap (Wrap e) n el nl) -> Maybe nl
forall a b. (a -> b) -> a -> b
$ n
-> Map n (InOutMap (Wrap e) n el nl)
-> Maybe (InOutMap (Wrap e) n el nl)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup n
n Map n (InOutMap (Wrap e) n el nl)
g

{- |
Direct predecessors of a node,
i.e. nodes with an outgoing edge to the queried node.
-}
predecessors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]
predecessors :: Graph e n el nl -> n -> [n]
predecessors Graph e n el nl
g n
n =
   (Wrap e n -> n) -> [Wrap e n] -> [n]
forall a b. (a -> b) -> [a] -> [b]
map Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
fromWrap ([Wrap e n] -> [n])
-> (Graph e n el nl -> [Wrap e n]) -> Graph e n el nl -> [n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Wrap e n) el -> [Wrap e n]
forall k a. Map k a -> [k]
Map.keys (Map (Wrap e n) el -> [Wrap e n])
-> (Graph e n el nl -> Map (Wrap e n) el)
-> Graph e n el nl
-> [Wrap e n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map (Wrap e n) el
forall a b c. (a, b, c) -> a
fst3 ((Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map (Wrap e n) el)
-> (Graph e n el nl -> (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Graph e n el nl
-> Map (Wrap e n) el
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> n
-> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (String -> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall a. HasCallStack => String -> a
error String
"predecessors: unknown node") n
n (Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
 -> (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> (Graph e n el nl
    -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Graph e n el nl
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap (Graph e n el nl -> [n]) -> Graph e n el nl -> [n]
forall a b. (a -> b) -> a -> b
$ Graph e n el nl
g

{- |
Direct successors of a node,
i.e. nodes with an incoming edge from the queried node.
-}
successors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]
successors :: Graph e n el nl -> n -> [n]
successors Graph e n el nl
g n
n =
   (Wrap e n -> n) -> [Wrap e n] -> [n]
forall a b. (a -> b) -> [a] -> [b]
map Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
toWrap ([Wrap e n] -> [n])
-> (Graph e n el nl -> [Wrap e n]) -> Graph e n el nl -> [n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Wrap e n) el -> [Wrap e n]
forall k a. Map k a -> [k]
Map.keys (Map (Wrap e n) el -> [Wrap e n])
-> (Graph e n el nl -> Map (Wrap e n) el)
-> Graph e n el nl
-> [Wrap e n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map (Wrap e n) el
forall a b c. (a, b, c) -> c
thd3 ((Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Map (Wrap e n) el)
-> (Graph e n el nl -> (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Graph e n el nl
-> Map (Wrap e n) el
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> n
-> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (String -> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall a. HasCallStack => String -> a
error String
"successors: unknown node") n
n (Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
 -> (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> (Graph e n el nl
    -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Graph e n el nl
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap (Graph e n el nl -> [n]) -> Graph e n el nl -> [n]
forall a b. (a -> b) -> a -> b
$ Graph e n el nl
g

{-# DEPRECATED adjacentEdges "Use adjacentEdgeSet instead." #-}
adjacentEdges, adjacentEdgeSet ::
   (Edge e, Ord n) =>
   Graph e n el nl -> n -> Set (e n)
adjacentEdges :: Graph e n el nl -> n -> Set (e n)
adjacentEdges = Graph e n el nl -> n -> Set (e n)
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Graph e n el nl -> n -> Set (e n)
adjacentEdgeSet
adjacentEdgeSet :: Graph e n el nl -> n -> Set (e n)
adjacentEdgeSet Graph e n el nl
g n
n =
   (\(Map (Wrap e n) el
ins,nl
_nl,Map (Wrap e n) el
outs) ->
      Set (Wrap e n) -> Set (e n)
forall (f :: * -> *) a. Set (Wrap f a) -> Set (f a)
unwrapSet (Set (Wrap e n) -> Set (e n)) -> Set (Wrap e n) -> Set (e n)
forall a b. (a -> b) -> a -> b
$ Map (Wrap e n) el -> Set (Wrap e n)
forall k a. Map k a -> Set k
Map.keysSet Map (Wrap e n) el
ins Set (Wrap e n) -> Set (Wrap e n) -> Set (Wrap e n)
forall a. Ord a => Set a -> Set a -> Set a
`Set.union` Map (Wrap e n) el -> Set (Wrap e n)
forall k a. Map k a -> Set k
Map.keysSet Map (Wrap e n) el
outs) ((Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Set (e n))
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el) -> Set (e n)
forall a b. (a -> b) -> a -> b
$
   (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> n
-> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (String -> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall a. HasCallStack => String -> a
error String
"adjacentEdgeSet: unknown node") n
n (Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
 -> (Map (Wrap e n) el, nl, Map (Wrap e n) el))
-> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
-> (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall a b. (a -> b) -> a -> b
$
   Graph e n el nl -> Map n (Map (Wrap e n) el, nl, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap Graph e n el nl
g

{-
In constrast to Map.intersectWith ($), unaffected values are preserved.
-}
applyMap :: (Ord k) => Map k (a -> a) -> Map k a -> Map k a
applyMap :: Map k (a -> a) -> Map k a -> Map k a
applyMap Map k (a -> a)
f Map k a
x =
   Map k a -> Map k a -> Map k a
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union (((a -> a) -> a -> a) -> Map k (a -> a) -> Map k a -> Map k a
forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
Map.intersectionWith (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
($) Map k (a -> a)
f Map k a
x) Map k a
x

{- |
Node to be deleted must be contained in the graph.

prop> \(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr
prop> \(TestGraph gr) n nl -> Graph.deleteNode n (Graph.insertNode n nl gr) == deleteNodeIfExists n gr
prop> \(TestGraph gr) -> let isolatedNodes = filter (isolated gr) $ Graph.nodes gr in not (null isolatedNodes) ==> QC.forAll (QC.elements isolatedNodes) $ \n nl -> Graph.insertNode n nl gr == Graph.insertNode n nl (Graph.deleteNode n gr)
-}
deleteNode ::
   (Edge e, Ord n) =>
   n -> Graph e n el nl -> Graph e n el nl
deleteNode :: n -> Graph e n el nl -> Graph e n el nl
deleteNode n
n =
   (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl -> Graph e n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e) n el nl)
  -> Map n (InOutMap (Wrap e) n el nl))
 -> Graph e n el nl -> Graph e n el nl)
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall a b. (a -> b) -> a -> b
$ \Map n (InOutMap (Wrap e) n el nl)
ns ->
   case InOutMap (Wrap e) n el nl
-> n
-> Map n (InOutMap (Wrap e) n el nl)
-> InOutMap (Wrap e) n el nl
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (String -> InOutMap (Wrap e) n el nl
forall a. HasCallStack => String -> a
error String
"deleteNode: unknown node") n
n Map n (InOutMap (Wrap e) n el nl)
ns of
      (Map (Wrap e n) el
ins, nl
_nl, Map (Wrap e n) el
outs) ->
         Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => Map k (a -> a) -> Map k a -> Map k a
applyMap
            ((Wrap e n -> n)
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
fromWrap (Map
   (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl))
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
             (Wrap e n
 -> el -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map (Wrap e n) el
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (\Wrap e n
e el
_ -> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall c d a b. (c -> d) -> (a, b, c) -> (a, b, d)
mapThd3 ((Map (Wrap e n) el -> Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> InOutMap (Wrap e) n el nl
forall a b. (a -> b) -> a -> b
$ Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Wrap e n
e) Map (Wrap e n) el
ins)  (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
         Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => Map k (a -> a) -> Map k a -> Map k a
applyMap
            ((Wrap e n -> n)
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
toWrap   (Map
   (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl))
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
             (Wrap e n
 -> el -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map (Wrap e n) el
-> Map
     (Wrap e n) (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (\Wrap e n
e el
_ -> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall a d b c. (a -> d) -> (a, b, c) -> (d, b, c)
mapFst3 ((Map (Wrap e n) el -> Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> InOutMap (Wrap e) n el nl
forall a b. (a -> b) -> a -> b
$ Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete Wrap e n
e) Map (Wrap e n) el
outs) (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
         n
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete n
n Map n (InOutMap (Wrap e) n el nl)
ns

{- |
Could be implemented more efficiently.
-}
deleteNodeSet ::
   (Edge e, Ord n) =>
   Set n -> Graph e n el nl -> Graph e n el nl
deleteNodeSet :: Set n -> Graph e n el nl -> Graph e n el nl
deleteNodeSet Set n
delNs Graph e n el nl
g = (Graph e n el nl -> n -> Graph e n el nl)
-> Graph e n el nl -> Set n -> Graph e n el nl
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl ((n -> Graph e n el nl -> Graph e n el nl)
-> Graph e n el nl -> n -> Graph e n el nl
forall a b c. (a -> b -> c) -> b -> a -> c
flip n -> Graph e n el nl -> Graph e n el nl
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
n -> Graph e n el nl -> Graph e n el nl
deleteNode) Graph e n el nl
g Set n
delNs

{- |
prop> \(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr
prop> \(GraphAndEdge gr e) el -> Graph.deleteEdge e (Graph.insertEdge e el gr) == Graph.deleteEdge e gr
prop> \(GraphAndEdge gr e) el -> Graph.insertEdge e el gr == Graph.insertEdge e el (Graph.deleteEdge e gr)
-}
deleteEdge ::
   (Edge e, Ord n) =>
   e n -> Graph e n el nl -> Graph e n el nl
deleteEdge :: e n -> Graph e n el nl -> Graph e n el nl
deleteEdge e n
e =
   (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl -> Graph e n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e) n el nl)
  -> Map n (InOutMap (Wrap e) n el nl))
 -> Graph e n el nl -> Graph e n el nl)
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall a b. (a -> b) -> a -> b
$
      (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> n
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust ((Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall c d a b. (c -> d) -> (a, b, c) -> (a, b, d)
mapThd3 ((Map (Wrap e n) el -> Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> InOutMap (Wrap e) n el nl
forall a b. (a -> b) -> a -> b
$ Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete (Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall a b. (a -> b) -> a -> b
$ e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap e n
e) (e n -> n
forall (edge :: * -> *) node. Edge edge => edge node -> node
from e n
e) (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> n
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust ((Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall a d b c. (a -> d) -> (a, b, c) -> (d, b, c)
mapFst3 ((Map (Wrap e n) el -> Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl
-> InOutMap (Wrap e) n el nl
forall a b. (a -> b) -> a -> b
$ Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete (Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> Wrap e n -> Map (Wrap e n) el -> Map (Wrap e n) el
forall a b. (a -> b) -> a -> b
$ e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap e n
e) (e n -> n
forall (edge :: * -> *) node. Edge edge => edge node -> node
to e n
e)

{- |
prop> \(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr == Graph.deleteEdge e gr
-}
filterEdgeWithKey ::
   (Edge e, Ord n) =>
   (e n -> el -> Bool) ->
   Graph e n el nl -> Graph e n el nl
filterEdgeWithKey :: (e n -> el -> Bool) -> Graph e n el nl -> Graph e n el nl
filterEdgeWithKey e n -> el -> Bool
f =
   Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl)
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap e n) el
ins, nl
nl, Map (Wrap e n) el
outs) ->
         ((Wrap e n -> el -> Bool) -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey (e n -> el -> Bool
f (e n -> el -> Bool) -> (Wrap e n -> e n) -> Wrap e n -> el -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e n -> e n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e n) el
ins, nl
nl,
          (Wrap e n -> el -> Bool) -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey (e n -> el -> Bool
f (e n -> el -> Bool) -> (Wrap e n -> e n) -> Wrap e n -> el -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e n -> e n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e n) el
outs)) (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Map n (InOutMap (Wrap e) n el nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
You may only use this for filtering edges
and use more specialised types as a result.
You must not alter source and target nodes of edges.
-}
mapMaybeEdgeKeys ::
   (Edge e1, Ord n) =>
   (e0 n -> Maybe (e1 n)) ->
   Graph e0 n el nl -> Graph e1 n el nl
mapMaybeEdgeKeys :: (e0 n -> Maybe (e1 n)) -> Graph e0 n el nl -> Graph e1 n el nl
mapMaybeEdgeKeys e0 n -> Maybe (e1 n)
f =
   (Map n (InOutMap (Wrap e0) n el nl)
 -> Map n (InOutMap (Wrap e1) n el nl))
-> Graph e0 n el nl -> Graph e1 n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e0) n el nl)
  -> Map n (InOutMap (Wrap e1) n el nl))
 -> Graph e0 n el nl -> Graph e1 n el nl)
-> (Map n (InOutMap (Wrap e0) n el nl)
    -> Map n (InOutMap (Wrap e1) n el nl))
-> Graph e0 n el nl
-> Graph e1 n el nl
forall a b. (a -> b) -> a -> b
$
   (InOutMap (Wrap e0) n el nl -> InOutMap (Wrap e1) n el nl)
-> Map n (InOutMap (Wrap e0) n el nl)
-> Map n (InOutMap (Wrap e1) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap e0 n) el
ins, nl
nl, Map (Wrap e0 n) el
outs) ->
         ((Wrap e0 n -> Maybe (Wrap e1 n))
-> Map (Wrap e0 n) el -> Map (Wrap e1 n) el
forall k1 k0 a. Ord k1 => (k0 -> Maybe k1) -> Map k0 a -> Map k1 a
MapU.mapMaybeKeys ((e1 n -> Wrap e1 n) -> Maybe (e1 n) -> Maybe (Wrap e1 n)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap e1 n -> Wrap e1 n
forall (f :: * -> *) a. f a -> Wrap f a
wrap (Maybe (e1 n) -> Maybe (Wrap e1 n))
-> (Wrap e0 n -> Maybe (e1 n)) -> Wrap e0 n -> Maybe (Wrap e1 n)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. e0 n -> Maybe (e1 n)
f (e0 n -> Maybe (e1 n))
-> (Wrap e0 n -> e0 n) -> Wrap e0 n -> Maybe (e1 n)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e0 n -> e0 n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e0 n) el
ins,
          nl
nl,
          (Wrap e0 n -> Maybe (Wrap e1 n))
-> Map (Wrap e0 n) el -> Map (Wrap e1 n) el
forall k1 k0 a. Ord k1 => (k0 -> Maybe k1) -> Map k0 a -> Map k1 a
MapU.mapMaybeKeys ((e1 n -> Wrap e1 n) -> Maybe (e1 n) -> Maybe (Wrap e1 n)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap e1 n -> Wrap e1 n
forall (f :: * -> *) a. f a -> Wrap f a
wrap (Maybe (e1 n) -> Maybe (Wrap e1 n))
-> (Wrap e0 n -> Maybe (e1 n)) -> Wrap e0 n -> Maybe (Wrap e1 n)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. e0 n -> Maybe (e1 n)
f (e0 n -> Maybe (e1 n))
-> (Wrap e0 n -> e0 n) -> Wrap e0 n -> Maybe (e1 n)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e0 n -> e0 n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e0 n) el
outs))

{- |
Same restrictions as in 'mapMaybeEdgeKeys'.
-}
mapEdgeKeys ::
   (Edge e1, Ord n) =>
   (e0 n -> e1 n) ->
   Graph e0 n el nl -> Graph e1 n el nl
mapEdgeKeys :: (e0 n -> e1 n) -> Graph e0 n el nl -> Graph e1 n el nl
mapEdgeKeys e0 n -> e1 n
f =
   (Map n (InOutMap (Wrap e0) n el nl)
 -> Map n (InOutMap (Wrap e1) n el nl))
-> Graph e0 n el nl -> Graph e1 n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e0) n el nl)
  -> Map n (InOutMap (Wrap e1) n el nl))
 -> Graph e0 n el nl -> Graph e1 n el nl)
-> (Map n (InOutMap (Wrap e0) n el nl)
    -> Map n (InOutMap (Wrap e1) n el nl))
-> Graph e0 n el nl
-> Graph e1 n el nl
forall a b. (a -> b) -> a -> b
$
   (InOutMap (Wrap e0) n el nl -> InOutMap (Wrap e1) n el nl)
-> Map n (InOutMap (Wrap e0) n el nl)
-> Map n (InOutMap (Wrap e1) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
      (\(Map (Wrap e0 n) el
ins, nl
nl, Map (Wrap e0 n) el
outs) ->
         ((Wrap e0 n -> Wrap e1 n)
-> Map (Wrap e0 n) el -> Map (Wrap e1 n) el
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys (e1 n -> Wrap e1 n
forall (f :: * -> *) a. f a -> Wrap f a
wrap (e1 n -> Wrap e1 n)
-> (Wrap e0 n -> e1 n) -> Wrap e0 n -> Wrap e1 n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. e0 n -> e1 n
f (e0 n -> e1 n) -> (Wrap e0 n -> e0 n) -> Wrap e0 n -> e1 n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e0 n -> e0 n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e0 n) el
ins,
          nl
nl,
          (Wrap e0 n -> Wrap e1 n)
-> Map (Wrap e0 n) el -> Map (Wrap e1 n) el
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys (e1 n -> Wrap e1 n
forall (f :: * -> *) a. f a -> Wrap f a
wrap (e1 n -> Wrap e1 n)
-> (Wrap e0 n -> e1 n) -> Wrap e0 n -> Wrap e1 n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. e0 n -> e1 n
f (e0 n -> e1 n) -> (Wrap e0 n -> e0 n) -> Wrap e0 n -> e1 n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e0 n -> e0 n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e0 n) el
outs))

{- |
In the current implementation
existing nodes are replaced with new labels
and existing edges are maintained.
However, I think we should better have an extra function for this purpose
and you should not rely on this behavior.

prop> \(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr
prop> \(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) == Just nl
-}
insertNode ::
   (Ord n) => n -> nl -> Graph e n el nl -> Graph e n el nl
insertNode :: n -> nl -> Graph e n el nl -> Graph e n el nl
insertNode n
n nl
nl =
   Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl)
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (InOutMap (Wrap e) n el nl
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> n
-> InOutMap (Wrap e) n el nl
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith
      (\InOutMap (Wrap e) n el nl
_ (Map (Wrap e n) el
ins, nl
_, Map (Wrap e n) el
outs) -> (Map (Wrap e n) el
ins, nl
nl, Map (Wrap e n) el
outs))
      n
n (Map (Wrap e n) el
forall k a. Map k a
Map.empty, nl
nl, Map (Wrap e n) el
forall k a. Map k a
Map.empty) (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Map n (InOutMap (Wrap e) n el nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
prop> \(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr
prop> \(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) == Just el
-}
insertEdge ::
   (Edge e, Ord n) =>
   e n -> el -> Graph e n el nl -> Graph e n el nl
insertEdge :: e n -> el -> Graph e n el nl -> Graph e n el nl
insertEdge e n
e el
el = Map (e n) el -> Graph e n el nl -> Graph e n el nl
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Map (e n) el -> Graph e n el nl -> Graph e n el nl
insertEdgeSet (Map (e n) el -> Graph e n el nl -> Graph e n el nl)
-> Map (e n) el -> Graph e n el nl -> Graph e n el nl
forall a b. (a -> b) -> a -> b
$ e n -> el -> Map (e n) el
forall k a. k -> a -> Map k a
Map.singleton e n
e el
el

{- |
In the current implementation
existing edges are replaced with new labels.
However, I think we should better have an extra function for this purpose
and you should not rely on this behavior.
It is an unchecked error if edges between non-existing nodes are inserted.
-}
insertEdgeSet ::
   (Edge e, Ord n) =>
   Map (e n) el -> Graph e n el nl -> Graph e n el nl
insertEdgeSet :: Map (e n) el -> Graph e n el nl -> Graph e n el nl
insertEdgeSet Map (e n) el
es =
   let ess :: Map (Wrap e n) (Map (Wrap e n) el)
ess = (Wrap e n -> el -> Map (Wrap e n) el)
-> Map (Wrap e n) el -> Map (Wrap e n) (Map (Wrap e n) el)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey Wrap e n -> el -> Map (Wrap e n) el
forall k a. k -> a -> Map k a
Map.singleton (Map (Wrap e n) el -> Map (Wrap e n) (Map (Wrap e n) el))
-> Map (Wrap e n) el -> Map (Wrap e n) (Map (Wrap e n) el)
forall a b. (a -> b) -> a -> b
$ Map (e n) el -> Map (Wrap e n) el
forall (e :: * -> *) n a. Map (e n) a -> Map (Wrap e n) a
wrapMap Map (e n) el
es
   in  (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl -> Graph e n el nl
forall n0 (e0 :: * -> *) el0 nl0 n1 (e1 :: * -> *) el1 nl1.
(Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph ((Map n (InOutMap (Wrap e) n el nl)
  -> Map n (InOutMap (Wrap e) n el nl))
 -> Graph e n el nl -> Graph e n el nl)
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Graph e n el nl
forall a b. (a -> b) -> a -> b
$
       Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => Map k (a -> a) -> Map k a -> Map k a
applyMap
          ((Map (Wrap e n) el
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Map (Wrap e n) el
new -> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall a d b c. (a -> d) -> (a, b, c) -> (d, b, c)
mapFst3 (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Map (Wrap e n) el
new)) (Map n (Map (Wrap e n) el)
 -> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl))
-> Map n (Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
           (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> (Wrap e n -> n)
-> Map (Wrap e n) (Map (Wrap e n) el)
-> Map n (Map (Wrap e n) el)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
toWrap   Map (Wrap e n) (Map (Wrap e n) el)
ess) (Map n (InOutMap (Wrap e) n el nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> (Map n (InOutMap (Wrap e) n el nl)
    -> Map n (InOutMap (Wrap e) n el nl))
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
       Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a. Ord k => Map k (a -> a) -> Map k a -> Map k a
applyMap
          ((Map (Wrap e n) el
 -> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
-> Map n (Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Map (Wrap e n) el
new -> (Map (Wrap e n) el -> Map (Wrap e n) el)
-> InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl
forall c d a b. (c -> d) -> (a, b, c) -> (a, b, d)
mapThd3 (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Map (Wrap e n) el
new)) (Map n (Map (Wrap e n) el)
 -> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl))
-> Map n (Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl -> InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
           (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> (Wrap e n -> n)
-> Map (Wrap e n) (Map (Wrap e n) el)
-> Map n (Map (Wrap e n) el)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
fromWrap Map (Wrap e n) (Map (Wrap e n) el)
ess)

fromList ::
   (Edge e, Ord n) =>
   [LabeledNode n nl] -> [LabeledEdge e n el] -> Graph e n el nl
fromList :: [LabeledNode n nl] -> [LabeledEdge e n el] -> Graph e n el nl
fromList [LabeledNode n nl]
ns [LabeledEdge e n el]
es =
   Map n nl -> Map (Wrap e n) el -> Graph e n el nl
forall (e :: * -> *) n nl el.
(Edge e, Ord n) =>
Map n nl -> Map (Wrap e n) el -> Graph e n el nl
fromMapWrap ([LabeledNode n nl] -> Map n nl
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [LabeledNode n nl]
ns) (Map (Wrap e n) el -> Graph e n el nl)
-> Map (Wrap e n) el -> Graph e n el nl
forall a b. (a -> b) -> a -> b
$ [(Wrap e n, el)] -> Map (Wrap e n) el
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(Wrap e n, el)] -> Map (Wrap e n) el)
-> [(Wrap e n, el)] -> Map (Wrap e n) el
forall a b. (a -> b) -> a -> b
$ (LabeledEdge e n el -> (Wrap e n, el))
-> [LabeledEdge e n el] -> [(Wrap e n, el)]
forall a b. (a -> b) -> [a] -> [b]
map ((e n -> Wrap e n) -> LabeledEdge e n el -> (Wrap e n, el)
forall a c b. (a -> c) -> (a, b) -> (c, b)
mapFst e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap) [LabeledEdge e n el]
es

{- |
prop> \(TestGraph gr) -> gr == Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr)
-}
fromMap ::
   (Edge e, Ord n) =>
   Map n nl -> Map (e n) el -> Graph e n el nl
fromMap :: Map n nl -> Map (e n) el -> Graph e n el nl
fromMap Map n nl
ns = Map n nl -> Map (Wrap e n) el -> Graph e n el nl
forall (e :: * -> *) n nl el.
(Edge e, Ord n) =>
Map n nl -> Map (Wrap e n) el -> Graph e n el nl
fromMapWrap Map n nl
ns (Map (Wrap e n) el -> Graph e n el nl)
-> (Map (e n) el -> Map (Wrap e n) el)
-> Map (e n) el
-> Graph e n el nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (e n) el -> Map (Wrap e n) el
forall (e :: * -> *) n a. Map (e n) a -> Map (Wrap e n) a
wrapMap

fromMapWrap ::
   (Edge e, Ord n) =>
   Map n nl -> Map (Wrap e n) el -> Graph e n el nl
fromMapWrap :: Map n nl -> Map (Wrap e n) el -> Graph e n el nl
fromMapWrap Map n nl
ns Map (Wrap e n) el
es =
   let ess :: Map (Wrap e n) (Map (Wrap e n) el)
ess = (Wrap e n -> el -> Map (Wrap e n) el)
-> Map (Wrap e n) el -> Map (Wrap e n) (Map (Wrap e n) el)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey Wrap e n -> el -> Map (Wrap e n) el
forall k a. k -> a -> Map k a
Map.singleton Map (Wrap e n) el
es
   in  Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl)
-> Map n (InOutMap (Wrap e) n el nl) -> Graph e n el nl
forall a b. (a -> b) -> a -> b
$
       (Map (Wrap e n) el
 -> (Map (Wrap e n) el, nl) -> InOutMap (Wrap e) n el nl)
-> TotalMap n (Map (Wrap e n) el)
-> Map n (Map (Wrap e n) el, nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall k a b c.
Ord k =>
(a -> b -> c) -> TotalMap k a -> Map k b -> Map k c
TMap.intersectionPartialWith (\Map (Wrap e n) el
ins (Map (Wrap e n) el
outs, nl
nl) -> (Map (Wrap e n) el
ins,nl
nl,Map (Wrap e n) el
outs))
          (Map (Wrap e n) el
-> Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el)
forall a k. a -> Map k a -> TotalMap k a
TMap.cons Map (Wrap e n) el
forall k a. Map k a
Map.empty (Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el))
-> Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el)
forall a b. (a -> b) -> a -> b
$ (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> (Wrap e n -> n)
-> Map (Wrap e n) (Map (Wrap e n) el)
-> Map n (Map (Wrap e n) el)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
toWrap   Map (Wrap e n) (Map (Wrap e n) el)
ess) (Map n (Map (Wrap e n) el, nl)
 -> Map n (InOutMap (Wrap e) n el nl))
-> Map n (Map (Wrap e n) el, nl)
-> Map n (InOutMap (Wrap e) n el nl)
forall a b. (a -> b) -> a -> b
$
       (Map (Wrap e n) el -> nl -> (Map (Wrap e n) el, nl))
-> TotalMap n (Map (Wrap e n) el)
-> Map n nl
-> Map n (Map (Wrap e n) el, nl)
forall k a b c.
Ord k =>
(a -> b -> c) -> TotalMap k a -> Map k b -> Map k c
TMap.intersectionPartialWith (,)
          (Map (Wrap e n) el
-> Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el)
forall a k. a -> Map k a -> TotalMap k a
TMap.cons Map (Wrap e n) el
forall k a. Map k a
Map.empty (Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el))
-> Map n (Map (Wrap e n) el) -> TotalMap n (Map (Wrap e n) el)
forall a b. (a -> b) -> a -> b
$ (Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el)
-> (Wrap e n -> n)
-> Map (Wrap e n) (Map (Wrap e n) el)
-> Map n (Map (Wrap e n) el)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Map (Wrap e n) el -> Map (Wrap e n) el -> Map (Wrap e n) el
forall k a. Ord k => Map k a -> Map k a -> Map k a
Map.union Wrap e n -> n
forall (edge :: * -> *) node. Edge edge => Wrap edge node -> node
fromWrap Map (Wrap e n) (Map (Wrap e n) el)
ess) Map n nl
ns


{- |
prop> \(TestGraph gr) -> Graph.mapNode id gr == gr
-}
mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNode nl0 -> nl1
f =
   Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1)
-> (Graph e n el nl0 -> Map n (InOutMap (Wrap e) n el nl1))
-> Graph e n el nl0
-> Graph e n el nl1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl1)
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl1)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Map (Wrap e n) el
ins,nl0
n,Map (Wrap e n) el
outs) -> (Map (Wrap e n) el
ins, nl0 -> nl1
f nl0
n, Map (Wrap e n) el
outs)) (Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> Map n (InOutMap (Wrap e) n el nl1))
-> (Graph e n el nl0
    -> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el))
-> Graph e n el nl0
-> Map n (InOutMap (Wrap e) n el nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl0
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

mapNodeWithKey :: (n -> nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNodeWithKey :: (n -> nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNodeWithKey n -> nl0 -> nl1
f =
   Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1)
-> (Graph e n el nl0 -> Map n (InOutMap (Wrap e) n el nl1))
-> Graph e n el nl0
-> Graph e n el nl1
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (n
 -> (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl1)
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl1)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (\n
n (Map (Wrap e n) el
ins,nl0
nl,Map (Wrap e n) el
outs) -> (Map (Wrap e n) el
ins, n -> nl0 -> nl1
f n
n nl0
nl, Map (Wrap e n) el
outs)) (Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> Map n (InOutMap (Wrap e) n el nl1))
-> (Graph e n el nl0
    -> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el))
-> Graph e n el nl0
-> Map n (InOutMap (Wrap e) n el nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el nl0
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
prop> \(TestGraph gr) -> Graph.mapEdge id gr == gr
-}
mapEdge :: (el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapEdge :: (el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapEdge el0 -> el1
f =
   Map n (InOutMap (Wrap e) n el1 nl) -> Graph e n el1 nl
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el1 nl) -> Graph e n el1 nl)
-> (Graph e n el0 nl -> Map n (InOutMap (Wrap e) n el1 nl))
-> Graph e n el0 nl
-> Graph e n el1 nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
 -> InOutMap (Wrap e) n el1 nl)
-> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
-> Map n (InOutMap (Wrap e) n el1 nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Map (Wrap e n) el0
ins,nl
n,Map (Wrap e n) el0
outs) -> ((el0 -> el1) -> Map (Wrap e n) el0 -> Map (Wrap e n) el1
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap el0 -> el1
f Map (Wrap e n) el0
ins, nl
n, (el0 -> el1) -> Map (Wrap e n) el0 -> Map (Wrap e n) el1
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap el0 -> el1
f Map (Wrap e n) el0
outs)) (Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
 -> Map n (InOutMap (Wrap e) n el1 nl))
-> (Graph e n el0 nl
    -> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0))
-> Graph e n el0 nl
-> Map n (InOutMap (Wrap e) n el1 nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el0 nl
-> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

mapEdgeWithKey :: (e n -> el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapEdgeWithKey :: (e n -> el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapEdgeWithKey e n -> el0 -> el1
f =
   Map n (InOutMap (Wrap e) n el1 nl) -> Graph e n el1 nl
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el1 nl) -> Graph e n el1 nl)
-> (Graph e n el0 nl -> Map n (InOutMap (Wrap e) n el1 nl))
-> Graph e n el0 nl
-> Graph e n el1 nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   ((Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
 -> InOutMap (Wrap e) n el1 nl)
-> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
-> Map n (InOutMap (Wrap e) n el1 nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Map (Wrap e n) el0
ins,nl
n,Map (Wrap e n) el0
outs) -> ((Wrap e n -> el0 -> el1)
-> Map (Wrap e n) el0 -> Map (Wrap e n) el1
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (e n -> el0 -> el1
f (e n -> el0 -> el1) -> (Wrap e n -> e n) -> Wrap e n -> el0 -> el1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e n -> e n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e n) el0
ins, nl
n, (Wrap e n -> el0 -> el1)
-> Map (Wrap e n) el0 -> Map (Wrap e n) el1
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (e n -> el0 -> el1
f (e n -> el0 -> el1) -> (Wrap e n -> e n) -> Wrap e n -> el0 -> el1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap e n -> e n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap) Map (Wrap e n) el0
outs)) (Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
 -> Map n (InOutMap (Wrap e) n el1 nl))
-> (Graph e n el0 nl
    -> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0))
-> Graph e n el0 nl
-> Map n (InOutMap (Wrap e) n el1 nl)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el0 nl
-> Map n (Map (Wrap e n) el0, nl, Map (Wrap e n) el0)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

nodeSet :: Graph e n el nl -> Set n
nodeSet :: Graph e n el nl -> Set n
nodeSet = Map n (InOutMap (Wrap e) n el nl) -> Set n
forall k a. Map k a -> Set k
Map.keysSet (Map n (InOutMap (Wrap e) n el nl) -> Set n)
-> (Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl))
-> Graph e n el nl
-> Set n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e n el nl -> Map n (InOutMap (Wrap e) n el nl)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap


type
   InOut e n el nl =
      ([LabeledEdge e n el], LabeledNode n nl, [LabeledEdge e n el])

mapNodeWithInOut ::
   (Edge e, Ord n) =>
   (InOut e n el nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNodeWithInOut :: (InOut e n el nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNodeWithInOut InOut e n el nl0 -> nl1
f =
   Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1)
-> (Graph e n el nl0 -> Map n (InOutMap (Wrap e) n el nl1))
-> Graph e n el nl0
-> Graph e n el nl1
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (n
 -> (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> InOutMap (Wrap e) n el nl1)
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
-> Map n (InOutMap (Wrap e) n el nl1)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey
      (\n
n (Map (Wrap e n) el
ins,nl0
nl,Map (Wrap e n) el
outs) ->
         (Map (Wrap e n) el
ins,
          InOut e n el nl0 -> nl1
f (Map (e n) el -> [(e n, el)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map (e n) el -> [(e n, el)]) -> Map (e n) el -> [(e n, el)]
forall a b. (a -> b) -> a -> b
$ Map (Wrap e n) el -> Map (e n) el
forall (e :: * -> *) n a. Map (Wrap e n) a -> Map (e n) a
unwrapMap Map (Wrap e n) el
ins, (n
n,nl0
nl), Map (e n) el -> [(e n, el)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map (e n) el -> [(e n, el)]) -> Map (e n) el -> [(e n, el)]
forall a b. (a -> b) -> a -> b
$ Map (Wrap e n) el -> Map (e n) el
forall (e :: * -> *) n a. Map (Wrap e n) a -> Map (e n) a
unwrapMap Map (Wrap e n) el
outs),
          Map (Wrap e n) el
outs)) (Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> Map n (InOutMap (Wrap e) n el nl1))
-> (Graph e n el nl0
    -> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el))
-> Graph e n el nl0
-> Map n (InOutMap (Wrap e) n el nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el nl0
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap


{- |
Same restrictions as in 'traverse'.

prop> \(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr
prop> \(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) == Graph.mapNode Char.toUpper gr
-}
traverseNode ::
   (Applicative f, Edge e, Ord n) =>
   (nl0 -> f nl1) -> Graph e n el nl0 -> f (Graph e n el nl1)
traverseNode :: (nl0 -> f nl1) -> Graph e n el nl0 -> f (Graph e n el nl1)
traverseNode nl0 -> f nl1
f =
   (Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1)
-> f (Map n (InOutMap (Wrap e) n el nl1)) -> f (Graph e n el nl1)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map n (InOutMap (Wrap e) n el nl1) -> Graph e n el nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (f (Map n (InOutMap (Wrap e) n el nl1)) -> f (Graph e n el nl1))
-> (Graph e n el nl0 -> f (Map n (InOutMap (Wrap e) n el nl1)))
-> Graph e n el nl0
-> f (Graph e n el nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   ((Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> f (InOutMap (Wrap e) n el nl1))
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
-> f (Map n (InOutMap (Wrap e) n el nl1))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse (\(Map (Wrap e n) el
ins,nl0
nl0,Map (Wrap e n) el
outs) -> (nl1 -> InOutMap (Wrap e) n el nl1)
-> f nl1 -> f (InOutMap (Wrap e) n el nl1)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\nl1
nl1 -> (Map (Wrap e n) el
ins, nl1
nl1, Map (Wrap e n) el
outs)) (f nl1 -> f (InOutMap (Wrap e) n el nl1))
-> f nl1 -> f (InOutMap (Wrap e) n el nl1)
forall a b. (a -> b) -> a -> b
$ nl0 -> f nl1
f nl0
nl0) (Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
 -> f (Map n (InOutMap (Wrap e) n el nl1)))
-> (Graph e n el nl0
    -> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el))
-> Graph e n el nl0
-> f (Map n (InOutMap (Wrap e) n el nl1))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el nl0
-> Map n (Map (Wrap e n) el, nl0, Map (Wrap e n) el)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

{- |
Same restrictions as in 'traverse'.

prop> \(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr
prop> \(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) == Graph.mapEdge (el+) gr
-}
traverseEdge ::
   (Applicative f, Edge e, Ord n) =>
   (el0 -> f el1) -> Graph e n el0 nl -> f (Graph e n el1 nl)
traverseEdge :: (el0 -> f el1) -> Graph e n el0 nl -> f (Graph e n el1 nl)
traverseEdge el0 -> f el1
f Graph e n el0 nl
gr =
   (Map (e n) el1 -> Graph e n el1 nl)
-> f (Map (e n) el1) -> f (Graph e n el1 nl)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Map n nl -> Map (e n) el1 -> Graph e n el1 nl
forall (e :: * -> *) n nl el.
(Edge e, Ord n) =>
Map n nl -> Map (e n) el -> Graph e n el nl
fromMap (Graph e n el0 nl -> Map n nl
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Graph e n el nl -> Map n nl
nodeLabels Graph e n el0 nl
gr)) (f (Map (e n) el1) -> f (Graph e n el1 nl))
-> f (Map (e n) el1) -> f (Graph e n el1 nl)
forall a b. (a -> b) -> a -> b
$ (el0 -> f el1) -> Map (e n) el0 -> f (Map (e n) el1)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse el0 -> f el1
f (Map (e n) el0 -> f (Map (e n) el1))
-> Map (e n) el0 -> f (Map (e n) el1)
forall a b. (a -> b) -> a -> b
$ Graph e n el0 nl -> Map (e n) el0
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
edgeLabels Graph e n el0 nl
gr

{- |
Don't rely on a particular order of traversal!

prop> \(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr
prop> \(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseNode nl (evalTraverseEdge el gr)
prop> \(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseEdge el (evalTraverseNode nl gr)
prop> \(TestGraph gr) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) == flip MS.evalState nl (Graph.traverse nodeAction pure gr)
prop> \(TestGraph gr) el -> flip MS.evalState el (Graph.traverseEdge edgeAction gr) == flip MS.evalState el (Graph.traverse pure edgeAction gr)
-}
traverse, _traverseNaive ::
   (Applicative f, Edge e, Ord n) =>
   (nl0 -> f nl1) ->
   (el0 -> f el1) ->
   Graph e n el0 nl0 -> f (Graph e n el1 nl1)
traverse :: (nl0 -> f nl1)
-> (el0 -> f el1) -> Graph e n el0 nl0 -> f (Graph e n el1 nl1)
traverse nl0 -> f nl1
fn el0 -> f el1
fe Graph e n el0 nl0
gr =
   (Map n nl1 -> Map (e n) el1 -> Graph e n el1 nl1)
-> f (Map n nl1) -> f (Map (e n) el1) -> f (Graph e n el1 nl1)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Map n nl1 -> Map (e n) el1 -> Graph e n el1 nl1
forall (e :: * -> *) n nl el.
(Edge e, Ord n) =>
Map n nl -> Map (e n) el -> Graph e n el nl
fromMap
      ((nl0 -> f nl1) -> Map n nl0 -> f (Map n nl1)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse nl0 -> f nl1
fn (Map n nl0 -> f (Map n nl1)) -> Map n nl0 -> f (Map n nl1)
forall a b. (a -> b) -> a -> b
$ Graph e n el0 nl0 -> Map n nl0
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Graph e n el nl -> Map n nl
nodeLabels Graph e n el0 nl0
gr)
      ((el0 -> f el1) -> Map (e n) el0 -> f (Map (e n) el1)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse el0 -> f el1
fe (Map (e n) el0 -> f (Map (e n) el1))
-> Map (e n) el0 -> f (Map (e n) el1)
forall a b. (a -> b) -> a -> b
$ Graph e n el0 nl0 -> Map (e n) el0
forall (edge :: * -> *) node edgeLabel nodeLabel.
(Edge edge, Ord node) =>
Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
edgeLabels Graph e n el0 nl0
gr)

{-
Due to the current implementation all edges are accessed twice.
That is, the actions should be commutative and non-destructive.
-}
_traverseNaive :: (nl0 -> f nl1)
-> (el0 -> f el1) -> Graph e n el0 nl0 -> f (Graph e n el1 nl1)
_traverseNaive nl0 -> f nl1
fn el0 -> f el1
fe =
   (Map n (InOutMap (Wrap e) n el1 nl1) -> Graph e n el1 nl1)
-> f (Map n (InOutMap (Wrap e) n el1 nl1)) -> f (Graph e n el1 nl1)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map n (InOutMap (Wrap e) n el1 nl1) -> Graph e n el1 nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (f (Map n (InOutMap (Wrap e) n el1 nl1)) -> f (Graph e n el1 nl1))
-> (Graph e n el0 nl0 -> f (Map n (InOutMap (Wrap e) n el1 nl1)))
-> Graph e n el0 nl0
-> f (Graph e n el1 nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   ((Map (Wrap e n) el0, nl0, Map (Wrap e n) el0)
 -> f (InOutMap (Wrap e) n el1 nl1))
-> Map n (Map (Wrap e n) el0, nl0, Map (Wrap e n) el0)
-> f (Map n (InOutMap (Wrap e) n el1 nl1))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse
      (\(Map (Wrap e n) el0
ins,nl0
n,Map (Wrap e n) el0
outs) ->
         (Map (Wrap e n) el1
 -> nl1 -> Map (Wrap e n) el1 -> InOutMap (Wrap e) n el1 nl1)
-> f (Map (Wrap e n) el1)
-> f nl1
-> f (Map (Wrap e n) el1)
-> f (InOutMap (Wrap e) n el1 nl1)
forall (f :: * -> *) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 (,,) ((el0 -> f el1) -> Map (Wrap e n) el0 -> f (Map (Wrap e n) el1)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse el0 -> f el1
fe Map (Wrap e n) el0
ins) (nl0 -> f nl1
fn nl0
n) ((el0 -> f el1) -> Map (Wrap e n) el0 -> f (Map (Wrap e n) el1)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
Trav.traverse el0 -> f el1
fe Map (Wrap e n) el0
outs)) (Map n (Map (Wrap e n) el0, nl0, Map (Wrap e n) el0)
 -> f (Map n (InOutMap (Wrap e) n el1 nl1)))
-> (Graph e n el0 nl0
    -> Map n (Map (Wrap e n) el0, nl0, Map (Wrap e n) el0))
-> Graph e n el0 nl0
-> f (Map n (InOutMap (Wrap e) n el1 nl1))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   Graph e n el0 nl0
-> Map n (Map (Wrap e n) el0, nl0, Map (Wrap e n) el0)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap


isLoop :: (Edge edge, Eq node) => edge node -> Bool
isLoop :: edge node -> Bool
isLoop edge node
e = edge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
from edge node
e node -> node -> Bool
forall a. Eq a => a -> a -> Bool
== edge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
to edge node
e

pathExists ::
   (Edge edge, Ord node) =>
   node -> node -> Graph edge node edgeLabel nodeLabel -> Bool
pathExists :: node -> node -> Graph edge node edgeLabel nodeLabel -> Bool
pathExists node
src node
dst =
   let go :: Graph e node el nl -> node -> Bool
go Graph e node el nl
gr node
a =
          Bool -> Bool
not (Graph e node el nl -> Bool
forall (e :: * -> *) n el nl. Graph e n el nl -> Bool
isEmpty Graph e node el nl
gr) Bool -> Bool -> Bool
&&
          (node
anode -> node -> Bool
forall a. Eq a => a -> a -> Bool
==node
dst Bool -> Bool -> Bool
|| ((node -> Bool) -> [node] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Graph e node el nl -> node -> Bool
go (node -> Graph e node el nl -> Graph e node el nl
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
n -> Graph e n el nl -> Graph e n el nl
deleteNode node
a Graph e node el nl
gr)) ([node] -> Bool) -> [node] -> Bool
forall a b. (a -> b) -> a -> b
$ Graph e node el nl -> node -> [node]
forall (e :: * -> *) n el nl.
(Edge e, Ord n) =>
Graph e n el nl -> n -> [n]
successors Graph e node el nl
gr node
a))
   in  (Graph edge node edgeLabel nodeLabel -> node -> Bool)
-> node -> Graph edge node edgeLabel nodeLabel -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip Graph edge node edgeLabel nodeLabel -> node -> Bool
forall (e :: * -> *) el nl.
Edge e =>
Graph e node el nl -> node -> Bool
go node
src


-- * Wrap utilities

type Wrap = IdentityT

wrap :: f a -> Wrap f a
wrap :: f a -> Wrap f a
wrap = f a -> Wrap f a
forall k (f :: k -> *) (a :: k). f a -> IdentityT f a
IdentityT

unwrap :: Wrap f a -> f a
unwrap :: Wrap f a -> f a
unwrap = Wrap f a -> f a
forall k (f :: k -> *) (a :: k). IdentityT f a -> f a
runIdentityT

unwrapMap :: Map (Wrap e n) a -> Map (e n) a
unwrapMap :: Map (Wrap e n) a -> Map (e n) a
unwrapMap = (Wrap e n -> e n) -> Map (Wrap e n) a -> Map (e n) a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysMonotonic Wrap e n -> e n
forall (f :: * -> *) a. Wrap f a -> f a
unwrap

wrapMap :: Map (e n) a -> Map (Wrap e n) a
wrapMap :: Map (e n) a -> Map (Wrap e n) a
wrapMap = (e n -> Wrap e n) -> Map (e n) a -> Map (Wrap e n) a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysMonotonic e n -> Wrap e n
forall (f :: * -> *) a. f a -> Wrap f a
wrap

unwrapSet :: Set (Wrap f a) -> Set (f a)
unwrapSet :: Set (Wrap f a) -> Set (f a)
unwrapSet = (Wrap f a -> f a) -> Set (Wrap f a) -> Set (f a)
forall a b. (a -> b) -> Set a -> Set b
Set.mapMonotonic Wrap f a -> f a
forall (f :: * -> *) a. Wrap f a -> f a
unwrap


type InOutMap e n el nl = (Map (e n) el, nl, Map (e n) el)

unwrapInOut :: InOutMap (Wrap e) n el nl -> InOutMap e n el nl
unwrapInOut :: InOutMap (Wrap e) n el nl -> InOutMap e n el nl
unwrapInOut = (Map (Wrap e n) el -> Map (e n) el)
-> (Map (Wrap e n) el, nl, Map (e n) el) -> InOutMap e n el nl
forall a d b c. (a -> d) -> (a, b, c) -> (d, b, c)
mapFst3 Map (Wrap e n) el -> Map (e n) el
forall (e :: * -> *) n a. Map (Wrap e n) a -> Map (e n) a
unwrapMap ((Map (Wrap e n) el, nl, Map (e n) el) -> InOutMap e n el nl)
-> (InOutMap (Wrap e) n el nl
    -> (Map (Wrap e n) el, nl, Map (e n) el))
-> InOutMap (Wrap e) n el nl
-> InOutMap e n el nl
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map (Wrap e n) el -> Map (e n) el)
-> InOutMap (Wrap e) n el nl
-> (Map (Wrap e n) el, nl, Map (e n) el)
forall c d a b. (c -> d) -> (a, b, c) -> (a, b, d)
mapThd3 Map (Wrap e n) el -> Map (e n) el
forall (e :: * -> *) n a. Map (Wrap e n) a -> Map (e n) a
unwrapMap

withWrappedGraph ::
   (Map n0 (InOutMap (Wrap e0) n0 el0 nl0) ->
    Map n1 (InOutMap (Wrap e1) n1 el1 nl1)) ->
   Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph :: (Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0 -> Graph e1 n1 el1 nl1
withWrappedGraph Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
-> Map n1 (InOutMap (Wrap e1) n1 el1 nl1)
f =
   Map n1 (InOutMap (Wrap e1) n1 el1 nl1) -> Graph e1 n1 el1 nl1
forall (edge :: * -> *) node edgeLabel nodeLabel.
Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
-> Graph edge node edgeLabel nodeLabel
Graph (Map n1 (InOutMap (Wrap e1) n1 el1 nl1) -> Graph e1 n1 el1 nl1)
-> (Graph e0 n0 el0 nl0 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> Graph e0 n0 el0 nl0
-> Graph e1 n1 el1 nl1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
-> Map n1 (InOutMap (Wrap e1) n1 el1 nl1)
f (Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
 -> Map n1 (InOutMap (Wrap e1) n1 el1 nl1))
-> (Graph e0 n0 el0 nl0 -> Map n0 (InOutMap (Wrap e0) n0 el0 nl0))
-> Graph e0 n0 el0 nl0
-> Map n1 (InOutMap (Wrap e1) n1 el1 nl1)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph e0 n0 el0 nl0 -> Map n0 (InOutMap (Wrap e0) n0 el0 nl0)
forall (edge :: * -> *) node edgeLabel nodeLabel.
Graph edge node edgeLabel nodeLabel
-> Map node (InOutMap (Wrap edge) node edgeLabel nodeLabel)
graphMapWrap

fromWrap :: (Edge edge) => Wrap edge node -> node
fromWrap :: Wrap edge node -> node
fromWrap = edge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
from (edge node -> node)
-> (Wrap edge node -> edge node) -> Wrap edge node -> node
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap edge node -> edge node
forall (f :: * -> *) a. Wrap f a -> f a
unwrap

toWrap :: (Edge edge) => Wrap edge node -> node
toWrap :: Wrap edge node -> node
toWrap   = edge node -> node
forall (edge :: * -> *) node. Edge edge => edge node -> node
to   (edge node -> node)
-> (Wrap edge node -> edge node) -> Wrap edge node -> node
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wrap edge node -> edge node
forall (f :: * -> *) a. Wrap f a -> f a
unwrap