{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Data.DiGraph
( DiGraph
, DiEdge
, adjacencySets
, vertices
, edges
, adjacents
, incidents
, insertEdge
, fromEdges
, insertVertex
, mapVertices
, union
, transpose
, symmetric
, fromList
, unsafeFromList
, isDiGraph
, isAdjacent
, isRegular
, isSymmetric
, isIrreflexive
, isEdge
, isVertex
, order
, size
, diSize
, symSize
, outDegree
, inDegree
, maxOutDegree
, maxInDegree
, minOutDegree
, minInDegree
, ShortestPathCache
, shortestPathCache
, shortestPath
, shortestPath_
, distance
, distance_
, diameter
, diameter_
, emptyGraph
, singleton
, clique
, pair
, triangle
, cycle
, diCycle
, line
, diLine
, petersonGraph
, twentyChainGraph
, hoffmanSingleton
) where
import Control.Arrow
import Control.DeepSeq
import Control.Monad
import Data.Foldable
import Data.Hashable (Hashable)
import qualified Data.HashMap.Strict as HM
import qualified Data.HashSet as HS
import qualified Data.List as L
import Data.Maybe
import Data.Semigroup
import Data.Traversable
import Data.Tuple
import GHC.Generics
import Numeric.Natural
import Prelude hiding (cycle)
import qualified Data.DiGraph.FloydWarshall as FW
int :: Integral a => Num b => a -> b
int :: a -> b
int = a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral
{-# INLINE int #-}
type DiEdge a = (a, a)
newtype DiGraph a = DiGraph { DiGraph a -> HashMap a (HashSet a)
unGraph :: HM.HashMap a (HS.HashSet a) }
deriving (Int -> DiGraph a -> ShowS
[DiGraph a] -> ShowS
DiGraph a -> String
(Int -> DiGraph a -> ShowS)
-> (DiGraph a -> String)
-> ([DiGraph a] -> ShowS)
-> Show (DiGraph a)
forall a. Show a => Int -> DiGraph a -> ShowS
forall a. Show a => [DiGraph a] -> ShowS
forall a. Show a => DiGraph a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DiGraph a] -> ShowS
$cshowList :: forall a. Show a => [DiGraph a] -> ShowS
show :: DiGraph a -> String
$cshow :: forall a. Show a => DiGraph a -> String
showsPrec :: Int -> DiGraph a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> DiGraph a -> ShowS
Show, DiGraph a -> DiGraph a -> Bool
(DiGraph a -> DiGraph a -> Bool)
-> (DiGraph a -> DiGraph a -> Bool) -> Eq (DiGraph a)
forall a. Eq a => DiGraph a -> DiGraph a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: DiGraph a -> DiGraph a -> Bool
$c/= :: forall a. Eq a => DiGraph a -> DiGraph a -> Bool
== :: DiGraph a -> DiGraph a -> Bool
$c== :: forall a. Eq a => DiGraph a -> DiGraph a -> Bool
Eq, Eq (DiGraph a)
Eq (DiGraph a)
-> (DiGraph a -> DiGraph a -> Ordering)
-> (DiGraph a -> DiGraph a -> Bool)
-> (DiGraph a -> DiGraph a -> Bool)
-> (DiGraph a -> DiGraph a -> Bool)
-> (DiGraph a -> DiGraph a -> Bool)
-> (DiGraph a -> DiGraph a -> DiGraph a)
-> (DiGraph a -> DiGraph a -> DiGraph a)
-> Ord (DiGraph a)
DiGraph a -> DiGraph a -> Bool
DiGraph a -> DiGraph a -> Ordering
DiGraph a -> DiGraph a -> DiGraph a
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 a. Ord a => Eq (DiGraph a)
forall a. Ord a => DiGraph a -> DiGraph a -> Bool
forall a. Ord a => DiGraph a -> DiGraph a -> Ordering
forall a. Ord a => DiGraph a -> DiGraph a -> DiGraph a
min :: DiGraph a -> DiGraph a -> DiGraph a
$cmin :: forall a. Ord a => DiGraph a -> DiGraph a -> DiGraph a
max :: DiGraph a -> DiGraph a -> DiGraph a
$cmax :: forall a. Ord a => DiGraph a -> DiGraph a -> DiGraph a
>= :: DiGraph a -> DiGraph a -> Bool
$c>= :: forall a. Ord a => DiGraph a -> DiGraph a -> Bool
> :: DiGraph a -> DiGraph a -> Bool
$c> :: forall a. Ord a => DiGraph a -> DiGraph a -> Bool
<= :: DiGraph a -> DiGraph a -> Bool
$c<= :: forall a. Ord a => DiGraph a -> DiGraph a -> Bool
< :: DiGraph a -> DiGraph a -> Bool
$c< :: forall a. Ord a => DiGraph a -> DiGraph a -> Bool
compare :: DiGraph a -> DiGraph a -> Ordering
$ccompare :: forall a. Ord a => DiGraph a -> DiGraph a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (DiGraph a)
Ord, (forall x. DiGraph a -> Rep (DiGraph a) x)
-> (forall x. Rep (DiGraph a) x -> DiGraph a)
-> Generic (DiGraph a)
forall x. Rep (DiGraph a) x -> DiGraph a
forall x. DiGraph a -> Rep (DiGraph a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (DiGraph a) x -> DiGraph a
forall a x. DiGraph a -> Rep (DiGraph a) x
$cto :: forall a x. Rep (DiGraph a) x -> DiGraph a
$cfrom :: forall a x. DiGraph a -> Rep (DiGraph a) x
Generic)
deriving anyclass (DiGraph a -> ()
(DiGraph a -> ()) -> NFData (DiGraph a)
forall a. NFData a => DiGraph a -> ()
forall a. (a -> ()) -> NFData a
rnf :: DiGraph a -> ()
$crnf :: forall a. NFData a => DiGraph a -> ()
NFData, Int -> DiGraph a -> Int
DiGraph a -> Int
(Int -> DiGraph a -> Int)
-> (DiGraph a -> Int) -> Hashable (DiGraph a)
forall a. Hashable a => Int -> DiGraph a -> Int
forall a. Hashable a => DiGraph a -> Int
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: DiGraph a -> Int
$chash :: forall a. Hashable a => DiGraph a -> Int
hashWithSalt :: Int -> DiGraph a -> Int
$chashWithSalt :: forall a. Hashable a => Int -> DiGraph a -> Int
Hashable)
instance (Hashable a, Eq a) => Semigroup (DiGraph a) where
(DiGraph HashMap a (HashSet a)
a) <> :: DiGraph a -> DiGraph a -> DiGraph a
<> (DiGraph HashMap a (HashSet a)
b) = HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph ((HashSet a -> HashSet a -> HashSet a)
-> HashMap a (HashSet a)
-> HashMap a (HashSet a)
-> HashMap a (HashSet a)
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
HM.unionWith HashSet a -> HashSet a -> HashSet a
forall a. Semigroup a => a -> a -> a
(<>) HashMap a (HashSet a)
a HashMap a (HashSet a)
b)
{-# INLINE (<>) #-}
instance (Hashable a, Eq a) => Monoid (DiGraph a) where
mempty :: DiGraph a
mempty = HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph HashMap a (HashSet a)
forall a. Monoid a => a
mempty
mappend :: DiGraph a -> DiGraph a -> DiGraph a
mappend = DiGraph a -> DiGraph a -> DiGraph a
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE mempty #-}
{-# INLINE mappend #-}
isDiGraph :: Eq a => Hashable a => DiGraph a -> Bool
isDiGraph :: DiGraph a -> Bool
isDiGraph g :: DiGraph a
g@(DiGraph HashMap a (HashSet a)
m) = HashSet a -> Bool
forall a. HashSet a -> Bool
HS.null ([HashSet a] -> HashSet a
forall a. (Eq a, Hashable a) => [HashSet a] -> HashSet a
HS.unions (HashMap a (HashSet a) -> [HashSet a]
forall k v. HashMap k v -> [v]
HM.elems HashMap a (HashSet a)
m) HashSet a -> HashSet a -> HashSet a
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
`HS.difference` DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices DiGraph a
g)
{-# INLINE isDiGraph #-}
adjacencySets :: DiGraph a -> HM.HashMap a (HS.HashSet a)
adjacencySets :: DiGraph a -> HashMap a (HashSet a)
adjacencySets = DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE adjacencySets #-}
vertices :: DiGraph a -> HS.HashSet a
vertices :: DiGraph a -> HashSet a
vertices = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HS.fromMap (HashMap a () -> HashSet a)
-> (DiGraph a -> HashMap a ()) -> DiGraph a -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashSet a -> ()) -> HashMap a (HashSet a) -> HashMap a ()
forall v1 v2 k. (v1 -> v2) -> HashMap k v1 -> HashMap k v2
HM.map (() -> HashSet a -> ()
forall a b. a -> b -> a
const ()) (HashMap a (HashSet a) -> HashMap a ())
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> HashMap a ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE vertices #-}
edges :: Eq a => Hashable a => DiGraph a -> HS.HashSet (DiEdge a)
edges :: DiGraph a -> HashSet (DiEdge a)
edges = [DiEdge a] -> HashSet (DiEdge a)
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([DiEdge a] -> HashSet (DiEdge a))
-> (DiGraph a -> [DiEdge a]) -> DiGraph a -> HashSet (DiEdge a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, HashSet a) -> [DiEdge a]) -> [(a, HashSet a)] -> [DiEdge a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap ((HashSet a -> [a]) -> (a, HashSet a) -> [DiEdge a]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse HashSet a -> [a]
forall a. HashSet a -> [a]
HS.toList) ([(a, HashSet a)] -> [DiEdge a])
-> (DiGraph a -> [(a, HashSet a)]) -> DiGraph a -> [DiEdge a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a (HashSet a) -> [(a, HashSet a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList (HashMap a (HashSet a) -> [(a, HashSet a)])
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> [(a, HashSet a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE edges #-}
adjacents :: Eq a => Hashable a => a -> DiGraph a -> HS.HashSet a
adjacents :: a -> DiGraph a -> HashSet a
adjacents a
a (DiGraph HashMap a (HashSet a)
g) = HashMap a (HashSet a)
g HashMap a (HashSet a) -> a -> HashSet a
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
a
{-# INLINE adjacents #-}
incidents :: Eq a => Hashable a => a -> DiGraph a -> [(a, a)]
incidents :: a -> DiGraph a -> [(a, a)]
incidents a
a DiGraph a
g = [ (a
a, a
b) | a
b <- HashSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (a -> DiGraph a -> HashSet a
forall a. (Eq a, Hashable a) => a -> DiGraph a -> HashSet a
adjacents a
a DiGraph a
g) ]
{-# INLINE incidents #-}
fromList :: Eq a => Hashable a => [(a,[a])] -> DiGraph a
fromList :: [(a, [a])] -> DiGraph a
fromList [(a, [a])]
l = (a -> DiGraph a -> DiGraph a) -> DiGraph a -> [a] -> DiGraph a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => a -> DiGraph a -> DiGraph a
insertVertex DiGraph a
es ((a, [a]) -> a
forall a b. (a, b) -> a
fst ((a, [a]) -> a) -> [(a, [a])] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [(a, [a])]
l)
where
es :: DiGraph a
es = [(a, a)] -> DiGraph a
forall a (f :: * -> *).
(Eq a, Hashable a, Foldable f) =>
f (a, a) -> DiGraph a
fromEdges [ (a
a,a
b) | (a
a, [a]
bs) <- [(a, [a])]
l, a
b <- [a]
bs ]
{-# INLINE fromList #-}
unsafeFromList :: Eq a => Hashable a => [(a,[a])] -> DiGraph a
unsafeFromList :: [(a, [a])] -> DiGraph a
unsafeFromList = HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph (HashMap a (HashSet a) -> DiGraph a)
-> ([(a, [a])] -> HashMap a (HashSet a)) -> [(a, [a])] -> DiGraph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> HashSet a) -> HashMap a [a] -> HashMap a (HashSet a)
forall v1 v2 k. (v1 -> v2) -> HashMap k v1 -> HashMap k v2
HM.map [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList (HashMap a [a] -> HashMap a (HashSet a))
-> ([(a, [a])] -> HashMap a [a])
-> [(a, [a])]
-> HashMap a (HashSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, [a])] -> HashMap a [a]
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HM.fromList
{-# INLINE unsafeFromList #-}
fromEdges :: Eq a => Hashable a => Foldable f => f (a, a) -> DiGraph a
fromEdges :: f (a, a) -> DiGraph a
fromEdges = ((a, a) -> DiGraph a -> DiGraph a)
-> DiGraph a -> f (a, a) -> DiGraph a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (a, a) -> DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiEdge a -> DiGraph a -> DiGraph a
insertEdge DiGraph a
forall a. Monoid a => a
mempty
{-# INLINE fromEdges #-}
union :: Eq a => Hashable a => DiGraph a -> DiGraph a -> DiGraph a
union :: DiGraph a -> DiGraph a -> DiGraph a
union = DiGraph a -> DiGraph a -> DiGraph a
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE union #-}
mapVertices :: Eq b => Hashable b => (a -> b) -> DiGraph a -> DiGraph b
mapVertices :: (a -> b) -> DiGraph a -> DiGraph b
mapVertices a -> b
f = HashMap b (HashSet b) -> DiGraph b
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph (HashMap b (HashSet b) -> DiGraph b)
-> (DiGraph a -> HashMap b (HashSet b)) -> DiGraph a -> DiGraph b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, HashSet b)] -> HashMap b (HashSet b)
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HM.fromList ([(b, HashSet b)] -> HashMap b (HashSet b))
-> (DiGraph a -> [(b, HashSet b)])
-> DiGraph a
-> HashMap b (HashSet b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, HashSet a) -> (b, HashSet b))
-> [(a, HashSet a)] -> [(b, HashSet b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a -> b
f (a -> b)
-> (HashSet a -> HashSet b) -> (a, HashSet a) -> (b, HashSet b)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** (a -> b) -> HashSet a -> HashSet b
forall b a.
(Hashable b, Eq b) =>
(a -> b) -> HashSet a -> HashSet b
HS.map a -> b
f) ([(a, HashSet a)] -> [(b, HashSet b)])
-> (DiGraph a -> [(a, HashSet a)]) -> DiGraph a -> [(b, HashSet b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a (HashSet a) -> [(a, HashSet a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList (HashMap a (HashSet a) -> [(a, HashSet a)])
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> [(a, HashSet a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE mapVertices #-}
transpose :: Eq a => Hashable a => DiGraph a -> DiGraph a
transpose :: DiGraph a -> DiGraph a
transpose DiGraph a
g = (HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph (HashMap a (HashSet a) -> DiGraph a)
-> HashMap a (HashSet a) -> DiGraph a
forall a b. (a -> b) -> a -> b
$ HashSet a
forall a. Monoid a => a
mempty HashSet a -> HashMap a (HashSet a) -> HashMap a (HashSet a)
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph DiGraph a
g)
DiGraph a -> DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a -> DiGraph a
`union` (HashSet (a, a) -> DiGraph a
forall a (f :: * -> *).
(Eq a, Hashable a, Foldable f) =>
f (a, a) -> DiGraph a
fromEdges (HashSet (a, a) -> DiGraph a)
-> (HashSet (a, a) -> HashSet (a, a))
-> HashSet (a, a)
-> DiGraph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, a) -> (a, a)) -> HashSet (a, a) -> HashSet (a, a)
forall b a.
(Hashable b, Eq b) =>
(a -> b) -> HashSet a -> HashSet b
HS.map (a, a) -> (a, a)
forall a b. (a, b) -> (b, a)
swap (HashSet (a, a) -> DiGraph a) -> HashSet (a, a) -> DiGraph a
forall a b. (a -> b) -> a -> b
$ DiGraph a -> HashSet (a, a)
forall a. (Eq a, Hashable a) => DiGraph a -> HashSet (DiEdge a)
edges DiGraph a
g)
symmetric :: Eq a => Hashable a => DiGraph a -> DiGraph a
symmetric :: DiGraph a -> DiGraph a
symmetric DiGraph a
g = DiGraph a
g DiGraph a -> DiGraph a -> DiGraph a
forall a. Semigroup a => a -> a -> a
<> DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
transpose DiGraph a
g
{-# INLINE symmetric #-}
insertEdge :: Eq a => Hashable a => DiEdge a -> DiGraph a -> DiGraph a
insertEdge :: DiEdge a -> DiGraph a -> DiGraph a
insertEdge (a
a,a
b) = HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph
(HashMap a (HashSet a) -> DiGraph a)
-> (DiGraph a -> HashMap a (HashSet a)) -> DiGraph a -> DiGraph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashSet a -> HashSet a -> HashSet a)
-> a -> HashSet a -> HashMap a (HashSet a) -> HashMap a (HashSet a)
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
HM.insertWith HashSet a -> HashSet a -> HashSet a
forall a. Semigroup a => a -> a -> a
(<>) a
a [a
Item (HashSet a)
b]
(HashMap a (HashSet a) -> HashMap a (HashSet a))
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> HashMap a (HashSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashSet a -> HashSet a -> HashSet a)
-> a -> HashSet a -> HashMap a (HashSet a) -> HashMap a (HashSet a)
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
HM.insertWith HashSet a -> HashSet a -> HashSet a
forall a. Semigroup a => a -> a -> a
(<>) a
b []
(HashMap a (HashSet a) -> HashMap a (HashSet a))
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> HashMap a (HashSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE insertEdge #-}
insertVertex :: Eq a => Hashable a => a -> DiGraph a -> DiGraph a
insertVertex :: a -> DiGraph a -> DiGraph a
insertVertex a
a = HashMap a (HashSet a) -> DiGraph a
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph (HashMap a (HashSet a) -> DiGraph a)
-> (DiGraph a -> HashMap a (HashSet a)) -> DiGraph a -> DiGraph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashSet a -> HashSet a -> HashSet a)
-> a -> HashSet a -> HashMap a (HashSet a) -> HashMap a (HashSet a)
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
HM.insertWith HashSet a -> HashSet a -> HashSet a
forall a. Semigroup a => a -> a -> a
(<>) a
a [] (HashMap a (HashSet a) -> HashMap a (HashSet a))
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> HashMap a (HashSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE insertVertex #-}
order :: DiGraph a -> Natural
order :: DiGraph a -> Natural
order = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
int (Int -> Natural) -> (DiGraph a -> Int) -> DiGraph a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> Int
forall a. HashSet a -> Int
HS.size (HashSet a -> Int) -> (DiGraph a -> HashSet a) -> DiGraph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices
{-# INLINE order #-}
diSize :: Eq a => Hashable a => DiGraph a -> Natural
diSize :: DiGraph a -> Natural
diSize = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
int (Int -> Natural) -> (DiGraph a -> Int) -> DiGraph a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet (DiEdge a) -> Int
forall a. HashSet a -> Int
HS.size (HashSet (DiEdge a) -> Int)
-> (DiGraph a -> HashSet (DiEdge a)) -> DiGraph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashSet (DiEdge a)
forall a. (Eq a, Hashable a) => DiGraph a -> HashSet (DiEdge a)
edges
{-# INLINE diSize #-}
size :: Eq a => Hashable a => DiGraph a -> Natural
size :: DiGraph a -> Natural
size = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
int (Int -> Natural) -> (DiGraph a -> Int) -> DiGraph a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet (DiEdge a) -> Int
forall a. HashSet a -> Int
HS.size (HashSet (DiEdge a) -> Int)
-> (DiGraph a -> HashSet (DiEdge a)) -> DiGraph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashSet (DiEdge a)
forall a. (Eq a, Hashable a) => DiGraph a -> HashSet (DiEdge a)
edges
{-# INLINE size #-}
symSize :: Eq a => Hashable a => DiGraph a -> Natural
symSize :: DiGraph a -> Natural
symSize DiGraph a
g = DiGraph a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> Natural
diSize (DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
symmetric DiGraph a
g) Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`div` Natural
2
{-# INLINE symSize #-}
outDegree :: Eq a => Hashable a => DiGraph a -> a -> Natural
outDegree :: DiGraph a -> a -> Natural
outDegree (DiGraph HashMap a (HashSet a)
g) a
a = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
int (Int -> Natural) -> (HashSet a -> Int) -> HashSet a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> Int
forall a. HashSet a -> Int
HS.size (HashSet a -> Natural) -> HashSet a -> Natural
forall a b. (a -> b) -> a -> b
$ HashMap a (HashSet a)
g HashMap a (HashSet a) -> a -> HashSet a
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
a
{-# INLINE outDegree #-}
maxOutDegree :: Eq a => Hashable a => DiGraph a -> Natural
maxOutDegree :: DiGraph a -> Natural
maxOutDegree DiGraph a
g = HashSet Natural -> Natural
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (HashSet Natural -> Natural) -> HashSet Natural -> Natural
forall a b. (a -> b) -> a -> b
$ (a -> Natural) -> HashSet a -> HashSet Natural
forall b a.
(Hashable b, Eq b) =>
(a -> b) -> HashSet a -> HashSet b
HS.map (DiGraph a -> a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> a -> Natural
outDegree DiGraph a
g) (DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices DiGraph a
g)
{-# INLINE maxOutDegree #-}
minOutDegree :: Eq a => Hashable a => DiGraph a -> Natural
minOutDegree :: DiGraph a -> Natural
minOutDegree DiGraph a
g = HashSet Natural -> Natural
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum (HashSet Natural -> Natural) -> HashSet Natural -> Natural
forall a b. (a -> b) -> a -> b
$ (a -> Natural) -> HashSet a -> HashSet Natural
forall b a.
(Hashable b, Eq b) =>
(a -> b) -> HashSet a -> HashSet b
HS.map (DiGraph a -> a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> a -> Natural
outDegree DiGraph a
g) (DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices DiGraph a
g)
{-# INLINE minOutDegree #-}
inDegree :: Eq a => Hashable a => DiGraph a -> a -> Natural
inDegree :: DiGraph a -> a -> Natural
inDegree DiGraph a
g = DiGraph a -> a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> a -> Natural
outDegree (DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
transpose DiGraph a
g)
{-# INLINE inDegree #-}
maxInDegree :: Eq a => Hashable a => DiGraph a -> Natural
maxInDegree :: DiGraph a -> Natural
maxInDegree = DiGraph a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> Natural
maxOutDegree (DiGraph a -> Natural)
-> (DiGraph a -> DiGraph a) -> DiGraph a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
transpose
{-# INLINE maxInDegree #-}
minInDegree :: Eq a => Hashable a => DiGraph a -> Natural
minInDegree :: DiGraph a -> Natural
minInDegree = DiGraph a -> Natural
forall a. (Eq a, Hashable a) => DiGraph a -> Natural
minOutDegree (DiGraph a -> Natural)
-> (DiGraph a -> DiGraph a) -> DiGraph a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> DiGraph a
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
transpose
{-# INLINE minInDegree #-}
isRegular :: DiGraph a -> Bool
isRegular :: DiGraph a -> Bool
isRegular = (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1)
(Int -> Bool) -> (DiGraph a -> Int) -> DiGraph a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Int]] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length
([[Int]] -> Int) -> (DiGraph a -> [[Int]]) -> DiGraph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> [[Int]]
forall a. Eq a => [a] -> [[a]]
L.group
([Int] -> [[Int]]) -> (DiGraph a -> [Int]) -> DiGraph a -> [[Int]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, HashSet a) -> Int) -> [(a, HashSet a)] -> [Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (HashSet a -> Int
forall a. HashSet a -> Int
HS.size (HashSet a -> Int)
-> ((a, HashSet a) -> HashSet a) -> (a, HashSet a) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, HashSet a) -> HashSet a
forall a b. (a, b) -> b
snd)
([(a, HashSet a)] -> [Int])
-> (DiGraph a -> [(a, HashSet a)]) -> DiGraph a -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a (HashSet a) -> [(a, HashSet a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList
(HashMap a (HashSet a) -> [(a, HashSet a)])
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> [(a, HashSet a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE isRegular #-}
isSymmetric :: Hashable a => Eq a => DiGraph a -> Bool
isSymmetric :: DiGraph a -> Bool
isSymmetric DiGraph a
g = ((a, HashSet a) -> Bool) -> [(a, HashSet a)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a, HashSet a) -> Bool
forall (t :: * -> *). Foldable t => (a, t a) -> Bool
checkVertex ([(a, HashSet a)] -> Bool) -> [(a, HashSet a)] -> Bool
forall a b. (a -> b) -> a -> b
$ HashMap a (HashSet a) -> [(a, HashSet a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList (HashMap a (HashSet a) -> [(a, HashSet a)])
-> HashMap a (HashSet a) -> [(a, HashSet a)]
forall a b. (a -> b) -> a -> b
$ DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph DiGraph a
g
where
checkVertex :: (a, t a) -> Bool
checkVertex (a
a, t a
e) = (a -> Bool) -> t a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\a
x -> a -> a -> DiGraph a -> Bool
forall a. (Eq a, Hashable a) => a -> a -> DiGraph a -> Bool
isAdjacent a
x a
a DiGraph a
g) t a
e
{-# INLINE isSymmetric #-}
isIrreflexive :: Eq a => Hashable a => DiGraph a -> Bool
isIrreflexive :: DiGraph a -> Bool
isIrreflexive = Bool -> Bool
not (Bool -> Bool) -> (DiGraph a -> Bool) -> DiGraph a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, HashSet a) -> Bool) -> [(a, HashSet a)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((a -> HashSet a -> Bool) -> (a, HashSet a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> HashSet a -> Bool
forall a. (Eq a, Hashable a) => a -> HashSet a -> Bool
HS.member) ([(a, HashSet a)] -> Bool)
-> (DiGraph a -> [(a, HashSet a)]) -> DiGraph a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a (HashSet a) -> [(a, HashSet a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList (HashMap a (HashSet a) -> [(a, HashSet a)])
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> [(a, HashSet a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE isIrreflexive #-}
isVertex :: Eq a => Hashable a => a -> DiGraph a -> Bool
isVertex :: a -> DiGraph a -> Bool
isVertex a
a = a -> HashMap a (HashSet a) -> Bool
forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
HM.member a
a (HashMap a (HashSet a) -> Bool)
-> (DiGraph a -> HashMap a (HashSet a)) -> DiGraph a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE isVertex #-}
isEdge :: Eq a => Hashable a => DiEdge a -> DiGraph a -> Bool
isEdge :: DiEdge a -> DiGraph a -> Bool
isEdge (a
a, a
b) = Bool -> (HashSet a -> Bool) -> Maybe (HashSet a) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False (a -> HashSet a -> Bool
forall a. (Eq a, Hashable a) => a -> HashSet a -> Bool
HS.member a
b) (Maybe (HashSet a) -> Bool)
-> (DiGraph a -> Maybe (HashSet a)) -> DiGraph a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> HashMap a (HashSet a) -> Maybe (HashSet a)
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup a
a (HashMap a (HashSet a) -> Maybe (HashSet a))
-> (DiGraph a -> HashMap a (HashSet a))
-> DiGraph a
-> Maybe (HashSet a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> HashMap a (HashSet a)
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph
{-# INLINE isEdge #-}
isAdjacent :: Eq a => Hashable a => a -> a -> DiGraph a -> Bool
isAdjacent :: a -> a -> DiGraph a -> Bool
isAdjacent = ((a, a) -> DiGraph a -> Bool) -> a -> a -> DiGraph a -> Bool
forall a b c. ((a, b) -> c) -> a -> b -> c
curry (a, a) -> DiGraph a -> Bool
forall a. (Eq a, Hashable a) => DiEdge a -> DiGraph a -> Bool
isEdge
{-# INLINE isAdjacent #-}
data ShortestPathCache a = ShortestPathCache
{ ShortestPathCache a -> ShortestPathMatrix
_spcMatrix :: {-# UNPACK #-} !FW.ShortestPathMatrix
, ShortestPathCache a -> HashMap a Int
_spcIndices :: !(HM.HashMap a Int)
, ShortestPathCache a -> HashMap Int a
_spcVertices :: !(HM.HashMap Int a)
}
deriving (Int -> ShortestPathCache a -> ShowS
[ShortestPathCache a] -> ShowS
ShortestPathCache a -> String
(Int -> ShortestPathCache a -> ShowS)
-> (ShortestPathCache a -> String)
-> ([ShortestPathCache a] -> ShowS)
-> Show (ShortestPathCache a)
forall a. Show a => Int -> ShortestPathCache a -> ShowS
forall a. Show a => [ShortestPathCache a] -> ShowS
forall a. Show a => ShortestPathCache a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ShortestPathCache a] -> ShowS
$cshowList :: forall a. Show a => [ShortestPathCache a] -> ShowS
show :: ShortestPathCache a -> String
$cshow :: forall a. Show a => ShortestPathCache a -> String
showsPrec :: Int -> ShortestPathCache a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> ShortestPathCache a -> ShowS
Show, ShortestPathCache a -> ShortestPathCache a -> Bool
(ShortestPathCache a -> ShortestPathCache a -> Bool)
-> (ShortestPathCache a -> ShortestPathCache a -> Bool)
-> Eq (ShortestPathCache a)
forall a.
Eq a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c/= :: forall a.
Eq a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
== :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c== :: forall a.
Eq a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
Eq, Eq (ShortestPathCache a)
Eq (ShortestPathCache a)
-> (ShortestPathCache a -> ShortestPathCache a -> Ordering)
-> (ShortestPathCache a -> ShortestPathCache a -> Bool)
-> (ShortestPathCache a -> ShortestPathCache a -> Bool)
-> (ShortestPathCache a -> ShortestPathCache a -> Bool)
-> (ShortestPathCache a -> ShortestPathCache a -> Bool)
-> (ShortestPathCache a
-> ShortestPathCache a -> ShortestPathCache a)
-> (ShortestPathCache a
-> ShortestPathCache a -> ShortestPathCache a)
-> Ord (ShortestPathCache a)
ShortestPathCache a -> ShortestPathCache a -> Bool
ShortestPathCache a -> ShortestPathCache a -> Ordering
ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
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 a. Ord a => Eq (ShortestPathCache a)
forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Ordering
forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
min :: ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
$cmin :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
max :: ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
$cmax :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> ShortestPathCache a
>= :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c>= :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
> :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c> :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
<= :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c<= :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
< :: ShortestPathCache a -> ShortestPathCache a -> Bool
$c< :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Bool
compare :: ShortestPathCache a -> ShortestPathCache a -> Ordering
$ccompare :: forall a.
Ord a =>
ShortestPathCache a -> ShortestPathCache a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (ShortestPathCache a)
Ord, (forall x. ShortestPathCache a -> Rep (ShortestPathCache a) x)
-> (forall x. Rep (ShortestPathCache a) x -> ShortestPathCache a)
-> Generic (ShortestPathCache a)
forall x. Rep (ShortestPathCache a) x -> ShortestPathCache a
forall x. ShortestPathCache a -> Rep (ShortestPathCache a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (ShortestPathCache a) x -> ShortestPathCache a
forall a x. ShortestPathCache a -> Rep (ShortestPathCache a) x
$cto :: forall a x. Rep (ShortestPathCache a) x -> ShortestPathCache a
$cfrom :: forall a x. ShortestPathCache a -> Rep (ShortestPathCache a) x
Generic)
deriving anyclass (ShortestPathCache a -> ()
(ShortestPathCache a -> ()) -> NFData (ShortestPathCache a)
forall a. NFData a => ShortestPathCache a -> ()
forall a. (a -> ()) -> NFData a
rnf :: ShortestPathCache a -> ()
$crnf :: forall a. NFData a => ShortestPathCache a -> ()
NFData)
shortestPathCache :: Eq a => Hashable a => DiGraph a -> ShortestPathCache a
shortestPathCache :: DiGraph a -> ShortestPathCache a
shortestPathCache DiGraph a
g = ShortestPathMatrix
-> HashMap a Int -> HashMap Int a -> ShortestPathCache a
forall a.
ShortestPathMatrix
-> HashMap a Int -> HashMap Int a -> ShortestPathCache a
ShortestPathCache ShortestPathMatrix
m HashMap a Int
vmap HashMap Int a
rvmap
where
m :: ShortestPathMatrix
m = Array U Ix2 Int -> ShortestPathMatrix
forall a. (Unbox a, Real a) => Array U Ix2 a -> ShortestPathMatrix
FW.floydWarshall (Array U Ix2 Int -> ShortestPathMatrix)
-> Array U Ix2 Int -> ShortestPathMatrix
forall a b. (a -> b) -> a -> b
$ AdjacencySets -> Array U Ix2 Int
FW.fromAdjacencySets (DiGraph Int -> AdjacencySets
forall a. DiGraph a -> HashMap a (HashSet a)
unGraph DiGraph Int
ig)
ig :: DiGraph Int
ig = (a -> Int) -> DiGraph a -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices (HashMap a Int
vmap HashMap a Int -> a -> Int
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.!) DiGraph a
g
vmap :: HashMap a Int
vmap = [(a, Int)] -> HashMap a Int
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HM.fromList ([(a, Int)] -> HashMap a Int) -> [(a, Int)] -> HashMap a Int
forall a b. (a -> b) -> a -> b
$ [a] -> [Int] -> [(a, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip (HashSet a -> [a]
forall a. HashSet a -> [a]
HS.toList (HashSet a -> [a]) -> HashSet a -> [a]
forall a b. (a -> b) -> a -> b
$ DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices DiGraph a
g) [Item [Int]
0..]
rvmap :: HashMap Int a
rvmap = [(Int, a)] -> HashMap Int a
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HM.fromList ([(Int, a)] -> HashMap Int a) -> [(Int, a)] -> HashMap Int a
forall a b. (a -> b) -> a -> b
$ [Int] -> [a] -> [(Int, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Item [Int]
0..] (HashSet a -> [a]
forall a. HashSet a -> [a]
HS.toList (HashSet a -> [a]) -> HashSet a -> [a]
forall a b. (a -> b) -> a -> b
$ DiGraph a -> HashSet a
forall a. DiGraph a -> HashSet a
vertices DiGraph a
g)
diameter :: Eq a => Hashable a => DiGraph a -> Maybe Natural
diameter :: DiGraph a -> Maybe Natural
diameter = ShortestPathCache a -> Maybe Natural
forall a. ShortestPathCache a -> Maybe Natural
diameter_ (ShortestPathCache a -> Maybe Natural)
-> (DiGraph a -> ShortestPathCache a) -> DiGraph a -> Maybe Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> ShortestPathCache a
forall a. (Eq a, Hashable a) => DiGraph a -> ShortestPathCache a
shortestPathCache
{-# INLINE diameter #-}
diameter_ :: ShortestPathCache a -> Maybe Natural
diameter_ :: ShortestPathCache a -> Maybe Natural
diameter_ (ShortestPathCache ShortestPathMatrix
m HashMap a Int
_ HashMap Int a
_) = Double -> Natural
forall a b. (RealFrac a, Integral b) => a -> b
round (Double -> Natural) -> Maybe Double -> Maybe Natural
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ShortestPathMatrix -> Maybe Double
FW.diameter ShortestPathMatrix
m
{-# INLINE diameter_ #-}
shortestPath :: Eq a => Hashable a => a -> a -> DiGraph a -> Maybe [a]
shortestPath :: a -> a -> DiGraph a -> Maybe [a]
shortestPath a
src a
trg = a -> a -> ShortestPathCache a -> Maybe [a]
forall a.
(Eq a, Hashable a) =>
a -> a -> ShortestPathCache a -> Maybe [a]
shortestPath_ a
src a
trg (ShortestPathCache a -> Maybe [a])
-> (DiGraph a -> ShortestPathCache a) -> DiGraph a -> Maybe [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> ShortestPathCache a
forall a. (Eq a, Hashable a) => DiGraph a -> ShortestPathCache a
shortestPathCache
{-# INLINE shortestPath #-}
shortestPath_ :: Eq a => Hashable a => a -> a -> ShortestPathCache a -> Maybe [a]
shortestPath_ :: a -> a -> ShortestPathCache a -> Maybe [a]
shortestPath_ a
src a
trg (ShortestPathCache ShortestPathMatrix
c HashMap a Int
m HashMap Int a
r)
= (Int -> a) -> [Int] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (HashMap Int a -> Int -> a
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
(HM.!) HashMap Int a
r) ([Int] -> [a]) -> Maybe [Int] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ShortestPathMatrix -> Int -> Int -> Maybe [Int]
FW.shortestPath ShortestPathMatrix
c (HashMap a Int
m HashMap a Int -> a -> Int
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
src) (HashMap a Int
m HashMap a Int -> a -> Int
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
trg)
{-# INLINE shortestPath_ #-}
distance :: Eq a => Hashable a => a -> a -> DiGraph a -> Maybe Natural
distance :: a -> a -> DiGraph a -> Maybe Natural
distance a
src a
trg = a -> a -> ShortestPathCache a -> Maybe Natural
forall a.
(Eq a, Hashable a) =>
a -> a -> ShortestPathCache a -> Maybe Natural
distance_ a
src a
trg (ShortestPathCache a -> Maybe Natural)
-> (DiGraph a -> ShortestPathCache a) -> DiGraph a -> Maybe Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DiGraph a -> ShortestPathCache a
forall a. (Eq a, Hashable a) => DiGraph a -> ShortestPathCache a
shortestPathCache
{-# INLINE distance #-}
distance_ :: Eq a => Hashable a => a -> a -> ShortestPathCache a -> Maybe Natural
distance_ :: a -> a -> ShortestPathCache a -> Maybe Natural
distance_ a
src a
trg (ShortestPathCache ShortestPathMatrix
c HashMap a Int
m HashMap Int a
_)
= Double -> Natural
forall a b. (RealFrac a, Integral b) => a -> b
round (Double -> Natural) -> Maybe Double -> Maybe Natural
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ShortestPathMatrix -> Int -> Int -> Maybe Double
FW.distance ShortestPathMatrix
c (HashMap a Int
m HashMap a Int -> a -> Int
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
src) (HashMap a Int
m HashMap a Int -> a -> Int
forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
HM.! a
trg)
{-# INLINE distance_ #-}
emptyGraph :: Natural -> DiGraph Int
emptyGraph :: Natural -> DiGraph Int
emptyGraph Natural
n = [(Int, [Int])] -> DiGraph Int
forall a. (Eq a, Hashable a) => [(a, [a])] -> DiGraph a
unsafeFromList [ (Int
i, []) | Int
i <- [Item [Int]
0 .. Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] ]
clique :: Natural -> DiGraph Int
clique :: Natural -> DiGraph Int
clique Natural
i = [(Int, [Int])] -> DiGraph Int
forall a. (Eq a, Hashable a) => [(a, [a])] -> DiGraph a
unsafeFromList
[ (Int
a, [Int]
b)
| Int
a <- [Item [Int]
0 .. Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
, let b :: [Int]
b = [ Int
x | Int
x <- [Item [Int]
0 .. Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] , Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
a ]
]
singleton :: DiGraph Int
singleton :: DiGraph Int
singleton = Natural -> DiGraph Int
clique Natural
1
pair :: DiGraph Int
pair :: DiGraph Int
pair = Natural -> DiGraph Int
clique Natural
2
triangle :: DiGraph Int
triangle :: DiGraph Int
triangle = Natural -> DiGraph Int
clique Natural
3
diCycle :: Natural -> DiGraph Int
diCycle :: Natural -> DiGraph Int
diCycle Natural
n = [(Int, [Int])] -> DiGraph Int
forall a. (Eq a, Hashable a) => [(a, [a])] -> DiGraph a
unsafeFromList [ (Int
a, [(Int
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
n]) | Int
a <- [Item [Int]
0 .. Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] ]
cycle :: Natural -> DiGraph Int
cycle :: Natural -> DiGraph Int
cycle = DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
symmetric (DiGraph Int -> DiGraph Int)
-> (Natural -> DiGraph Int) -> Natural -> DiGraph Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> DiGraph Int
diCycle
diLine :: Natural -> DiGraph Int
diLine :: Natural -> DiGraph Int
diLine Natural
n = [(Int, [Int])] -> DiGraph Int
forall a. (Eq a, Hashable a) => [(a, [a])] -> DiGraph a
unsafeFromList [ (Int
a, [ Int
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 | Int
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]) | Int
a <- [Item [Int]
0 .. Natural -> Int
forall a b. (Integral a, Num b) => a -> b
int Natural
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] ]
line :: Natural -> DiGraph Int
line :: Natural -> DiGraph Int
line = DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a
symmetric (DiGraph Int -> DiGraph Int)
-> (Natural -> DiGraph Int) -> Natural -> DiGraph Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> DiGraph Int
diLine
petersonGraph :: DiGraph Int
petersonGraph :: DiGraph Int
petersonGraph = AdjacencySets -> DiGraph Int
forall a. HashMap a (HashSet a) -> DiGraph a
DiGraph
[ (Int
0, [Item (HashSet Int)
2,Item (HashSet Int)
3,Item (HashSet Int)
5])
, (Int
1, [Item (HashSet Int)
3,Item (HashSet Int)
4,Item (HashSet Int)
6])
, (Int
2, [Item (HashSet Int)
4,Item (HashSet Int)
0,Item (HashSet Int)
7])
, (Int
3, [Item (HashSet Int)
0,Item (HashSet Int)
1,Item (HashSet Int)
8])
, (Int
4, [Item (HashSet Int)
1,Item (HashSet Int)
2,Item (HashSet Int)
9])
, (Int
5, [Item (HashSet Int)
0,Item (HashSet Int)
6,Item (HashSet Int)
9])
, (Int
6, [Item (HashSet Int)
1,Item (HashSet Int)
5,Item (HashSet Int)
7])
, (Int
7, [Item (HashSet Int)
2,Item (HashSet Int)
6,Item (HashSet Int)
8])
, (Int
8, [Item (HashSet Int)
3,Item (HashSet Int)
7,Item (HashSet Int)
9])
, (Int
9, [Item (HashSet Int)
4,Item (HashSet Int)
8,Item (HashSet Int)
5])
]
twentyChainGraph :: DiGraph Int
twentyChainGraph :: DiGraph Int
twentyChainGraph = DiGraph Int
pentagram DiGraph Int -> DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a -> DiGraph a
`union` DiGraph Int
decagon DiGraph Int -> DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a -> DiGraph a
`union` DiGraph Int
connections
where
pentagram :: DiGraph Int
pentagram = (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
5) (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ DiGraph Int -> DiGraph Int
pentagon2pentagram (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ Natural -> DiGraph Int
cycle Natural
5
decagon :: DiGraph Int
decagon = (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
10) (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ Natural -> DiGraph Int
cycle Natural
10
connections :: DiGraph Int
connections = HashSet (Int, Int) -> DiGraph Int
forall a (f :: * -> *).
(Eq a, Hashable a, Foldable f) =>
f (a, a) -> DiGraph a
fromEdges (HashSet (Int, Int) -> DiGraph Int)
-> HashSet (Int, Int) -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> HashSet (Int, Int)
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([(Int, Int)] -> HashSet (Int, Int))
-> [(Int, Int)] -> HashSet (Int, Int)
forall a b. (a -> b) -> a -> b
$ [[(Int, Int)]] -> [(Int, Int)]
forall a. Monoid a => [a] -> a
mconcat
[ [(Int
i, Int
x), (Int
x, Int
i)]
| Int
i <- [Item [Int]
0..Item [Int]
4]
, Int
x <- [Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
5, Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
10, Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
15]
]
pentagon2pentagram :: DiGraph Int -> DiGraph Int
pentagon2pentagram = (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices ((Int -> Int) -> DiGraph Int -> DiGraph Int)
-> (Int -> Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ \case
Int
0 -> Int
0
Int
1 -> Int
3
Int
2 -> Int
1
Int
3 -> Int
4
Int
4 -> Int
2
Int
_ -> String -> Int
forall a. HasCallStack => String -> a
error String
"invalid vertex"
hoffmanSingleton :: DiGraph Int
hoffmanSingleton :: DiGraph Int
hoffmanSingleton = DiGraph Int
pentagons DiGraph Int -> DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a -> DiGraph a
`union` DiGraph Int
pentagrams DiGraph Int -> DiGraph Int -> DiGraph Int
forall a. (Eq a, Hashable a) => DiGraph a -> DiGraph a -> DiGraph a
`union` DiGraph Int
connections
where
pentagons :: DiGraph Int
pentagons = [DiGraph Int] -> DiGraph Int
forall a. Monoid a => [a] -> a
mconcat
[ (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices (Int -> Int -> Int
forall a. Num a => a -> a -> a
p_off Int
i) (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ Natural -> DiGraph Int
cycle Natural
5 | Int
i <- [Item [Int]
0 .. Item [Int]
4] ]
pentagrams :: DiGraph Int
pentagrams = [DiGraph Int] -> DiGraph Int
forall a. Monoid a => [a] -> a
mconcat
[ (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices (Int -> Int -> Int
forall a. Num a => a -> a -> a
q_off Int
i) (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ DiGraph Int -> DiGraph Int
pentagon2pentagram (DiGraph Int -> DiGraph Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ Natural -> DiGraph Int
cycle Natural
5 | Int
i <- [Item [Int]
0 .. Item [Int]
4] ]
p_off :: a -> a -> a
p_off a
h = a -> a -> a
forall a. Num a => a -> a -> a
(+) (a
25 a -> a -> a
forall a. Num a => a -> a -> a
+ a
5 a -> a -> a
forall a. Num a => a -> a -> a
* a
h)
q_off :: a -> a -> a
q_off a
i = a -> a -> a
forall a. Num a => a -> a -> a
(+) (a
5 a -> a -> a
forall a. Num a => a -> a -> a
* a
i)
pentagon2pentagram :: DiGraph Int -> DiGraph Int
pentagon2pentagram = (Int -> Int) -> DiGraph Int -> DiGraph Int
forall b a.
(Eq b, Hashable b) =>
(a -> b) -> DiGraph a -> DiGraph b
mapVertices ((Int -> Int) -> DiGraph Int -> DiGraph Int)
-> (Int -> Int) -> DiGraph Int -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ \case
Int
0 -> Int
0
Int
1 -> Int
3
Int
2 -> Int
1
Int
3 -> Int
4
Int
4 -> Int
2
Int
_ -> String -> Int
forall a. HasCallStack => String -> a
error String
"invalid vertex"
connections :: DiGraph Int
connections = HashSet (Int, Int) -> DiGraph Int
forall a (f :: * -> *).
(Eq a, Hashable a, Foldable f) =>
f (a, a) -> DiGraph a
fromEdges (HashSet (Int, Int) -> DiGraph Int)
-> HashSet (Int, Int) -> DiGraph Int
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> HashSet (Int, Int)
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HS.fromList ([(Int, Int)] -> HashSet (Int, Int))
-> [(Int, Int)] -> HashSet (Int, Int)
forall a b. (a -> b) -> a -> b
$ [[(Int, Int)]] -> [(Int, Int)]
forall a. Monoid a => [a] -> a
mconcat
[ [(Int
a, Int
b), (Int
b, Int
a)]
| Int
h <- [Item [Int]
0 .. Item [Int]
4]
, Int
j <- [Item [Int]
0 .. Item [Int]
4]
, let a :: Int
a = Int -> Int -> Int
forall a. Num a => a -> a -> a
p_off Int
h Int
j
, Int
i <- [Item [Int]
0 .. Item [Int]
4]
, let b :: Int
b = Int -> Int -> Int
forall a. Num a => a -> a -> a
q_off Int
i ((Int
h Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
5)
]