{-# LANGUAGE ConstrainedClassMethods #-}
-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.ToGraph
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- __Alga__ is a library for algebraic construction and manipulation of graphs
-- in Haskell. See <https://github.com/snowleopard/alga-paper this paper> for the
-- motivation behind the library, the underlying theory, and implementation details.
--
-- This module defines the type class 'ToGraph' for capturing data types that
-- can be converted to algebraic graphs. To make an instance of this class you
-- need to define just a single method ('toGraph' or 'foldg'), which gives you
-- access to many other useful methods for free (although note that the default
-- implementations may be suboptimal performance-wise).
--
-- This type class is similar to the standard type class 'Data.Foldable.Foldable'
-- defined for lists. Furthermore, one can define 'Foldable' methods 'foldMap'
-- and 'Data.Foldable.toList' using @ToGraph@.'foldg':
--
-- @
-- 'foldMap' f = 'foldg' 'mempty' f    ('<>') ('<>')
-- 'Data.Foldable.toList'    = 'foldg' []     'pure' ('++') ('++')
-- @
--
-- However, the resulting 'Foldable' instance is problematic. For example,
-- folding equivalent algebraic graphs @1@ and @1@ + @1@ leads to different
-- results:
--
-- @
-- 'Data.Foldable.toList' (1    ) == [1]
-- 'Data.Foldable.toList' (1 + 1) == [1, 1]
-- @
--
-- To avoid such cases, we do not provide 'Foldable' instances for algebraic
-- graph datatypes. Furthermore, we require that the four arguments passed to
-- 'foldg' satisfy the laws of the algebra of graphs. The above definitions
-- of 'foldMap' and 'Data.Foldable.toList' violate this requirement, for example
-- @[1] ++ [1] /= [1]@, and are therefore disallowed.
-----------------------------------------------------------------------------
module Algebra.Graph.ToGraph (
    -- * Type class
    ToGraph (..),

    -- * Derived functions
    adjacencyMap, adjacencyIntMap, adjacencyMapTranspose, adjacencyIntMapTranspose
    ) where

import Data.IntMap (IntMap)
import Data.IntSet (IntSet)
import Data.Map    (Map)
import Data.Set    (Set)
import Data.Tree

import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Map    as Map
import qualified Data.Set    as Set

-- Ideally, we would define all instances in the modules where the corresponding
-- data types are declared. However, that causes import cycles, so we define a
-- few instances here.

import qualified Algebra.Graph                           as G
import qualified Algebra.Graph.AdjacencyMap              as AM
import qualified Algebra.Graph.AdjacencyMap.Algorithm    as AM
import qualified Algebra.Graph.NonEmpty.AdjacencyMap     as NAM
import qualified Algebra.Graph.AdjacencyIntMap           as AIM
import qualified Algebra.Graph.AdjacencyIntMap.Algorithm as AIM

-- | The 'ToGraph' type class captures data types that can be converted to
-- algebraic graphs. Instances of this type class should satisfy the laws
-- specified by the default method definitions.
class ToGraph t where
    {-# MINIMAL toGraph | foldg #-}
    -- | The type of vertices of the resulting graph.
    type ToVertex t

    -- | Convert a value to the corresponding algebraic graph, see "Algebra.Graph".
    --
    -- @
    -- toGraph == 'foldg' 'G.Empty' 'G.Vertex' 'G.Overlay' 'G.Connect'
    -- @
    toGraph :: t -> G.Graph (ToVertex t)
    toGraph = Graph (ToVertex t)
-> (ToVertex t -> Graph (ToVertex t))
-> (Graph (ToVertex t) -> Graph (ToVertex t) -> Graph (ToVertex t))
-> (Graph (ToVertex t) -> Graph (ToVertex t) -> Graph (ToVertex t))
-> t
-> Graph (ToVertex t)
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Graph (ToVertex t)
forall a. Graph a
G.Empty ToVertex t -> Graph (ToVertex t)
forall a. a -> Graph a
G.Vertex Graph (ToVertex t) -> Graph (ToVertex t) -> Graph (ToVertex t)
forall a. Graph a -> Graph a -> Graph a
G.Overlay Graph (ToVertex t) -> Graph (ToVertex t) -> Graph (ToVertex t)
forall a. Graph a -> Graph a -> Graph a
G.Connect

    -- | The method 'foldg' is used for generalised graph folding. It collapses
    -- a given value by applying the provided graph construction primitives. The
    -- order of arguments is: empty, vertex, overlay and connect, and it is
    -- assumed that the arguments satisfy the axioms of the graph algebra.
    --
    -- @
    -- foldg == Algebra.Graph.'G.foldg' . 'toGraph'
    -- @
    foldg :: r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
    foldg r
e ToVertex t -> r
v r -> r -> r
o r -> r -> r
c = r
-> (ToVertex t -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph (ToVertex t)
-> r
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
G.foldg r
e ToVertex t -> r
v r -> r -> r
o r -> r -> r
c (Graph (ToVertex t) -> r) -> (t -> Graph (ToVertex t)) -> t -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> Graph (ToVertex t)
forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph

    -- | Check if a graph is empty.
    --
    -- @
    -- isEmpty == 'foldg' True ('const' False) (&&) (&&)
    -- @
    isEmpty :: t -> Bool
    isEmpty = Bool
-> (ToVertex t -> Bool)
-> (Bool -> Bool -> Bool)
-> (Bool -> Bool -> Bool)
-> t
-> Bool
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Bool
True (Bool -> ToVertex t -> Bool
forall a b. a -> b -> a
const Bool
False) Bool -> Bool -> Bool
(&&) Bool -> Bool -> Bool
(&&)

    -- | Check if a graph contains a given vertex.
    --
    -- @
    -- hasVertex x == 'foldg' False (==x) (||) (||)
    -- @
    hasVertex :: Eq (ToVertex t) => ToVertex t -> t -> Bool
    hasVertex ToVertex t
x = Bool
-> (ToVertex t -> Bool)
-> (Bool -> Bool -> Bool)
-> (Bool -> Bool -> Bool)
-> t
-> Bool
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Bool
False (ToVertex t -> ToVertex t -> Bool
forall a. Eq a => a -> a -> Bool
==ToVertex t
x) Bool -> Bool -> Bool
(||) Bool -> Bool -> Bool
(||)

    -- | Check if a graph contains a given edge.
    --
    -- @
    -- hasEdge x y == Algebra.Graph.'G.hasEdge' x y . 'toGraph'
    -- @
    hasEdge :: Eq (ToVertex t) => ToVertex t -> ToVertex t -> t -> Bool
    hasEdge ToVertex t
x ToVertex t
y = ToVertex t -> ToVertex t -> Graph (ToVertex t) -> Bool
forall a. Eq a => a -> a -> Graph a -> Bool
G.hasEdge ToVertex t
x ToVertex t
y (Graph (ToVertex t) -> Bool)
-> (t -> Graph (ToVertex t)) -> t -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> Graph (ToVertex t)
forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph

    -- | The number of vertices in a graph.
    --
    -- @
    -- vertexCount == Set.'Set.size' . 'vertexSet'
    -- @
    vertexCount :: Ord (ToVertex t) => t -> Int
    vertexCount = Set (ToVertex t) -> Int
forall a. Set a -> Int
Set.size (Set (ToVertex t) -> Int) -> (t -> Set (ToVertex t)) -> t -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> Set (ToVertex t)
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t)
vertexSet

    -- | The number of edges in a graph.
    --
    -- @
    -- edgeCount == Set.'Set.size' . 'edgeSet'
    -- @
    edgeCount :: Ord (ToVertex t) => t -> Int
    edgeCount = AdjacencyMap (ToVertex t) -> Int
forall a. AdjacencyMap a -> Int
AM.edgeCount (AdjacencyMap (ToVertex t) -> Int)
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | The sorted list of vertices of a given graph.
    --
    -- @
    -- vertexList == Set.'Set.toAscList' . 'vertexSet'
    -- @
    vertexList :: Ord (ToVertex t) => t -> [ToVertex t]
    vertexList = Set (ToVertex t) -> [ToVertex t]
forall a. Set a -> [a]
Set.toAscList (Set (ToVertex t) -> [ToVertex t])
-> (t -> Set (ToVertex t)) -> t -> [ToVertex t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> Set (ToVertex t)
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t)
vertexSet

    -- | The sorted list of edges of a graph.
    --
    -- @
    -- edgeList == Set.'Set.toAscList' . 'edgeSet'
    -- @
    edgeList :: Ord (ToVertex t) => t -> [(ToVertex t, ToVertex t)]
    edgeList = AdjacencyMap (ToVertex t) -> [(ToVertex t, ToVertex t)]
forall a. AdjacencyMap a -> [(a, a)]
AM.edgeList (AdjacencyMap (ToVertex t) -> [(ToVertex t, ToVertex t)])
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> [(ToVertex t, ToVertex t)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | The set of vertices of a graph.
    --
    -- @
    -- vertexSet == 'foldg' Set.'Set.empty' Set.'Set.singleton' Set.'Set.union' Set.'Set.union'
    -- @
    vertexSet :: Ord (ToVertex t) => t -> Set (ToVertex t)
    vertexSet = Set (ToVertex t)
-> (ToVertex t -> Set (ToVertex t))
-> (Set (ToVertex t) -> Set (ToVertex t) -> Set (ToVertex t))
-> (Set (ToVertex t) -> Set (ToVertex t) -> Set (ToVertex t))
-> t
-> Set (ToVertex t)
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Set (ToVertex t)
forall a. Set a
Set.empty ToVertex t -> Set (ToVertex t)
forall a. a -> Set a
Set.singleton Set (ToVertex t) -> Set (ToVertex t) -> Set (ToVertex t)
forall a. Ord a => Set a -> Set a -> Set a
Set.union Set (ToVertex t) -> Set (ToVertex t) -> Set (ToVertex t)
forall a. Ord a => Set a -> Set a -> Set a
Set.union

    -- | The set of vertices of a graph. Like 'vertexSet' but specialised for
    -- graphs with vertices of type 'Int'.
    --
    -- @
    -- vertexIntSet == 'foldg' IntSet.'IntSet.empty' IntSet.'IntSet.singleton' IntSet.'IntSet.union' IntSet.'IntSet.union'
    -- @
    vertexIntSet :: ToVertex t ~ Int => t -> IntSet
    vertexIntSet = IntSet
-> (ToVertex t -> IntSet)
-> (IntSet -> IntSet -> IntSet)
-> (IntSet -> IntSet -> IntSet)
-> t
-> IntSet
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg IntSet
IntSet.empty Int -> IntSet
ToVertex t -> IntSet
IntSet.singleton IntSet -> IntSet -> IntSet
IntSet.union IntSet -> IntSet -> IntSet
IntSet.union

    -- | The set of edges of a graph.
    --
    -- @
    -- edgeSet == Algebra.Graph.AdjacencyMap.'AM.edgeSet' . 'toAdjacencyMap'
    -- @
    edgeSet :: Ord (ToVertex t) => t -> Set (ToVertex t, ToVertex t)
    edgeSet = AdjacencyMap (ToVertex t) -> Set (ToVertex t, ToVertex t)
forall a. Eq a => AdjacencyMap a -> Set (a, a)
AM.edgeSet (AdjacencyMap (ToVertex t) -> Set (ToVertex t, ToVertex t))
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> Set (ToVertex t, ToVertex t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | The /preset/ of a vertex is the set of its /direct predecessors/.
    --
    -- @
    -- preSet x == Algebra.Graph.AdjacencyMap.'AM.preSet' x . 'toAdjacencyMap'
    -- @
    preSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t)
    preSet ToVertex t
x = ToVertex t -> AdjacencyMap (ToVertex t) -> Set (ToVertex t)
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet ToVertex t
x (AdjacencyMap (ToVertex t) -> Set (ToVertex t))
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Set (ToVertex t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMapTranspose

    -- | The /preset/ (here @preIntSet@) of a vertex is the set of its
    -- /direct predecessors/. Like 'preSet' but specialised for graphs with
    -- vertices of type 'Int'.
    --
    -- @
    -- preIntSet x == Algebra.Graph.AdjacencyIntMap.'AIM.preIntSet' x . 'toAdjacencyIntMap'
    -- @
    preIntSet :: ToVertex t ~ Int => Int -> t -> IntSet
    preIntSet Int
x = Int -> AdjacencyIntMap -> IntSet
AIM.postIntSet Int
x (AdjacencyIntMap -> IntSet)
-> (t -> AdjacencyIntMap) -> t -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMapTranspose

    -- | The /postset/ of a vertex is the set of its /direct successors/.
    --
    -- @
    -- postSet x == Algebra.Graph.AdjacencyMap.'AM.postSet' x . 'toAdjacencyMap'
    -- @
    postSet :: Ord (ToVertex t) => ToVertex t -> t -> Set (ToVertex t)
    postSet ToVertex t
x = ToVertex t -> AdjacencyMap (ToVertex t) -> Set (ToVertex t)
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet ToVertex t
x (AdjacencyMap (ToVertex t) -> Set (ToVertex t))
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Set (ToVertex t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | The /postset/ (here @postIntSet@) of a vertex is the set of its
    -- /direct successors/. Like 'postSet' but specialised for graphs with
    -- vertices of type 'Int'.
    --
    -- @
    -- postIntSet x == Algebra.Graph.AdjacencyIntMap.'AIM.postIntSet' x . 'toAdjacencyIntMap'
    -- @
    postIntSet :: ToVertex t ~ Int => Int -> t -> IntSet
    postIntSet Int
x = Int -> AdjacencyIntMap -> IntSet
AIM.postIntSet Int
x (AdjacencyIntMap -> IntSet)
-> (t -> AdjacencyIntMap) -> t -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap

    -- | The sorted /adjacency list/ of a graph.
    --
    -- @
    -- adjacencyList == Algebra.Graph.AdjacencyMap.'AM.adjacencyList' . 'toAdjacencyMap'
    -- @
    adjacencyList :: Ord (ToVertex t) => t -> [(ToVertex t, [ToVertex t])]
    adjacencyList = AdjacencyMap (ToVertex t) -> [(ToVertex t, [ToVertex t])]
forall a. AdjacencyMap a -> [(a, [a])]
AM.adjacencyList (AdjacencyMap (ToVertex t) -> [(ToVertex t, [ToVertex t])])
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> [(ToVertex t, [ToVertex t])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Compute the /depth-first search/ forest of a graph that corresponds to
    -- searching from each of the graph vertices in the 'Ord' @a@ order.
    --
    -- @
    -- dfsForest == Algebra.Graph.AdjacencyMap.'AM.dfsForest' . toAdjacencyMap
    -- @
    dfsForest :: Ord (ToVertex t) => t -> Forest (ToVertex t)
    dfsForest = AdjacencyMap (ToVertex t) -> Forest (ToVertex t)
forall a. Ord a => AdjacencyMap a -> Forest a
AM.dfsForest (AdjacencyMap (ToVertex t) -> Forest (ToVertex t))
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Forest (ToVertex t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Compute the /depth-first search/ forest of a graph, searching from each
    -- of the given vertices in order. Note that the resulting forest does not
    -- necessarily span the whole graph, as some vertices may be unreachable.
    --
    -- @
    -- dfsForestFrom == Algebra.Graph.AdjacencyMap.'AM.dfsForestFrom' . toAdjacencyMap
    -- @
    dfsForestFrom :: Ord (ToVertex t) => t -> [ToVertex t] -> Forest (ToVertex t)
    dfsForestFrom = AdjacencyMap (ToVertex t) -> [ToVertex t] -> Forest (ToVertex t)
forall a. Ord a => AdjacencyMap a -> [a] -> Forest a
AM.dfsForestFrom (AdjacencyMap (ToVertex t) -> [ToVertex t] -> Forest (ToVertex t))
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> [ToVertex t]
-> Forest (ToVertex t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Compute the list of vertices visited by the /depth-first search/ in a
    -- graph, when searching from each of the given vertices in order.
    --
    -- @
    -- dfs == Algebra.Graph.AdjacencyMap.'AM.dfs' . toAdjacencyMap
    -- @
    dfs :: Ord (ToVertex t) => t -> [ToVertex t] -> [ToVertex t]
    dfs = AdjacencyMap (ToVertex t) -> [ToVertex t] -> [ToVertex t]
forall a. Ord a => AdjacencyMap a -> [a] -> [a]
AM.dfs (AdjacencyMap (ToVertex t) -> [ToVertex t] -> [ToVertex t])
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> [ToVertex t]
-> [ToVertex t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Compute the list of vertices that are /reachable/ from a given source
    -- vertex in a graph. The vertices in the resulting list appear in the
    -- /depth-first order/.
    --
    -- @
    -- reachable == Algebra.Graph.AdjacencyMap.'AM.reachable' . toAdjacencyMap
    -- @
    reachable :: Ord (ToVertex t) => t -> ToVertex t -> [ToVertex t]
    reachable = AdjacencyMap (ToVertex t) -> ToVertex t -> [ToVertex t]
forall a. Ord a => AdjacencyMap a -> a -> [a]
AM.reachable (AdjacencyMap (ToVertex t) -> ToVertex t -> [ToVertex t])
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> ToVertex t
-> [ToVertex t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Compute the /topological sort/ of a graph or a @AM.Cycle@ if the
    -- graph is cyclic.
    --
    -- @
    -- topSort == Algebra.Graph.AdjacencyMap.'AM.topSort' . toAdjacencyMap
    -- @
    topSort :: Ord (ToVertex t) => t -> Either (AM.Cycle (ToVertex t)) [ToVertex t]
    topSort = AdjacencyMap (ToVertex t)
-> Either (Cycle (ToVertex t)) [ToVertex t]
forall a. Ord a => AdjacencyMap a -> Either (Cycle a) [a]
AM.topSort (AdjacencyMap (ToVertex t)
 -> Either (Cycle (ToVertex t)) [ToVertex t])
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> Either (Cycle (ToVertex t)) [ToVertex t]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Check if a given graph is /acyclic/.
    --
    -- @
    -- isAcyclic == Algebra.Graph.AdjacencyMap.'AM.isAcyclic' . toAdjacencyMap
    -- @
    isAcyclic :: Ord (ToVertex t) => t -> Bool
    isAcyclic = AdjacencyMap (ToVertex t) -> Bool
forall a. Ord a => AdjacencyMap a -> Bool
AM.isAcyclic (AdjacencyMap (ToVertex t) -> Bool)
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Convert a value to the corresponding 'AM.AdjacencyMap'.
    --
    -- @
    -- toAdjacencyMap == 'foldg' 'AM.empty' 'AM.vertex' 'AM.overlay' 'AM.connect'
    -- @
    toAdjacencyMap :: Ord (ToVertex t) => t -> AM.AdjacencyMap (ToVertex t)
    toAdjacencyMap = AdjacencyMap (ToVertex t)
-> (ToVertex t -> AdjacencyMap (ToVertex t))
-> (AdjacencyMap (ToVertex t)
    -> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t))
-> (AdjacencyMap (ToVertex t)
    -> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t))
-> t
-> AdjacencyMap (ToVertex t)
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyMap (ToVertex t)
forall a. AdjacencyMap a
AM.empty ToVertex t -> AdjacencyMap (ToVertex t)
forall a. a -> AdjacencyMap a
AM.vertex AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t)
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.overlay AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t)
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.connect

    -- | Convert a value to the corresponding 'AM.AdjacencyMap' and transpose the
    -- result.
    --
    -- @
    -- toAdjacencyMapTranspose == 'foldg' 'AM.empty' 'AM.vertex' 'AM.overlay' ('flip' 'AM.connect')
    -- @
    toAdjacencyMapTranspose :: Ord (ToVertex t) => t -> AM.AdjacencyMap (ToVertex t)
    toAdjacencyMapTranspose = AdjacencyMap (ToVertex t)
-> (ToVertex t -> AdjacencyMap (ToVertex t))
-> (AdjacencyMap (ToVertex t)
    -> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t))
-> (AdjacencyMap (ToVertex t)
    -> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t))
-> t
-> AdjacencyMap (ToVertex t)
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyMap (ToVertex t)
forall a. AdjacencyMap a
AM.empty ToVertex t -> AdjacencyMap (ToVertex t)
forall a. a -> AdjacencyMap a
AM.vertex AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t)
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.overlay ((AdjacencyMap (ToVertex t)
 -> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t))
-> AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t)
forall a b c. (a -> b -> c) -> b -> a -> c
flip AdjacencyMap (ToVertex t)
-> AdjacencyMap (ToVertex t) -> AdjacencyMap (ToVertex t)
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.connect)

    -- | Convert a value to the corresponding 'AIM.AdjacencyIntMap'.
    --
    -- @
    -- toAdjacencyIntMap == 'foldg' 'AIM.empty' 'AIM.vertex' 'AIM.overlay' 'AIM.connect'
    -- @
    toAdjacencyIntMap :: ToVertex t ~ Int => t -> AIM.AdjacencyIntMap
    toAdjacencyIntMap = AdjacencyIntMap
-> (ToVertex t -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> t
-> AdjacencyIntMap
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyIntMap
AIM.empty Int -> AdjacencyIntMap
ToVertex t -> AdjacencyIntMap
AIM.vertex AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.overlay AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.connect

    -- | Convert a value to the corresponding 'AIM.AdjacencyIntMap' and transpose
    -- the result.
    --
    -- @
    -- toAdjacencyIntMapTranspose == 'foldg' 'AIM.empty' 'AIM.vertex' 'AIM.overlay' ('flip' 'AIM.connect')
    -- @
    toAdjacencyIntMapTranspose :: ToVertex t ~ Int => t -> AIM.AdjacencyIntMap
    toAdjacencyIntMapTranspose = AdjacencyIntMap
-> (ToVertex t -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> t
-> AdjacencyIntMap
forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyIntMap
AIM.empty Int -> AdjacencyIntMap
ToVertex t -> AdjacencyIntMap
AIM.vertex AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.overlay ((AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
forall a b c. (a -> b -> c) -> b -> a -> c
flip AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.connect)

    -- | Check if a given forest is a valid /depth-first search/ forest of a
    -- graph.
    --
    -- @
    -- isDfsForestOf f == Algebra.Graph.AdjacencyMap.'AM.isDfsForestOf' f . toAdjacencyMap
    -- @
    isDfsForestOf :: Ord (ToVertex t) => Forest (ToVertex t) -> t -> Bool
    isDfsForestOf Forest (ToVertex t)
f = Forest (ToVertex t) -> AdjacencyMap (ToVertex t) -> Bool
forall a. Ord a => Forest a -> AdjacencyMap a -> Bool
AM.isDfsForestOf Forest (ToVertex t)
f (AdjacencyMap (ToVertex t) -> Bool)
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

    -- | Check if a given list of vertices is a valid /topological sort/ of a
    -- graph.
    --
    -- @
    -- isTopSortOf vs == Algebra.Graph.AdjacencyMap.'AM.isTopSortOf' vs . toAdjacencyMap
    -- @
    isTopSortOf :: Ord (ToVertex t) => [ToVertex t] -> t -> Bool
    isTopSortOf [ToVertex t]
vs = [ToVertex t] -> AdjacencyMap (ToVertex t) -> Bool
forall a. Ord a => [a] -> AdjacencyMap a -> Bool
AM.isTopSortOf [ToVertex t]
vs (AdjacencyMap (ToVertex t) -> Bool)
-> (t -> AdjacencyMap (ToVertex t)) -> t -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

-- | See "Algebra.Graph".
instance Ord a => ToGraph (G.Graph a) where
    type ToVertex (G.Graph a) = a
    toGraph :: Graph a -> Graph (ToVertex (Graph a))
toGraph = Graph a -> Graph (ToVertex (Graph a))
forall a. a -> a
id
    foldg :: r
-> (ToVertex (Graph a) -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph a
-> r
foldg   = r
-> (ToVertex (Graph a) -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph a
-> r
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
G.foldg
    hasEdge :: ToVertex (Graph a) -> ToVertex (Graph a) -> Graph a -> Bool
hasEdge = ToVertex (Graph a) -> ToVertex (Graph a) -> Graph a -> Bool
forall a. Eq a => a -> a -> Graph a -> Bool
G.hasEdge

-- | See "Algebra.Graph.AdjacencyMap".
instance Ord a => ToGraph (AM.AdjacencyMap a) where
    type ToVertex (AM.AdjacencyMap a) = a
    toGraph :: AdjacencyMap a -> Graph (ToVertex (AdjacencyMap a))
toGraph                    = [(a, [a])] -> Graph a
forall a. [(a, [a])] -> Graph a
G.stars
                               ([(a, [a])] -> Graph a)
-> (AdjacencyMap a -> [(a, [a])]) -> AdjacencyMap a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, Set a) -> (a, [a])) -> [(a, Set a)] -> [(a, [a])]
forall a b. (a -> b) -> [a] -> [b]
map ((Set a -> [a]) -> (a, Set a) -> (a, [a])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Set a -> [a]
forall a. Set a -> [a]
Set.toList)
                               ([(a, Set a)] -> [(a, [a])])
-> (AdjacencyMap a -> [(a, Set a)]) -> AdjacencyMap a -> [(a, [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a (Set a) -> [(a, Set a)]
forall k a. Map k a -> [(k, a)]
Map.toList
                               (Map a (Set a) -> [(a, Set a)])
-> (AdjacencyMap a -> Map a (Set a))
-> AdjacencyMap a
-> [(a, Set a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> Map a (Set a)
forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap
    isEmpty :: AdjacencyMap a -> Bool
isEmpty                    = AdjacencyMap a -> Bool
forall a. AdjacencyMap a -> Bool
AM.isEmpty
    hasVertex :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasVertex                  = ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
forall a. Ord a => a -> AdjacencyMap a -> Bool
AM.hasVertex
    hasEdge :: ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasEdge                    = ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
forall a. Ord a => a -> a -> AdjacencyMap a -> Bool
AM.hasEdge
    vertexCount :: AdjacencyMap a -> Int
vertexCount                = AdjacencyMap a -> Int
forall a. AdjacencyMap a -> Int
AM.vertexCount
    edgeCount :: AdjacencyMap a -> Int
edgeCount                  = AdjacencyMap a -> Int
forall a. AdjacencyMap a -> Int
AM.edgeCount
    vertexList :: AdjacencyMap a -> [ToVertex (AdjacencyMap a)]
vertexList                 = AdjacencyMap a -> [ToVertex (AdjacencyMap a)]
forall a. AdjacencyMap a -> [a]
AM.vertexList
    vertexSet :: AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
vertexSet                  = AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. AdjacencyMap a -> Set a
AM.vertexSet
    vertexIntSet :: AdjacencyMap a -> IntSet
vertexIntSet               = [Int] -> IntSet
IntSet.fromAscList ([Int] -> IntSet)
-> (AdjacencyMap Int -> [Int]) -> AdjacencyMap Int -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap Int -> [Int]
forall a. AdjacencyMap a -> [a]
AM.vertexList
    edgeList :: AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
edgeList                   = AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
forall a. AdjacencyMap a -> [(a, a)]
AM.edgeList
    edgeSet :: AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
edgeSet                    = AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
forall a. Eq a => AdjacencyMap a -> Set (a, a)
AM.edgeSet
    adjacencyList :: AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]
adjacencyList              = AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]
forall a. AdjacencyMap a -> [(a, [a])]
AM.adjacencyList
    preSet :: ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
preSet                     = ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.preSet
    postSet :: ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
postSet                    = ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet
    dfsForest :: AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))
dfsForest                  = AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))
forall a. Ord a => AdjacencyMap a -> Forest a
AM.dfsForest
    dfsForestFrom :: AdjacencyMap a
-> [ToVertex (AdjacencyMap a)]
-> Forest (ToVertex (AdjacencyMap a))
dfsForestFrom              = AdjacencyMap a
-> [ToVertex (AdjacencyMap a)]
-> Forest (ToVertex (AdjacencyMap a))
forall a. Ord a => AdjacencyMap a -> [a] -> Forest a
AM.dfsForestFrom
    dfs :: AdjacencyMap a
-> [ToVertex (AdjacencyMap a)] -> [ToVertex (AdjacencyMap a)]
dfs                        = AdjacencyMap a
-> [ToVertex (AdjacencyMap a)] -> [ToVertex (AdjacencyMap a)]
forall a. Ord a => AdjacencyMap a -> [a] -> [a]
AM.dfs
    reachable :: AdjacencyMap a
-> ToVertex (AdjacencyMap a) -> [ToVertex (AdjacencyMap a)]
reachable                  = AdjacencyMap a
-> ToVertex (AdjacencyMap a) -> [ToVertex (AdjacencyMap a)]
forall a. Ord a => AdjacencyMap a -> a -> [a]
AM.reachable
    topSort :: AdjacencyMap a
-> Either
     (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)]
topSort                    = AdjacencyMap a
-> Either
     (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)]
forall a. Ord a => AdjacencyMap a -> Either (Cycle a) [a]
AM.topSort
    isAcyclic :: AdjacencyMap a -> Bool
isAcyclic                  = AdjacencyMap a -> Bool
forall a. Ord a => AdjacencyMap a -> Bool
AM.isAcyclic
    toAdjacencyMap :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMap             = AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
forall a. a -> a
id
    toAdjacencyIntMap :: AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMap          = AdjacencyMap a -> AdjacencyIntMap
AdjacencyMap Int -> AdjacencyIntMap
AIM.fromAdjacencyMap
    toAdjacencyMapTranspose :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMapTranspose    = AdjacencyMap a -> AdjacencyMap a
forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
AM.transpose (AdjacencyMap a -> AdjacencyMap a)
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> AdjacencyMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyIntMapTranspose :: AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMapTranspose = AdjacencyIntMap -> AdjacencyIntMap
AIM.transpose (AdjacencyIntMap -> AdjacencyIntMap)
-> (AdjacencyMap a -> AdjacencyIntMap)
-> AdjacencyMap a
-> AdjacencyIntMap
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap
    isDfsForestOf :: Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
isDfsForestOf              = Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
forall a. Ord a => Forest a -> AdjacencyMap a -> Bool
AM.isDfsForestOf
    isTopSortOf :: [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
isTopSortOf                = [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
forall a. Ord a => [a] -> AdjacencyMap a -> Bool
AM.isTopSortOf

-- | See "Algebra.Graph.AdjacencyIntMap".
instance ToGraph AIM.AdjacencyIntMap where
    type ToVertex AIM.AdjacencyIntMap = Int
    toGraph :: AdjacencyIntMap -> Graph (ToVertex AdjacencyIntMap)
toGraph                    = [(Int, [Int])] -> Graph Int
forall a. [(a, [a])] -> Graph a
G.stars
                               ([(Int, [Int])] -> Graph Int)
-> (AdjacencyIntMap -> [(Int, [Int])])
-> AdjacencyIntMap
-> Graph Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, IntSet) -> (Int, [Int]))
-> [(Int, IntSet)] -> [(Int, [Int])]
forall a b. (a -> b) -> [a] -> [b]
map ((IntSet -> [Int]) -> (Int, IntSet) -> (Int, [Int])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntSet -> [Int]
IntSet.toList)
                               ([(Int, IntSet)] -> [(Int, [Int])])
-> (AdjacencyIntMap -> [(Int, IntSet)])
-> AdjacencyIntMap
-> [(Int, [Int])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap IntSet -> [(Int, IntSet)]
forall a. IntMap a -> [(Int, a)]
IntMap.toList
                               (IntMap IntSet -> [(Int, IntSet)])
-> (AdjacencyIntMap -> IntMap IntSet)
-> AdjacencyIntMap
-> [(Int, IntSet)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap
    isEmpty :: AdjacencyIntMap -> Bool
isEmpty                    = AdjacencyIntMap -> Bool
AIM.isEmpty
    hasVertex :: ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
hasVertex                  = Int -> AdjacencyIntMap -> Bool
ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
AIM.hasVertex
    hasEdge :: ToVertex AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
hasEdge                    = Int -> Int -> AdjacencyIntMap -> Bool
ToVertex AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
AIM.hasEdge
    vertexCount :: AdjacencyIntMap -> Int
vertexCount                = AdjacencyIntMap -> Int
AIM.vertexCount
    edgeCount :: AdjacencyIntMap -> Int
edgeCount                  = AdjacencyIntMap -> Int
AIM.edgeCount
    vertexList :: AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
vertexList                 = AdjacencyIntMap -> [Int]
AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
AIM.vertexList
    vertexSet :: AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap)
vertexSet                  = [Int] -> Set Int
forall a. Eq a => [a] -> Set a
Set.fromAscList ([Int] -> Set Int)
-> (AdjacencyIntMap -> [Int]) -> AdjacencyIntMap -> Set Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toAscList (IntSet -> [Int])
-> (AdjacencyIntMap -> IntSet) -> AdjacencyIntMap -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> IntSet
AIM.vertexIntSet
    vertexIntSet :: AdjacencyIntMap -> IntSet
vertexIntSet               = AdjacencyIntMap -> IntSet
AIM.vertexIntSet
    edgeList :: AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)]
