{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE ScopedTypeVariables #-}

-- |
-- Module: DiGraph
-- Copyright: Copyright © 2018-2020 Kadena LLC.
-- License: MIT
-- Maintainer: Lars Kuhtz <lars@kadena.io>
-- Stability: experimental
--
-- Directed graphs in adjacency set representation. The implementation is based
-- on "Data.HashMap.Strict" and "Data.HashSet" from the [unordered-containers
-- package](https://hackage.haskell.org/package/unordered-containers)
--
-- Undirected graphs are represented as symmetric, irreflexive directed graphs.
--
module Data.DiGraph
( DiGraph
, DiEdge
, adjacencySets
, vertices
, edges
, adjacents
, incidents

-- * Construction and Modification of Graphs
, insertEdge
, fromEdges
, insertVertex
, mapVertices
, union
, transpose
, symmetric
, fromList
, unsafeFromList

-- * Predicates
, isDiGraph
, isAdjacent
, isRegular
, isSymmetric
, isIrreflexive
, isEdge
, isVertex

-- * Properties
, order
, size
, diSize
, symSize
, outDegree
, inDegree
, maxOutDegree
, maxInDegree
, minOutDegree
, minInDegree

-- * Distances, Shortest Paths, and Diameter
, ShortestPathCache
, shortestPathCache
, shortestPath
, shortestPath_
, distance
, distance_
, diameter
, diameter_

-- * Graphs
, 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)

-- internal modules

import qualified Data.DiGraph.FloydWarshall as FW

-- -------------------------------------------------------------------------- --
-- Utils

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 #-}

-- -------------------------------------------------------------------------- --
-- Graph

-- | Directed Edge.
--
type DiEdge a = (a, a)

-- | Adjacency set representation of directed graphs.
--
-- It is assumed that each target of an edge is also explicitly a vertex in the
-- graph.
--
-- It is not generally required that graphs are irreflexive, but all concrete
-- graphs that are defined in this module are irreflexive.
--
-- Undirected graphs are represented as symmetric directed graphs.
--
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 #-}

-- | A predicate that asserts that every target of an edge is also a vertex in
-- the graph. Any graph that is constructed without using unsafe methods is
-- guaranteed to satisfy this predicate.
--
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 #-}

-- | The adjacency sets of a graph.
--
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 #-}

-- | The set of vertices of the graph.
--
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 #-}

-- | The set edges of the graph.
--
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 #-}

-- | The set of adjacent pairs of a graph.
--
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 #-}

-- | The set of incident edges of a graph.
--
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 #-}

-- -------------------------------------------------------------------------- --
-- Constructing and Modifying Graphs

-- | Construct a graph from adjacency lists.
--
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 #-}

-- | Unsafely construct a graph from adjacency lists.
--
-- This function assumes that the input includes a adjacency list of each vertex
-- that appears in a adjacency list of another vertex. Generally, 'fromList'
-- should be preferred.
--
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 #-}

-- | Construct a graph from a foldable structure of edges.
--
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 #-}

-- | The union of two graphs.
--
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 #-}

-- | Map a function over all vertices of a graph.
--
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 a graph, i.e. reverse all edges of the graph.
--
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 closure of a graph.
--
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 #-}

-- | Insert an edge. Returns the graph unmodified if the edge is already in the
-- graph. Non-existing vertices are added.
--
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 #-}

-- | Insert a vertex. Returns the graph unmodified if the vertex is already in
-- the graph.
--
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 #-}

-- -------------------------------------------------------------------------- --
-- Properties

-- | The order of a graph is the number of vertices.
--
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 #-}

-- | Directed Size. This the number of edges of the graph.
--
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 #-}

-- | Directed Size. This the number of edges of the graph.
--
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 #-}

-- | Undirected Size of a graph. This is the number of edges of the symmetric
-- closure of the graph.
--
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 #-}

-- | The number of outgoing edges of vertex in a graph.
--
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 #-}

-- | The maximum out-degree of the vertices of a graph.
--
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 #-}

-- | The minimum out-degree of the vertices of a graph.
--
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 #-}

-- | The number of incoming edges of vertex in a graph.
--
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 #-}

-- | The maximum in-degree of the vertices of a graph.
--
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 #-}

-- | The minimum in-degree of the vertices of a graph.
--
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 #-}

-- -------------------------------------------------------------------------- --
-- Predicates

-- | Return whether a graph is regular, i.e. whether all vertices have the same
-- out-degree. Note that the latter implies that all vertices also have the same
-- in-degree.
--
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 #-}

-- | Return whether a graph is symmetric, i.e. whether for each edge \((a,b)\)
-- there is also the edge \((b,a)\) in the graph.
--
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 #-}

-- | Return whether a graph is irreflexive. A graph is irreflexive if for each
-- edge \((a,b)\) it holds that \(a \neq b\), i.e there are no self-loops in the
-- graph.
--
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 #-}

-- | Return whether a vertex is contained in a graph.
--
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 #-}

-- | Return whether an edge is contained in a graph.
--
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 #-}

-- | Return whether two vertices are adjacent in a graph.
--
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 #-}

-- -------------------------------------------------------------------------- --
-- Distances, Shortest Paths, and Diameter

-- | The shortest path matrix of a graph.
--
-- The shortest path matrix of a graph can be used to efficiently query the
-- distance and shortest path between any two vertices of the graph. It can also
-- be used to efficiently compute the diameter of the graph.
--
-- Computing the shortest path matrix is expensive for larger graphs. The matrix
-- is computed using the Floyd-Warshall algorithm. The space and time complexity
-- is quadratic in the /order/ of the graph. For sparse graphs there are more
-- efficient algorithms for computing distances and shortest paths between the
-- nodes of the graph.
--
data ShortestPathCache a = ShortestPathCache
    { ShortestPathCache a -> ShortestPathMatrix
_spcMatrix :: {-# UNPACK #-} !FW.ShortestPathMatrix
        -- ^ The shortest path matrix of a graph.
    , ShortestPathCache a -> HashMap a Int
_spcIndices :: !(HM.HashMap a Int)
        -- ^ mapping from vertices of the graph to indices in the shortest path
        -- matrix.
    , ShortestPathCache a -> HashMap Int a
_spcVertices :: !(HM.HashMap Int a)
        -- ^ mapping from indices in the shortest path matrix to vertices in the
        -- graph.
    }
    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)

-- | Compute the shortest path matrix for a graph. The result can be used to
-- efficiently query the distance and shortest path between any two vertices of
-- the graph. It can also be used to efficiently compute the diameter of the
-- graph.
--
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)

-- | Compute the Diameter of a graph, i.e. the maximum length of a shortest path
-- between two vertices in the graph.
--
-- This is expensive to compute for larger graphs. If also the shortest paths or
-- distances are needed, one should use 'shortestPathCache' to cache the result
-- of the search and use the 'diameter_', 'shortestPath_', and 'distance_' to
-- query the respective results from the cache.
--
-- The algorithm is optimized for dense graphs. For large sparse graphs a more
-- efficient algorithm should be used.
--
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 #-}

-- | Compute the Diameter of a graph from a shortest path matrix. The diameter
-- of a graph is the maximum length of a shortest path between two vertices in
-- the graph.
--
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_ #-}

-- | Compute the shortest path between two vertices of a graph.
--
-- | This is expensive for larger graphs. If more than one path is needed one
-- should use 'shortestPathCache' to cache the result of the search and use
-- 'shortestPath_' to query paths from the cache.
--
-- The algorithm is optimized for dense graphs. For large sparse graphs a more
-- efficient algorithm should be used.
--
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 #-}

-- | Compute the shortest path between two vertices from the shortest path
-- matrix of a graph.
--
-- The algorithm is optimized for dense graphs. For large sparse graphs a more
-- efficient algorithm should be used.
--
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_ #-}

-- | Compute the distance between two vertices of a graph.
--
-- | This is expensive for larger graphs. If more than one distance is needed
-- one should use 'shortestPathCache' to cache the result of the search and use
-- 'distance_' to query paths from the cache.
--
-- The algorithm is optimized for dense graphs. For large sparse graphs a more
-- efficient algorithm should be used.
--
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 #-}

-- | Compute the distance between two vertices from the shortest path matrix of
-- a graph.
--
-- The algorithm is optimized for dense graphs. For large sparse graphs a more
-- efficient algorithm should be used.
--
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_ #-}

-- -------------------------------------------------------------------------- --
-- Concrete Graph

-- | The empty graph on @n@ nodes. This is the graph of 'order' @n@ and 'size'
-- @0@.
--
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] ]

