module Data.Graph.Comfort (
Graph,
LabeledNode,
LabeledEdge,
Edge(from, to), defaultEdgeFoldMap,
DirEdge(DirEdge),
UndirEdge(UndirEdge), undirEdge,
EitherEdge(EDirEdge,EUndirEdge),
empty, fromList, fromMap,
graphMap,
nodeLabels, nodeSet, nodes, nodeEdges,
edgeLabels, edgeSet, edges,
isEmpty,
lookupNode, lookupEdge,
predecessors, successors,
adjacentEdgeSet, adjacentEdges,
isLoop,
pathExists,
isConsistent,
mapNode, mapNodeWithKey,
mapEdge, mapEdgeWithKey,
mapNodeWithInOut, InOut,
filterEdgeWithKey,
traverseNode, traverseEdge, traverse,
checkedZipWith,
union,
Reverse,
reverse,
reverseEdge,
mapKeys,
mapMaybeEdgeKeys,
mapEdgeKeys,
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)
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
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
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
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
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
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
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
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
_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
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
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
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
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
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
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
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)
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
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))
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))
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
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
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
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
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
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
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
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
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)
_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
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