edgeList                   = AdjacencyIntMap -> [(Int, Int)]
AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)]
AIM.edgeList
    edgeSet :: AdjacencyIntMap
-> Set (ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)
edgeSet                    = AdjacencyIntMap -> Set (Int, Int)
AdjacencyIntMap
-> Set (ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)
AIM.edgeSet
    adjacencyList :: AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, [ToVertex AdjacencyIntMap])]
adjacencyList              = AdjacencyIntMap -> [(Int, [Int])]
AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, [ToVertex AdjacencyIntMap])]
AIM.adjacencyList
    preIntSet :: Int -> AdjacencyIntMap -> IntSet
preIntSet                  = Int -> AdjacencyIntMap -> IntSet
AIM.preIntSet
    postIntSet :: Int -> AdjacencyIntMap -> IntSet
postIntSet                 = Int -> AdjacencyIntMap -> IntSet
AIM.postIntSet
    dfsForest :: AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap)
dfsForest                  = AdjacencyIntMap -> Forest Int
AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap)
AIM.dfsForest
    dfsForestFrom :: AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> Forest (ToVertex AdjacencyIntMap)
dfsForestFrom              = AdjacencyIntMap -> [Int] -> Forest Int
AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> Forest (ToVertex AdjacencyIntMap)
AIM.dfsForestFrom
    dfs :: AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> [ToVertex AdjacencyIntMap]