-- | Undirected clique.
--
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 ]
    ]

-- | The (irreflexive) singleton graph.
--
singleton :: DiGraph Int
singleton :: DiGraph Int
singleton = Natural -> DiGraph Int
clique Natural
1

-- | Undirected pair.
--
pair :: DiGraph Int
pair :: DiGraph Int
pair = Natural -> DiGraph Int
clique Natural
2

-- | Undirected triangle.
--
triangle :: DiGraph Int
triangle :: DiGraph Int
triangle = Natural -> DiGraph Int
clique Natural
3

-- | Directed cycle.
--
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] ]

-- | Undirected cycle.
--
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

-- | Directed line.
--
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] ]

-- | Undirected line.
--
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

-- | The Peterson graph.
--
-- * order: 10
-- * size: 30
-- * degree: 3
-- * diameter: 2
--
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])
    ]

-- | The "twenty chain" graph.
--
-- * order: 20
-- * size: 60
-- * degree: 3
-- * diameter: 3
--
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"

-- | Hoffman-Singleton Graph.
--
-- The Hoffman-Singleton graph is a 7-regular graph with 50 vertices and 175
-- edges. It's the largest graph of max-degree 7 and diameter 2. Cf.
-- [https://en.wikipedia.org/wiki/Hoffman–Singleton_graph]()
--
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)
        ]