{-# LANGUAGE ConstrainedClassMethods #-}
-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.ToGraph
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : [email protected]
-- 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg forall a. Graph a
G.Empty forall a. a -> Graph a
G.Vertex forall a. Graph a -> Graph a -> Graph a
G.Overlay 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 = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph

    -- | Check if a graph is empty.
    --
    -- @
    -- isEmpty == 'foldg' True ('const' False) (&&) (&&)
    -- @
    isEmpty :: t -> Bool
    isEmpty = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Bool
True (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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg Bool
False (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 = forall a. Eq a => a -> a -> Graph a -> Bool
G.hasEdge ToVertex t
x ToVertex t
y forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Set a -> Int
Set.size forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. AdjacencyMap a -> Int
AM.edgeCount forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Set a -> [a]
Set.toAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. AdjacencyMap a -> [(a, a)]
AM.edgeList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg forall a. Set a
Set.empty forall a. a -> Set a
Set.singleton forall a. Ord a => Set a -> Set a -> Set a
Set.union 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg IntSet
IntSet.empty Int -> 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 = forall a. Eq a => AdjacencyMap a -> Set (a, a)
AM.edgeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet ToVertex t
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet ToVertex t
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. AdjacencyMap a -> [(a, [a])]
AM.adjacencyList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> Forest a
AM.dfsForest forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> [a] -> Forest a
AM.dfsForestFrom forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> [a] -> [a]
AM.dfs forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> a -> [a]
AM.reachable forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> Either (Cycle a) [a]
AM.topSort forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => AdjacencyMap a -> Bool
AM.isAcyclic forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg forall a. AdjacencyMap a
AM.empty forall a. a -> AdjacencyMap a
AM.vertex forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.overlay 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg forall a. AdjacencyMap a
AM.empty forall a. a -> AdjacencyMap a
AM.vertex forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.overlay (forall a b c. (a -> b -> c) -> b -> a -> c
flip 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyIntMap
AIM.empty Int -> 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 = forall t r.
ToGraph t =>
r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
foldg AdjacencyIntMap
AIM.empty Int -> AdjacencyIntMap
AIM.vertex AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.overlay (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 = forall a. Ord a => Forest a -> AdjacencyMap a -> Bool
AM.isDfsForestOf Forest (ToVertex t)
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Ord a => [a] -> AdjacencyMap a -> Bool
AM.isTopSortOf [ToVertex t]
vs forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. a -> a
id
    foldg :: forall r.
r
-> (ToVertex (Graph a) -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph a
-> r
foldg   = forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
G.foldg
    hasEdge :: Eq (ToVertex (Graph a)) =>
ToVertex (Graph a) -> ToVertex (Graph a) -> Graph a -> Bool
hasEdge = 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                    = forall a. [(a, [a])] -> Graph a
G.stars
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Set a -> [a]
Set.toList)
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Map k a -> [(k, a)]
Map.toList
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap
    isEmpty :: AdjacencyMap a -> Bool
isEmpty                    = forall a. AdjacencyMap a -> Bool
AM.isEmpty
    hasVertex :: Eq (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasVertex                  = forall a. Ord a => a -> AdjacencyMap a -> Bool
AM.hasVertex
    hasEdge :: Eq (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasEdge                    = forall a. Ord a => a -> a -> AdjacencyMap a -> Bool
AM.hasEdge
    vertexCount :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Int
vertexCount                = forall a. AdjacencyMap a -> Int
AM.vertexCount
    edgeCount :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Int
edgeCount                  = forall a. AdjacencyMap a -> Int
AM.edgeCount
    vertexList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> [ToVertex (AdjacencyMap a)]
vertexList                 = forall a. AdjacencyMap a -> [a]
AM.vertexList
    vertexSet :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
vertexSet                  = forall a. AdjacencyMap a -> Set a
AM.vertexSet
    vertexIntSet :: (ToVertex (AdjacencyMap a) ~ Int) => AdjacencyMap a -> IntSet
vertexIntSet               = [Int] -> IntSet
IntSet.fromAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. AdjacencyMap a -> [a]
AM.vertexList
    edgeList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
edgeList                   = forall a. AdjacencyMap a -> [(a, a)]
AM.edgeList
    edgeSet :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
edgeSet                    = forall a. Eq a => AdjacencyMap a -> Set (a, a)
AM.edgeSet
    adjacencyList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]
adjacencyList              = forall a. AdjacencyMap a -> [(a, [a])]
AM.adjacencyList
    preSet :: Ord (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
preSet                     = forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.preSet
    postSet :: Ord (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
postSet                    = forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet
    dfsForest :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))
dfsForest                  = forall a. Ord a => AdjacencyMap a -> Forest a
AM.dfsForest
    dfsForestFrom :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [ToVertex (AdjacencyMap a)]
-> Forest (ToVertex (AdjacencyMap a))
dfsForestFrom              = forall a. Ord a => AdjacencyMap a -> [a] -> Forest a
AM.dfsForestFrom
    dfs :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [ToVertex (AdjacencyMap a)] -> [ToVertex (AdjacencyMap a)]
dfs                        = forall a. Ord a => AdjacencyMap a -> [a] -> [a]
AM.dfs
    reachable :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> ToVertex (AdjacencyMap a) -> [ToVertex (AdjacencyMap a)]
reachable                  = forall a. Ord a => AdjacencyMap a -> a -> [a]
AM.reachable
    topSort :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> Either
     (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)]
topSort                    = forall a. Ord a => AdjacencyMap a -> Either (Cycle a) [a]
AM.topSort
    isAcyclic :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Bool
isAcyclic                  = forall a. Ord a => AdjacencyMap a -> Bool
AM.isAcyclic
    toAdjacencyMap :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMap             = forall a. a -> a
id
    toAdjacencyIntMap :: (ToVertex (AdjacencyMap a) ~ Int) =>
AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMap          = AdjacencyMap Int -> AdjacencyIntMap
AIM.fromAdjacencyMap
    toAdjacencyMapTranspose :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMapTranspose    = forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
AM.transpose forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyIntMapTranspose :: (ToVertex (AdjacencyMap a) ~ Int) =>
AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMapTranspose = AdjacencyIntMap -> AdjacencyIntMap
AIM.transpose forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap
    isDfsForestOf :: Ord (ToVertex (AdjacencyMap a)) =>
Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
isDfsForestOf              = forall a. Ord a => Forest a -> AdjacencyMap a -> Bool
AM.isDfsForestOf
    isTopSortOf :: Ord (ToVertex (AdjacencyMap a)) =>
[ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
isTopSortOf                = 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                    = forall a. [(a, [a])] -> Graph a
G.stars
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntSet -> [Int]
IntSet.toList)
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. IntMap a -> [(Int, a)]
IntMap.toList
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap
    isEmpty :: AdjacencyIntMap -> Bool
isEmpty                    = AdjacencyIntMap -> Bool
AIM.isEmpty
    hasVertex :: Eq (ToVertex AdjacencyIntMap) =>
ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
hasVertex                  = Int -> AdjacencyIntMap -> Bool
AIM.hasVertex
    hasEdge :: Eq (ToVertex AdjacencyIntMap) =>
ToVertex AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> AdjacencyIntMap -> Bool
hasEdge                    = Int -> Int -> AdjacencyIntMap -> Bool
AIM.hasEdge
    vertexCount :: Ord (ToVertex AdjacencyIntMap) => AdjacencyIntMap -> Int
vertexCount                = AdjacencyIntMap -> Int
AIM.vertexCount
    edgeCount :: Ord (ToVertex AdjacencyIntMap) => AdjacencyIntMap -> Int
edgeCount                  = AdjacencyIntMap -> Int
AIM.edgeCount
    vertexList :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
vertexList                 = AdjacencyIntMap -> [Int]
AIM.vertexList
    vertexSet :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap -> Set (ToVertex AdjacencyIntMap)
vertexSet                  = forall a. Eq a => [a] -> Set a
Set.fromAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> IntSet
AIM.vertexIntSet
    vertexIntSet :: (ToVertex AdjacencyIntMap ~ Int) => AdjacencyIntMap -> IntSet
vertexIntSet               = AdjacencyIntMap -> IntSet
AIM.vertexIntSet
    edgeList :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)]
edgeList                   = AdjacencyIntMap -> [(Int, Int)]
AIM.edgeList
    edgeSet :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> Set (ToVertex AdjacencyIntMap, ToVertex AdjacencyIntMap)
edgeSet                    = AdjacencyIntMap -> Set (Int, Int)
AIM.edgeSet
    adjacencyList :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> [(ToVertex AdjacencyIntMap, [ToVertex AdjacencyIntMap])]
adjacencyList              = AdjacencyIntMap -> [(Int, [Int])]
AIM.adjacencyList
    preIntSet :: (ToVertex AdjacencyIntMap ~ Int) =>
Int -> AdjacencyIntMap -> IntSet
preIntSet                  = Int -> AdjacencyIntMap -> IntSet
AIM.preIntSet
    postIntSet :: (ToVertex AdjacencyIntMap ~ Int) =>
Int -> AdjacencyIntMap -> IntSet
postIntSet                 = Int -> AdjacencyIntMap -> IntSet
AIM.postIntSet
    dfsForest :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap -> Forest (ToVertex AdjacencyIntMap)
dfsForest                  = AdjacencyIntMap -> Forest Int
AIM.dfsForest
    dfsForestFrom :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> Forest (ToVertex AdjacencyIntMap)
dfsForestFrom              = AdjacencyIntMap -> [Int] -> Forest Int
AIM.dfsForestFrom
    dfs :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> [ToVertex AdjacencyIntMap] -> [ToVertex AdjacencyIntMap]
dfs                        = AdjacencyIntMap -> [Int] -> [Int]
AIM.dfs
    reachable :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> ToVertex AdjacencyIntMap -> [ToVertex AdjacencyIntMap]
reachable                  = AdjacencyIntMap -> Int -> [Int]
AIM.reachable
    topSort :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap
-> Either
     (Cycle (ToVertex AdjacencyIntMap)) [ToVertex AdjacencyIntMap]
topSort                    = AdjacencyIntMap -> Either (Cycle Int) [Int]
AIM.topSort
    isAcyclic :: Ord (ToVertex AdjacencyIntMap) => AdjacencyIntMap -> Bool
isAcyclic                  = AdjacencyIntMap -> Bool
AIM.isAcyclic
    toAdjacencyMap :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)
toAdjacencyMap             = forall a. Ord a => [(a, [a])] -> AdjacencyMap a
AM.stars forall b c a. (b -> c) -> (a -> b) -> a -> c
. AdjacencyIntMap -> [(Int, [Int])]
AIM.adjacencyList
    toAdjacencyIntMap :: (ToVertex AdjacencyIntMap ~ Int) =>
AdjacencyIntMap -> AdjacencyIntMap
toAdjacencyIntMap          = forall a. a -> a
id
    toAdjacencyMapTranspose :: Ord (ToVertex AdjacencyIntMap) =>
AdjacencyIntMap -> AdjacencyMap (ToVertex AdjacencyIntMap)
toAdjacencyMapTranspose    = forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
AM.transpose forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyIntMapTranspose :: (ToVertex AdjacencyIntMap ~ Int) =>
AdjacencyIntMap -> AdjacencyIntMap
toAdjacencyIntMapTranspose = AdjacencyIntMap -> AdjacencyIntMap
AIM.transpose forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap
    isDfsForestOf :: Ord (ToVertex AdjacencyIntMap) =>
Forest (ToVertex AdjacencyIntMap) -> AdjacencyIntMap -> Bool
isDfsForestOf              = Forest Int -> AdjacencyIntMap -> Bool
AIM.isDfsForestOf
    isTopSortOf :: Ord (ToVertex AdjacencyIntMap) =>
[ToVertex AdjacencyIntMap] -> AdjacencyIntMap -> Bool
isTopSortOf                = [Int] -> 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                    = forall t. ToGraph t => t -> Graph (ToVertex t)
toGraph forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isEmpty :: AdjacencyMap a -> Bool
isEmpty AdjacencyMap a
_                  = Bool
False
    hasVertex :: Eq (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasVertex                  = forall a. Ord a => a -> AdjacencyMap a -> Bool
NAM.hasVertex
    hasEdge :: Eq (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> ToVertex (AdjacencyMap a) -> AdjacencyMap a -> Bool
hasEdge                    = forall a. Ord a => a -> a -> AdjacencyMap a -> Bool
NAM.hasEdge
    vertexCount :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Int
vertexCount                = forall a. AdjacencyMap a -> Int
NAM.vertexCount
    edgeCount :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Int
edgeCount                  = forall a. AdjacencyMap a -> Int
NAM.edgeCount
    vertexList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> [ToVertex (AdjacencyMap a)]
vertexList                 = forall t. (ToGraph t, Ord (ToVertex t)) => t -> [ToVertex t]
vertexList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    vertexSet :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
vertexSet                  = forall a. AdjacencyMap a -> Set a
NAM.vertexSet
    vertexIntSet :: (ToVertex (AdjacencyMap a) ~ Int) => AdjacencyMap a -> IntSet
vertexIntSet               = forall t. (ToGraph t, ToVertex t ~ Int) => t -> IntSet
vertexIntSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    edgeList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))]
edgeList                   = forall a. AdjacencyMap a -> [(a, a)]
NAM.edgeList
    edgeSet :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> Set (ToVertex (AdjacencyMap a), ToVertex (AdjacencyMap a))
edgeSet                    = forall a. Ord a => AdjacencyMap a -> Set (a, a)
NAM.edgeSet
    adjacencyList :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [(ToVertex (AdjacencyMap a), [ToVertex (AdjacencyMap a)])]
adjacencyList              = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [(ToVertex t, [ToVertex t])]
adjacencyList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    preSet :: Ord (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
preSet                     = forall a. Ord a => a -> AdjacencyMap a -> Set a
NAM.preSet
    postSet :: Ord (ToVertex (AdjacencyMap a)) =>
ToVertex (AdjacencyMap a)
-> AdjacencyMap a -> Set (ToVertex (AdjacencyMap a))
postSet                    = forall a. Ord a => a -> AdjacencyMap a -> Set a
NAM.postSet
    dfsForest :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> Forest (ToVertex (AdjacencyMap a))
dfsForest                  = forall t. (ToGraph t, Ord (ToVertex t)) => t -> Forest (ToVertex t)
dfsForest forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    dfsForestFrom :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [ToVertex (AdjacencyMap a)]
-> Forest (ToVertex (AdjacencyMap a))
dfsForestFrom              = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [ToVertex t] -> Forest (ToVertex t)
dfsForestFrom forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    dfs :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> [ToVertex (AdjacencyMap a)] -> [ToVertex (AdjacencyMap a)]
dfs                        = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [ToVertex t] -> [ToVertex t]
dfs forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    reachable :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> ToVertex (AdjacencyMap a) -> [ToVertex (AdjacencyMap a)]
reachable                  = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> ToVertex t -> [ToVertex t]
reachable forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    topSort :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a
-> Either
     (Cycle (ToVertex (AdjacencyMap a))) [ToVertex (AdjacencyMap a)]
topSort                    = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> Either (Cycle (ToVertex t)) [ToVertex t]
topSort forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isAcyclic :: Ord (ToVertex (AdjacencyMap a)) => AdjacencyMap a -> Bool
isAcyclic                  = forall t. (ToGraph t, Ord (ToVertex t)) => t -> Bool
isAcyclic forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyMap :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMap             = forall a. AdjacencyMap a -> AdjacencyMap a
NAM.fromNonEmpty
    toAdjacencyIntMap :: (ToVertex (AdjacencyMap a) ~ Int) =>
AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMap          = forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    toAdjacencyMapTranspose :: Ord (ToVertex (AdjacencyMap a)) =>
AdjacencyMap a -> AdjacencyMap (ToVertex (AdjacencyMap a))
toAdjacencyMapTranspose    = forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
NAM.transpose
    toAdjacencyIntMapTranspose :: (ToVertex (AdjacencyMap a) ~ Int) =>
AdjacencyMap a -> AdjacencyIntMap
toAdjacencyIntMapTranspose = forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => AdjacencyMap a -> AdjacencyMap a
NAM.transpose
    isDfsForestOf :: Ord (ToVertex (AdjacencyMap a)) =>
Forest (ToVertex (AdjacencyMap a)) -> AdjacencyMap a -> Bool
isDfsForestOf Forest (ToVertex (AdjacencyMap a))
f            = forall t.
(ToGraph t, Ord (ToVertex t)) =>
Forest (ToVertex t) -> t -> Bool
isDfsForestOf Forest (ToVertex (AdjacencyMap a))
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
toAdjacencyMap
    isTopSortOf :: Ord (ToVertex (AdjacencyMap a)) =>
[ToVertex (AdjacencyMap a)] -> AdjacencyMap a -> Bool
isTopSortOf [ToVertex (AdjacencyMap a)]
x              = forall t.
(ToGraph t, Ord (ToVertex t)) =>
[ToVertex t] -> t -> Bool
isTopSortOf [ToVertex (AdjacencyMap a)]
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 :: forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMap = forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 :: forall t. (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
adjacencyIntMap = AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 :: forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> Map (ToVertex t) (Set (ToVertex t))
adjacencyMapTranspose = forall a. AdjacencyMap a -> Map a (Set a)
AM.adjacencyMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 :: forall t. (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
adjacencyIntMapTranspose = AdjacencyIntMap -> IntMap IntSet
AIM.adjacencyIntMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
toAdjacencyIntMapTranspose