dfs                        = AdjacencyIntMap -> [Int] -> [Int]
AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> [ToVertex AdjacencyIntMap]
AIM.dfs
    reachable :: AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
reachable                  = AdjacencyIntMap -> Int -> [Int]
AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
AIM.reachable
    topSort :: AdjacencyIntMap
-> Either
     (Cycle (ToVertex AdjacencyIntMap)) [ToVertex AdjacencyIntMap]
topSort                    = AdjacencyIntMap -> Either (Cycle Int) [Int]
AdjacencyIntMap
-> Either
     (Cycle (ToVertex AdjacencyIntMap)) [ToVertex AdjacencyIntMap]
AIM.topSort
    isAcyclic :: AdjacencyIntMap -> Bool
isAcyclic                  = AdjacencyIntMap -> Bool
AIM.isAcyclic
    toAdjacencyMap :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)
toAdjacencyMap             = [(Int, [Int])] -> AdjacencyMap Int
forall a. Ord a => [(a, [a])] -> AdjacencyMap a
AM.stars ([(Int, [Int])] -> AdjacencyMap Int)
-> (AdjacencyIntMap -> [(Int, [Int])])
-> AdjacencyIntMap
-> AdjacencyMap Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> [(Int, [Int])]
AIM.adjacencyList
    toAdjacencyIntMap :: AdjacencyIntMap -> AdjacencyIntMap
toAdjacencyIntMap          = AdjacencyIntMap -> AdjacencyIntMap
forall a. a -> a
id
    toAdjacencyMapTranspose :: AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)
toAdjacencyMapTranspose    = AdjacencyMap Int -> AdjacencyMap Int
forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
AM.transpose (AdjacencyMap Int -> AdjacencyMap Int)
-> (AdjacencyIntMap -> AdjacencyMap Int)
-> AdjacencyIntMap
-> AdjacencyMap Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> AdjacencyMap Int
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyIntMapTranspose :: AdjacencyIntMap -> AdjacencyIntMap
toAdjacencyIntMapTranspose = AdjacencyIntMap -> AdjacencyIntMap
AIM.transpose (AdjacencyIntMap -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap)
-> AdjacencyIntMap
-> AdjacencyIntMap
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap
    isDfsForestOf :: Forest (ToVertex AdjacencyIntMap) -> AdjacencyIntMap -> Bool
isDfsForestOf              = Forest Int -> AdjacencyIntMap -> Bool
Forest (ToVertex AdjacencyIntMap) -> AdjacencyIntMap -> Bool
AIM.isDfsForestOf
    isTopSortOf :: [ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> Bool
isTopSortOf                = [Int] -> AdjacencyIntMap -> Bool
[ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> Bool
AIM.isTopSortOf

-- | See "Algebra.Graph.NonEmpty.AdjacencyMap".
instance Ord a => ToGraph (NAM.AdjacencyMap a) where
    type ToVertex (NAM.AdjacencyMap a) = a
    toGraph :: AdjacencyMap a -> Graph (ToVertex (AdjacencyMap a))
toGraph                    = AdjacencyMap a -> Graph a
forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph (AdjacencyMap a -> Graph a)
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isEmpty :: AdjacencyMap a -> Bool
isEmpty AdjacencyMap a
_                  = Bool
False
    hasVertex :: ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasVertex                  = ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
forall a. Ord a => a -> AdjacencyMap a -> Bool
NAM.hasVertex
    hasEdge :: ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasEdge                    = ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
forall a. Ord a => a -> a -> AdjacencyMap a -> Bool
NAM.hasEdge
    vertexCount :: AdjacencyMap a -> Int
vertexCount                = AdjacencyMap a -> Int
forall a. AdjacencyMap a -> Int
NAM.vertexCount
    edgeCount :: AdjacencyMap a -> Int
edgeCount                  = AdjacencyMap a -> Int
forall a. AdjacencyMap a -> Int
NAM.edgeCount
    vertexList :: AdjacencyMap a -> [ToVertex (AdjacencyMap a)]
vertexList                 = AdjacencyMap a -> [a]
forall t. (ToGraph t, Ord (ToVertex t)) => t -> [ToVertex t]
vertexList (AdjacencyMap a -> [a])
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    vertexSet :: AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
vertexSet                  = AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. AdjacencyMap a -> Set a
NAM.vertexSet
    vertexIntSet :: AdjacencyMap a -> IntSet
vertexIntSet               = AdjacencyMap Int -> IntSet
forall t. (ToGraph t, ToVertex t ~ Int) => t -> IntSet
vertexIntSet (AdjacencyMap Int -> IntSet)
-> (AdjacencyMap a -> AdjacencyMap Int) -> AdjacencyMap a -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap Int
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    edgeList :: AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
edgeList                   = AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
forall a. AdjacencyMap a -> [(a, a)]
NAM.edgeList
    edgeSet :: AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
edgeSet                    = AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
forall a. Ord a => AdjacencyMap a -> Set (a, a)
NAM.edgeSet
    adjacencyList :: AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]
adjacencyList              = AdjacencyMap a -> [(a, [a])]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [(ToVertex t, [ToVertex t])]
adjacencyList (AdjacencyMap a -> [(a, [a])])
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> [(a, [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    preSet :: ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
preSet                     = ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. Ord a => a -> AdjacencyMap a -> Set a
NAM.preSet
    postSet :: ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
postSet                    = ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
forall a. Ord a => a -> AdjacencyMap a -> Set a
NAM.postSet
    dfsForest :: AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))
dfsForest                  = AdjacencyMap a -> [Tree a]
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Forest (ToVertex t)
dfsForest (AdjacencyMap a -> [Tree a])
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> [Tree a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    dfsForestFrom :: AdjacencyMap a
-> [ToVertex (AdjacencyMap a)]
-> Forest (ToVertex (AdjacencyMap a))
dfsForestFrom              = AdjacencyMap a -> [a] -> [Tree a]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [ToVertex t] -> Forest (ToVertex t)
dfsForestFrom (AdjacencyMap a -> [a] -> [Tree a])
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> [a]
-> [Tree a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    dfs :: AdjacencyMap a
-> [ToVertex (AdjacencyMap a)] -> [ToVertex (AdjacencyMap a)]
dfs                        = AdjacencyMap a -> [a] -> [a]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [ToVertex t] -> [ToVertex t]
dfs (AdjacencyMap a -> [a] -> [a])
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> [a]
-> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    reachable :: AdjacencyMap a
-> ToVertex (AdjacencyMap a) -> [ToVertex (AdjacencyMap a)]
reachable                  = AdjacencyMap a -> a -> [a]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> ToVertex t -> [ToVertex t]
reachable (AdjacencyMap a -> a -> [a])
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    topSort :: AdjacencyMap a
-> Either
     (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)]
topSort                    = AdjacencyMap a -> Either (NonEmpty a) [a]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> Either (Cycle (ToVertex t)) [ToVertex t]
topSort (AdjacencyMap a -> Either (NonEmpty a) [a])
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> Either (NonEmpty a) [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isAcyclic :: AdjacencyMap a -> Bool
isAcyclic                  = AdjacencyMap a -> Bool
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Bool
isAcyclic (AdjacencyMap a -> Bool)
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyMap :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMap             = AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
forall a. AdjacencyMap a -> AdjacencyMap a
NAM.fromNonEmpty
    toAdjacencyIntMap :: AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMap          = AdjacencyMap Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap (AdjacencyMap Int -> AdjacencyIntMap)
-> (AdjacencyMap a -> AdjacencyMap Int)
-> AdjacencyMap a
-> AdjacencyIntMap
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap Int
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyMapTranspose :: AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMapTranspose    = AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap (AdjacencyMap a -> AdjacencyMap a)
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> AdjacencyMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
NAM.transpose
    toAdjacencyIntMapTranspose :: AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMapTranspose = AdjacencyMap a -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap (AdjacencyMap a -> AdjacencyIntMap)
-> (AdjacencyMap a -> AdjacencyMap a)
-> AdjacencyMap a
-> AdjacencyIntMap
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
NAM.transpose
    isDfsForestOf :: Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
isDfsForestOf Forest (ToVertex (AdjacencyMap a))
f            = Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
forall t.
(ToGraph t, Ord (ToVertex t)) =>
Forest (ToVertex t) -> t -> Bool
isDfsForestOf Forest (ToVertex (AdjacencyMap a))
Forest (ToVertex (AdjacencyMap a))
f (AdjacencyMap a -> Bool)
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isTopSortOf :: [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
isTopSortOf [ToVertex (AdjacencyMap a)]
x              = [ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
forall t.
(ToGraph t, Ord (ToVertex t)) =>
[ToVertex t] -> t -> Bool
isTopSortOf [ToVertex (AdjacencyMap a)]
[ToVertex (AdjacencyMap a)]
x (AdjacencyMap a -> Bool)
-> (AdjacencyMap a -> AdjacencyMap a) -> AdjacencyMap a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyMap a -> AdjacencyMap a
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

-- | The /adjacency map/ of a graph: each vertex is associated with a set of its
-- /direct successors/.
--
-- @
-- adjacencyMap == Algebra.Graph.AdjacencyMap.'Algebra.Graph.AdjacencyMap.adjacencyMap' . 'toAdjacencyMap'
-- @
adjacencyMap :: ToGraph t => Ord (ToVertex t) => t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMap :: t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMap = AdjacencyMap (ToVertex t) -> Map (ToVertex t) (Set (ToVertex t))
forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap (AdjacencyMap (ToVertex t) -> Map (ToVertex t) (Set (ToVertex t)))
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> Map (ToVertex t) (Set (ToVertex t))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap

-- | The /adjacency map/ of a graph: each vertex is associated with a set of its
-- /direct successors/. Like 'adjacencyMap' but specialised for graphs with
-- vertices of type 'Int'.
--
-- @
-- adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.'Algebra.Graph.AdjacencyIntMap.adjacencyIntMap' . 'toAdjacencyIntMap'
-- @
adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
adjacencyIntMap :: t -> IntMap IntSet
adjacencyIntMap = AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap (AdjacencyIntMap -> IntMap IntSet)
-> (t -> AdjacencyIntMap) -> t -> IntMap IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap

-- | The transposed /adjacency map/ of a graph: each vertex is associated with a
-- set of its /direct predecessors/.
--
-- @
-- adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.'Algebra.Graph.AdjacencyMap.adjacencyMap' . 'toAdjacencyMapTranspose'
-- @
adjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMapTranspose :: t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMapTranspose = AdjacencyMap (ToVertex t) -> Map (ToVertex t) (Set (ToVertex t))
forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap (AdjacencyMap (ToVertex t) -> Map (ToVertex t) (Set (ToVertex t)))
-> (t -> AdjacencyMap (ToVertex t))
-> t
-> Map (ToVertex t) (Set (ToVertex t))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyMap (ToVertex t)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMapTranspose

-- | The transposed /adjacency map/ of a graph: each vertex is associated with a
-- set of its /direct predecessors/. Like 'adjacencyMapTranspose' but
-- specialised for graphs with vertices of type 'Int'.
--
-- @
-- adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.'Algebra.Graph.AdjacencyIntMap.adjacencyIntMap' . 'toAdjacencyIntMapTranspose'
-- @
adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
adjacencyIntMapTranspose :: t -> IntMap IntSet
adjacencyIntMapTranspose = AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap (AdjacencyIntMap -> IntMap IntSet)
-> (t -> AdjacencyIntMap) -> t -> IntMap IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMapTranspose