-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph
-- 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 core data type 'Graph' and associated algorithms.
-- For graphs that are known to be /non-empty/ at compile time, see
-- "Algebra.Graph.NonEmpty". 'Graph' is an instance of type classes defined in
-- modules "Algebra.Graph.Class" and "Algebra.Graph.HigherKinded.Class", which
-- can be used for polymorphic graph construction and manipulation.
--
-----------------------------------------------------------------------------
module Algebra.Graph (
    -- * Algebraic data type for graphs
    Graph (..),

    -- * Basic graph construction primitives
    empty, vertex, edge, overlay, connect, vertices, edges, overlays, connects,

    -- * Graph folding
    foldg, buildg,

    -- * Relations on graphs
    isSubgraphOf, (===),

    -- * Graph properties
    isEmpty, size, hasVertex, hasEdge, vertexCount, edgeCount, vertexList,
    edgeList, vertexSet, edgeSet, adjacencyList,

    -- * Standard families of graphs
    path, circuit, clique, biclique, star, stars, tree, forest, mesh, torus,
    deBruijn,

    -- * Graph transformation
    removeVertex, removeEdge, replaceVertex, mergeVertices, splitVertex,
    transpose, induce, induceJust, simplify, sparsify, sparsifyKL,

    -- * Graph composition
    compose, box,

    -- * Context
    Context (..), context
    ) where

import Control.Applicative (Alternative)
import Control.DeepSeq
import Control.Monad (MonadPlus (..))
import Control.Monad.Trans.State (runState, get, put)
import Data.Foldable (toList)
import Data.Maybe (fromMaybe)
import Data.String
import Data.Tree
import GHC.Generics

import Algebra.Graph.Internal

import qualified Control.Applicative
import qualified Algebra.Graph.AdjacencyMap    as AM
import qualified Algebra.Graph.AdjacencyIntMap as AIM
import qualified Data.Graph                    as KL
import qualified Data.IntSet                   as IntSet
import qualified Data.Set                      as Set
import qualified Data.Tree                     as Tree
import qualified GHC.Exts                      as Exts

{-| The 'Graph' data type is a deep embedding of the core graph construction
primitives 'empty', 'vertex', 'overlay' and 'connect'. We define a 'Num'
instance as a convenient notation for working with graphs:

@
0           == 'vertex' 0
1 + 2       == 'overlay' ('vertex' 1) ('vertex' 2)
1 * 2       == 'connect' ('vertex' 1) ('vertex' 2)
1 + 2 * 3   == 'overlay' ('vertex' 1) ('connect' ('vertex' 2) ('vertex' 3))
1 * (2 + 3) == 'connect' ('vertex' 1) ('overlay' ('vertex' 2) ('vertex' 3))
@

__Note:__ the 'Num' instance does not satisfy several "customary laws" of 'Num',
which dictate that 'fromInteger' @0@ and 'fromInteger' @1@ should act as
additive and multiplicative identities, and 'negate' as additive inverse.
Nevertheless, overloading 'fromInteger', '+' and '*' is very convenient when
working with algebraic graphs; we hope that in future Haskell's Prelude will
provide a more fine-grained class hierarchy for algebraic structures, which we
would be able to utilise without violating any laws.

The 'Eq' instance is currently implemented using the 'AM.AdjacencyMap' as the
/canonical graph representation/ and satisfies all axioms of algebraic graphs:

    * 'overlay' is commutative and associative:

        >       x + y == y + x
        > x + (y + z) == (x + y) + z

    * 'connect' is associative and has 'empty' as the identity:

        >   x * empty == x
        >   empty * x == x
        > x * (y * z) == (x * y) * z

    * 'connect' distributes over 'overlay':

        > x * (y + z) == x * y + x * z
        > (x + y) * z == x * z + y * z

    * 'connect' can be decomposed:

        > x * y * z == x * y + x * z + y * z

The following useful theorems can be proved from the above set of axioms.

    * 'overlay' has 'empty' as the identity and is idempotent:

        >   x + empty == x
        >   empty + x == x
        >       x + x == x

    * Absorption and saturation of 'connect':

        > x * y + x + y == x * y
        >     x * x * x == x * x

When specifying the time and memory complexity of graph algorithms, /n/ will
denote the number of vertices in the graph, /m/ will denote the number of
edges in the graph, and /s/ will denote the /size/ of the corresponding
'Graph' expression. For example, if @g@ is a 'Graph' then /n/, /m/ and /s/ can
be computed as follows:

@n == 'vertexCount' g
m == 'edgeCount' g
s == 'size' g@

Note that 'size' counts all leaves of the expression:

@'vertexCount' 'empty'           == 0
'size'        'empty'           == 1
'vertexCount' ('vertex' x)      == 1
'size'        ('vertex' x)      == 1
'vertexCount' ('empty' + 'empty') == 0
'size'        ('empty' + 'empty') == 2@

Converting a 'Graph' to the corresponding 'AM.AdjacencyMap' takes /O(s + m * log(m))/
time and /O(s + m)/ memory. This is also the complexity of the graph equality
test, because it is currently implemented by converting graph expressions to
canonical representations based on adjacency maps.

The total order on graphs is defined using /size-lexicographic/ comparison:

* Compare the number of vertices. In case of a tie, continue.
* Compare the sets of vertices. In case of a tie, continue.
* Compare the number of edges. In case of a tie, continue.
* Compare the sets of edges.

Here are a few examples:

@'vertex' 1 < 'vertex' 2
'vertex' 3 < 'edge' 1 2
'vertex' 1 < 'edge' 1 1
'edge' 1 1 < 'edge' 1 2
'edge' 1 2 < 'edge' 1 1 + 'edge' 2 2
'edge' 1 2 < 'edge' 1 3@

Note that the resulting order refines the 'isSubgraphOf' relation and is
compatible with 'overlay' and 'connect' operations:

@'isSubgraphOf' x y ==> x <= y@

@'empty' <= x
x     <= x + y
x + y <= x * y@

Deforestation (fusion) is implemented for some functions in this module. This
means that when a function tagged as a \"good producer\" is composed with a
function tagged as a \"good consumer\", the intermediate structure will not be
built.
-}
data Graph a = Empty
             | Vertex a
             | Overlay (Graph a) (Graph a)
             | Connect (Graph a) (Graph a)
             deriving (Int -> Graph a -> ShowS
[Graph a] -> ShowS
Graph a -> String
(Int -> Graph a -> ShowS)
-> (Graph a -> String) -> ([Graph a] -> ShowS) -> Show (Graph a)
forall a. Show a => Int -> Graph a -> ShowS
forall a. Show a => [Graph a] -> ShowS
forall a. Show a => Graph a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Graph a] -> ShowS
$cshowList :: forall a. Show a => [Graph a] -> ShowS
show :: Graph a -> String
$cshow :: forall a. Show a => Graph a -> String
showsPrec :: Int -> Graph a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Graph a -> ShowS
Show, (forall x. Graph a -> Rep (Graph a) x)
-> (forall x. Rep (Graph a) x -> Graph a) -> Generic (Graph a)
forall x. Rep (Graph a) x -> Graph a
forall x. Graph a -> Rep (Graph a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Graph a) x -> Graph a
forall a x. Graph a -> Rep (Graph a) x
$cto :: forall a x. Rep (Graph a) x -> Graph a
$cfrom :: forall a x. Graph a -> Rep (Graph a) x
Generic)

{- Note [Functions for rewrite rules]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This module contains several functions whose only purpose is to guide GHC
rewrite rules. The names of all such functions are suffixed with "R" so that it
is easier to distinguish them from others.

Why do we need them?

These functions are annotated with carefully chosen GHC pragmas that control
inlining, which would be impossible or unreliable if we used standard functions
instead. For example, the function 'eqR' has the following annotations:

    INLINE [2] eqR
    RULES "eqR/Int" eqR = eqIntR

The above tells GHC to rewrite 'eqR' to faster 'eqIntR' if possible (if the
types match), and -- importantly -- not to inline 'eqR' too early, before the
rewrite rule had a chance to fire.

We could have written the following rule instead:

    RULES "eqIntR" (==) = eqIntR

But that would have to rely on appropriate inlining behaviour of (==) which is
not under our control. We therefore choose the safe and more explicit path of
creating our own intermediate functions for guiding rewrite rules when needed.
-}

-- | 'fmap' is a good consumer and producer.
instance Functor Graph where
    fmap :: (a -> b) -> Graph a -> Graph b
fmap a -> b
f Graph a
g = Graph a
g Graph a -> (a -> Graph b) -> Graph b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (b -> Graph b
forall a. a -> Graph a
vertex (b -> Graph b) -> (a -> b) -> a -> Graph b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f)
    {-# INLINE fmap #-}

instance NFData a => NFData (Graph a) where
    rnf :: Graph a -> ()
rnf Graph a
Empty         = ()
    rnf (Vertex  a
x  ) = a -> ()
forall a. NFData a => a -> ()
rnf a
x
    rnf (Overlay Graph a
x Graph a
y) = Graph a -> ()
forall a. NFData a => a -> ()
rnf Graph a
x () -> () -> ()
`seq` Graph a -> ()
forall a. NFData a => a -> ()
rnf Graph a
y
    rnf (Connect Graph a
x Graph a
y) = Graph a -> ()
forall a. NFData a => a -> ()
rnf Graph a
x () -> () -> ()
`seq` Graph a -> ()
forall a. NFData a => a -> ()
rnf Graph a
y

-- | __Note:__ this does not satisfy the usual ring laws; see 'Graph' for more
-- details.
instance Num a => Num (Graph a) where
    fromInteger :: Integer -> Graph a
fromInteger = a -> Graph a
forall a. a -> Graph a
Vertex (a -> Graph a) -> (Integer -> a) -> Integer -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> a
forall a. Num a => Integer -> a
fromInteger
    + :: Graph a -> Graph a -> Graph a
(+)         = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay
    * :: Graph a -> Graph a -> Graph a
(*)         = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect
    signum :: Graph a -> Graph a
signum      = Graph a -> Graph a -> Graph a
forall a b. a -> b -> a
const Graph a
forall a. Graph a
Empty
    abs :: Graph a -> Graph a
abs         = Graph a -> Graph a
forall a. a -> a
id
    negate :: Graph a -> Graph a
negate      = Graph a -> Graph a
forall a. a -> a
id

instance IsString a => IsString (Graph a) where
    fromString :: String -> Graph a
fromString = a -> Graph a
forall a. a -> Graph a
Vertex (a -> Graph a) -> (String -> a) -> String -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> a
forall a. IsString a => String -> a
fromString

-- | `==` is a good consumer of both arguments.
instance Ord a => Eq (Graph a) where
    == :: Graph a -> Graph a -> Bool
(==) = Graph a -> Graph a -> Bool
forall a. Ord a => Graph a -> Graph a -> Bool
eqR

-- | 'compare' is a good consumer of both arguments.
instance Ord a => Ord (Graph a) where
    compare :: Graph a -> Graph a -> Ordering
compare = Graph a -> Graph a -> Ordering
forall a. Ord a => Graph a -> Graph a -> Ordering
ordR

-- TODO: Find a more efficient equality check. Note that assuming the Strong
-- Exponential Time Hypothesis (SETH), it is impossible to compare two algebraic
-- graphs in O(s^1.99), i.e. a quadratic algorithm is the best one can hope for.

-- Check if two graphs are equal by converting them to their adjacency maps.
eqR :: Ord a => Graph a -> Graph a -> Bool
eqR :: Graph a -> Graph a -> Bool
eqR Graph a
x Graph a
y = Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
x AdjacencyMap a -> AdjacencyMap a -> Bool
forall a. Eq a => a -> a -> Bool
== Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
y
{-# INLINE [2] eqR #-}
{-# RULES "eqR/Int" eqR = eqIntR #-}

-- Like 'eqR' but specialised for graphs with vertices of type 'Int'.
eqIntR :: Graph Int -> Graph Int -> Bool
eqIntR :: Graph Int -> Graph Int -> Bool
eqIntR Graph Int
x Graph Int
y = Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
x AdjacencyIntMap -> AdjacencyIntMap -> Bool
forall a. Eq a => a -> a -> Bool
== Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
y
{-# INLINE eqIntR #-}

-- TODO: Find a more efficient comparison.
-- Compare two graphs by converting them to their adjacency maps.
ordR :: Ord a => Graph a -> Graph a -> Ordering
ordR :: Graph a -> Graph a -> Ordering
ordR Graph a
x Graph a
y = AdjacencyMap a -> AdjacencyMap a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
x) (Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
y)
{-# INLINE [2] ordR #-}
{-# RULES "ordR/Int" ordR = ordIntR #-}

-- Like 'ordR' but specialised for graphs with vertices of type 'Int'.
ordIntR :: Graph Int -> Graph Int -> Ordering
ordIntR :: Graph Int -> Graph Int -> Ordering
ordIntR Graph Int
x Graph Int
y = AdjacencyIntMap -> AdjacencyIntMap -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
x) (Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
y)
{-# INLINE ordIntR #-}

-- TODO: It should be a good consumer of its second argument too.
-- | `<*>` is a good consumer of its first argument and a good producer.
instance Applicative Graph where
    pure :: a -> Graph a
pure    = a -> Graph a
forall a. a -> Graph a
Vertex
    Graph (a -> b)
f <*> :: Graph (a -> b) -> Graph a -> Graph b
<*> Graph a
x = (forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph b
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph b)
-> (forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph b
forall a b. (a -> b) -> a -> b
$ \r
e b -> r
v r -> r -> r
o r -> r -> r
c -> r
-> ((a -> b) -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph (a -> b)
-> r
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg r
e (\a -> b
w -> r -> (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
foldg r
e (b -> r
v (b -> r) -> (a -> b) -> a -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
w) r -> r -> r
o r -> r -> r
c Graph a
x) r -> r -> r
o r -> r -> r
c Graph (a -> b)
f
    {-# INLINE (<*>) #-}

-- | `>>=` is a good consumer and producer.
instance Monad Graph where
    return :: a -> Graph a
return  = a -> Graph a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    Graph a
g >>= :: Graph a -> (a -> Graph b) -> Graph b
>>= a -> Graph b
f = (forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph b
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph b)
-> (forall r. r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph b
forall a b. (a -> b) -> a -> b
$ \r
e b -> r
v r -> r -> r
o r -> r -> r
c -> r -> (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
foldg r
e ((Graph b -> r) -> (a -> Graph b) -> a -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
composeR (r -> (b -> r) -> (r -> r -> r) -> (r -> r -> r) -> Graph b -> r
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg r
e b -> r
v r -> r -> r
o r -> r -> r
c) a -> Graph b
f) r -> r -> r
o r -> r -> r
c Graph a
g
    {-# INLINE (>>=) #-}

instance Alternative Graph where
    empty :: Graph a
empty = Graph a
forall a. Graph a
Empty
    <|> :: Graph a -> Graph a -> Graph a
(<|>) = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay

instance MonadPlus Graph where
    mzero :: Graph a
mzero = Graph a
forall a. Graph a
Empty
    mplus :: Graph a -> Graph a -> Graph a
mplus = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay

-- | Defined via 'overlay'.
instance Semigroup (Graph a) where
    <> :: Graph a -> Graph a -> Graph a
(<>) = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay

-- | Defined via 'overlay' and 'empty'.
instance Monoid (Graph a) where
    mempty :: Graph a
mempty = Graph a
forall a. Graph a
empty

-- | Construct the /empty graph/. An alias for the constructor 'Empty'.
--
-- @
-- 'isEmpty'     empty == True
-- 'hasVertex' x empty == False
-- 'vertexCount' empty == 0
-- 'edgeCount'   empty == 0
-- 'size'        empty == 1
-- @
empty :: Graph a
empty :: Graph a
empty = Graph a
forall a. Graph a
Empty
{-# INLINE empty #-}

-- | Construct the graph comprising /a single isolated vertex/. An alias for the
-- constructor 'Vertex'.
--
-- @
-- 'isEmpty'     (vertex x) == False
-- 'hasVertex' x (vertex y) == (x == y)
-- 'vertexCount' (vertex x) == 1
-- 'edgeCount'   (vertex x) == 0
-- 'size'        (vertex x) == 1
-- @
vertex :: a -> Graph a
vertex :: a -> Graph a
vertex = a -> Graph a
forall a. a -> Graph a
Vertex
{-# INLINE vertex #-}

-- | Construct the graph comprising /a single edge/.
--
-- @
-- edge x y               == 'connect' ('vertex' x) ('vertex' y)
-- 'hasEdge' x y (edge x y) == True
-- 'edgeCount'   (edge x y) == 1
-- 'vertexCount' (edge 1 1) == 1
-- 'vertexCount' (edge 1 2) == 2
-- @
edge :: a -> a -> Graph a
edge :: a -> a -> Graph a
edge a
x a
y = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
connect (a -> Graph a
forall a. a -> Graph a
vertex a
x) (a -> Graph a
forall a. a -> Graph a
vertex a
y)
{-# INLINE edge #-}

-- | /Overlay/ two graphs. An alias for the constructor 'Overlay'. This is a
-- commutative, associative and idempotent operation with the identity 'empty'.
-- Complexity: /O(1)/ time and memory, /O(s1 + s2)/ size.
--
-- @
-- 'isEmpty'     (overlay x y) == 'isEmpty'   x   && 'isEmpty'   y
-- 'hasVertex' z (overlay x y) == 'hasVertex' z x || 'hasVertex' z y
-- 'vertexCount' (overlay x y) >= 'vertexCount' x
-- 'vertexCount' (overlay x y) <= 'vertexCount' x + 'vertexCount' y
-- 'edgeCount'   (overlay x y) >= 'edgeCount' x
-- 'edgeCount'   (overlay x y) <= 'edgeCount' x   + 'edgeCount' y
-- 'size'        (overlay x y) == 'size' x        + 'size' y
-- 'vertexCount' (overlay 1 2) == 2
-- 'edgeCount'   (overlay 1 2) == 0
-- @
overlay :: Graph a -> Graph a -> Graph a
overlay :: Graph a -> Graph a -> Graph a
overlay = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay
{-# INLINE overlay #-}

-- | /Connect/ two graphs. An alias for the constructor 'Connect'. This is an
-- associative operation with the identity 'empty', which distributes over
-- 'overlay' and obeys the decomposition axiom.
-- Complexity: /O(1)/ time and memory, /O(s1 + s2)/ size. Note that the number
-- of edges in the resulting graph is quadratic with respect to the number of
-- vertices of the arguments: /m = O(m1 + m2 + n1 * n2)/.
--
-- @
-- 'isEmpty'     (connect x y) == 'isEmpty'   x   && 'isEmpty'   y
-- 'hasVertex' z (connect x y) == 'hasVertex' z x || 'hasVertex' z y
-- 'vertexCount' (connect x y) >= 'vertexCount' x
-- 'vertexCount' (connect x y) <= 'vertexCount' x + 'vertexCount' y
-- 'edgeCount'   (connect x y) >= 'edgeCount' x
-- 'edgeCount'   (connect x y) >= 'edgeCount' y
-- 'edgeCount'   (connect x y) >= 'vertexCount' x * 'vertexCount' y
-- 'edgeCount'   (connect x y) <= 'vertexCount' x * 'vertexCount' y + 'edgeCount' x + 'edgeCount' y
-- 'size'        (connect x y) == 'size' x        + 'size' y
-- 'vertexCount' (connect 1 2) == 2
-- 'edgeCount'   (connect 1 2) == 1
-- @
connect :: Graph a -> Graph a -> Graph a
connect :: Graph a -> Graph a -> Graph a
connect = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect
{-# INLINE connect #-}

-- TODO: Simplify the definition to `overlays . map vertex` while preserving
-- goodness properties (which is not trivial since overlays is only a good
-- consumer of lists and not of lists of graphs).
-- | Construct the graph comprising a given list of isolated vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- vertices []            == 'empty'
-- vertices [x]           == 'vertex' x
-- vertices               == 'overlays' . map 'vertex'
-- 'hasVertex' x . vertices == 'elem' x
-- 'vertexCount' . vertices == 'length' . 'Data.List.nub'
-- 'vertexSet'   . vertices == Set.'Set.fromList'
-- @
vertices :: [a] -> Graph a
vertices :: [a] -> Graph a
vertices [a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
_ -> r -> (r -> r -> r) -> (a -> r) -> [a] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
o a -> r
v [a]
xs
{-# INLINE vertices #-}

-- | Construct the graph from a list of edges.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- edges []          == 'empty'
-- edges [(x,y)]     == 'edge' x y
-- edges             == 'overlays' . 'map' ('uncurry' 'edge')
-- 'edgeCount' . edges == 'length' . 'Data.List.nub'
-- @
edges :: [(a, a)] -> Graph a
edges :: [(a, a)] -> Graph a
edges [(a, a)]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> (r -> r -> r) -> ((a, a) -> r) -> [(a, a)] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
o (\(a
x, a
y) -> r -> r -> r
c (a -> r
v a
x) (a -> r
v a
y)) [(a, a)]
xs
{-# INLINE edges #-}

-- | Overlay a given list of graphs.
-- Complexity: /O(L)/ time and memory, and /O(S)/ size, where /L/ is the length
-- of the given list, and /S/ is the sum of sizes of the graphs in the list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- overlays []        == 'empty'
-- overlays [x]       == x
-- overlays [x,y]     == 'overlay' x y
-- overlays           == 'foldr' 'overlay' 'empty'
-- 'isEmpty' . overlays == 'all' 'isEmpty'
-- @
overlays :: [Graph a] -> Graph a
overlays :: [Graph a] -> Graph a
overlays [Graph a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> (r -> r -> r) -> (Graph a -> r) -> [Graph a] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
o (r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c) [Graph a]
xs
{-# INLINE overlays #-}

-- | Connect a given list of graphs.
-- Complexity: /O(L)/ time and memory, and /O(S)/ size, where /L/ is the length
-- of the given list, and /S/ is the sum of sizes of the graphs in the list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- connects []        == 'empty'
-- connects [x]       == x
-- connects [x,y]     == 'connect' x y
-- connects           == 'foldr' 'connect' 'empty'
-- 'isEmpty' . connects == 'all' 'isEmpty'
-- @
connects :: [Graph a] -> Graph a
connects :: [Graph a] -> Graph a
connects [Graph a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> (r -> r -> r) -> (Graph a -> r) -> [Graph a] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
c (r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c) [Graph a]
xs
{-# INLINE connects #-}

-- Safe version of foldr with a map (the composition is optimized)
-- This is a good consumer of lists.
combineR :: c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR :: c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR c
e c -> c -> c
o a -> c
f = c -> Maybe c -> c
forall a. a -> Maybe a -> a
fromMaybe c
e (Maybe c -> c) -> ([a] -> Maybe c) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> c -> c) -> [c] -> Maybe c
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe c -> c -> c
o ([c] -> Maybe c) -> ([a] -> [c]) -> [a] -> Maybe c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> c) -> [a] -> [c]
forall a b. (a -> b) -> [a] -> [b]
map a -> c
f
{-# INLINE combineR #-}

-- | Generalised 'Graph' folding: recursively collapse a 'Graph' by applying
-- the provided functions to the leaves and internal nodes of the expression.
-- The order of arguments is: empty, vertex, overlay and connect.
-- Complexity: /O(s)/ applications of the given functions. As an example, the
-- complexity of 'size' is /O(s)/, since 'const' and '+' have constant costs.
--
-- Good consumer.
--
-- @
-- foldg 'empty' 'vertex'        'overlay' 'connect'        == id
-- foldg 'empty' 'vertex'        'overlay' ('flip' 'connect') == 'transpose'
-- foldg 1     ('const' 1)     (+)     (+)            == 'size'
-- foldg True  ('const' False) (&&)    (&&)           == 'isEmpty'
-- foldg False (== x)        (||)    (||)           == 'hasVertex' x
-- @
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg b
e a -> b
v b -> b -> b
o b -> b -> b
c = Graph a -> b
go
  where
    go :: Graph a -> b
go Graph a
Empty         = b
e
    go (Vertex  a
x  ) = a -> b
v a
x
    go (Overlay Graph a
x Graph a
y) = b -> b -> b
o (Graph a -> b
go Graph a
x) (Graph a -> b
go Graph a
y)
    go (Connect Graph a
x Graph a
y) = b -> b -> b
c (Graph a -> b
go Graph a
x) (Graph a -> b
go Graph a
y)
{-# INLINE [0] foldg #-}

{-# RULES

"foldg/Empty"   forall e v o c.
    foldg e v o c Empty = e

"foldg/Vertex"  forall e v o c x.
    foldg e v o c (Vertex x) = v x

"foldg/Overlay" forall e v o c x y.
    foldg e v o c (Overlay x y) = o (foldg e v o c x) (foldg e v o c y)

"foldg/Connect" forall e v o c x y.
    foldg e v o c (Connect x y) = c (foldg e v o c x) (foldg e v o c y)

#-}

-- | Build a graph given an interpretation of the four graph construction
-- primitives 'empty', 'vertex', 'overlay' and 'connect', in this order. See
-- examples for further clarification.
--
-- Functions expressed with 'buildg' are good producers.
--
-- @
-- buildg f                                                   == f 'empty' 'vertex' 'overlay' 'connect'
-- buildg (\\e _ _ _ -> e)                                     == 'empty'
-- buildg (\\_ v _ _ -> v x)                                   == 'vertex' x
-- buildg (\\e v o c -> o ('foldg' e v o c x) ('foldg' e v o c y)) == 'overlay' x y
-- buildg (\\e v o c -> c ('foldg' e v o c x) ('foldg' e v o c y)) == 'connect' x y
-- buildg (\\e v o _ -> 'foldr' o e ('map' v xs))                  == 'vertices' xs
-- buildg (\\e v o c -> 'foldg' e v o ('flip' c) g)                == 'transpose' g
-- 'foldg' e v o c (buildg f)                                   == f e v o c
-- @
buildg :: (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r) -> Graph a
buildg :: (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r
f = Graph a
-> (a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> Graph a
forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r
f Graph a
forall a. Graph a
Empty a -> Graph a
forall a. a -> Graph a
Vertex Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect
{-# INLINE [1] buildg #-}

-- | The 'isSubgraphOf' function takes two graphs and returns 'True' if the
-- first graph is a /subgraph/ of the second.
-- Complexity: /O(s + m * log(m))/ time. Note that the number of edges /m/ of a
-- graph can be quadratic with respect to the expression size /s/.
--
-- Good consumer of both arguments.
--
-- @
-- isSubgraphOf 'empty'         x             ==  True
-- isSubgraphOf ('vertex' x)    'empty'         ==  False
-- isSubgraphOf x             ('overlay' x y) ==  True
-- isSubgraphOf ('overlay' x y) ('connect' x y) ==  True
-- isSubgraphOf ('path' xs)     ('circuit' xs)  ==  True
-- isSubgraphOf x y                         ==> x <= y
-- @
isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
isSubgraphOf :: Graph a -> Graph a -> Bool
isSubgraphOf Graph a
x Graph a
y = AdjacencyMap a -> AdjacencyMap a -> Bool
forall a. Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool
AM.isSubgraphOf (Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
x) (Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
y)
{-# INLINE [2] isSubgraphOf #-}
{-# RULES "isSubgraphOf/Int" isSubgraphOf = isSubgraphOfIntR #-}

-- Like 'isSubgraphOf' but specialised for graphs with vertices of type 'Int'.
isSubgraphOfIntR :: Graph Int -> Graph Int -> Bool
isSubgraphOfIntR :: Graph Int -> Graph Int -> Bool
isSubgraphOfIntR Graph Int
x Graph Int
y = AdjacencyIntMap -> AdjacencyIntMap -> Bool
AIM.isSubgraphOf (Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
x) (Graph Int -> AdjacencyIntMap
toAdjacencyIntMap Graph Int
y)
{-# INLINE isSubgraphOfIntR #-}

-- | Structural equality on graph expressions.
-- Complexity: /O(s)/ time.
--
-- @
--     x === x         == True
--     x === x + 'empty' == False
-- x + y === x + y     == True
-- 1 + 2 === 2 + 1     == False
-- x + y === x * y     == False
-- @
(===) :: Eq a => Graph a -> Graph a -> Bool
Graph a
Empty           === :: Graph a -> Graph a -> Bool
=== Graph a
Empty           = Bool
True
(Vertex  a
x1   ) === (Vertex  a
x2   ) = a
x1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==  a
x2
(Overlay Graph a
x1 Graph a
y1) === (Overlay Graph a
x2 Graph a
y2) = Graph a
x1 Graph a -> Graph a -> Bool
forall a. Eq a => Graph a -> Graph a -> Bool
=== Graph a
x2 Bool -> Bool -> Bool
&& Graph a
y1 Graph a -> Graph a -> Bool
forall a. Eq a => Graph a -> Graph a -> Bool
=== Graph a
y2
(Connect Graph a
x1 Graph a
y1) === (Connect Graph a
x2 Graph a
y2) = Graph a
x1 Graph a -> Graph a -> Bool
forall a. Eq a => Graph a -> Graph a -> Bool
=== Graph a
x2 Bool -> Bool -> Bool
&& Graph a
y1 Graph a -> Graph a -> Bool
forall a. Eq a => Graph a -> Graph a -> Bool
=== Graph a
y2
Graph a
_               === Graph a
_               = Bool
False
{-# SPECIALISE (===) :: Graph Int -> Graph Int -> Bool #-}

infix 4 ===

-- | Check if a graph is empty.
-- Complexity: /O(s)/ time.
--
-- Good consumer.
--
-- @
-- isEmpty 'empty'                       == True
-- isEmpty ('overlay' 'empty' 'empty')       == True
-- isEmpty ('vertex' x)                  == False
-- isEmpty ('removeVertex' x $ 'vertex' x) == True
-- isEmpty ('removeEdge' x y $ 'edge' x y) == False
-- @
isEmpty :: Graph a -> Bool
isEmpty :: Graph a -> Bool
isEmpty = Bool
-> (a -> Bool)
-> (Bool -> Bool -> Bool)
-> (Bool -> Bool -> Bool)
-> Graph a
-> Bool
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Bool
True (Bool -> a -> Bool
forall a b. a -> b -> a
const Bool
False) Bool -> Bool -> Bool
(&&) Bool -> Bool -> Bool
(&&)
{-# INLINE isEmpty #-}

-- | The /size/ of a graph, i.e. the number of leaves of the expression
-- including 'empty' leaves.
-- Complexity: /O(s)/ time.
--
-- Good consumer.
--
-- @
-- size 'empty'         == 1
-- size ('vertex' x)    == 1
-- size ('overlay' x y) == size x + size y
-- size ('connect' x y) == size x + size y
-- size x             >= 1
-- size x             >= 'vertexCount' x
-- @
size :: Graph a -> Int
size :: Graph a -> Int
size = Int
-> (a -> Int)
-> (Int -> Int -> Int)
-> (Int -> Int -> Int)
-> Graph a
-> Int
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Int
1 (Int -> a -> Int
forall a b. a -> b -> a
const Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int -> Int -> Int
forall a. Num a => a -> a -> a
(+)
{-# INLINE size #-}

-- | Check if a graph contains a given vertex.
-- Complexity: /O(s)/ time.
--
-- Good consumer.
--
-- @
-- hasVertex x 'empty'            == False
-- hasVertex x ('vertex' y)       == (x == y)
-- hasVertex x . 'removeVertex' x == 'const' False
-- @
hasVertex :: Eq a => a -> Graph a -> Bool
hasVertex :: a -> Graph a -> Bool
hasVertex a
x = Bool
-> (a -> Bool)
-> (Bool -> Bool -> Bool)
-> (Bool -> Bool -> Bool)
-> Graph a
-> Bool
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Bool
False (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
x) Bool -> Bool -> Bool
(||) Bool -> Bool -> Bool
(||)
{-# INLINE hasVertex #-}
{-# SPECIALISE hasVertex :: Int -> Graph Int -> Bool #-}

{- Note [The implementation of hasEdge]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

We fold a graph into a function of type Int -> Int where the Int stands for the
number of vertices of the specified edge that have been matched so far. The edge
belongs to the graph if we reach the number 2. Note that this algorithm can be
generalised to algebraic graphs of higher dimensions, e.g. we can similarly find
3-edges (triangles), 4-edges (tetrahedra), and k-edges in O(s) time.

The four graph constructors are interpreted as follows:

  * Empty       : the matching number is unchanged;
  * Vertex x    : if x matches the next vertex, the number is incremented;
  * Overlay x y : pick the best match in the two subexpressions;
  * Connect x y : match the subexpressions one after another.

Note that in the last two cases we can (and do) short-circuit the computation as
soon as the edge is fully matched in one of the subexpressions.
-}

-- | Check if a graph contains a given edge.
-- Complexity: /O(s)/ time.
--
-- Good consumer.
--
-- @
-- hasEdge x y 'empty'            == False
-- hasEdge x y ('vertex' z)       == False
-- hasEdge x y ('edge' x y)       == True
-- hasEdge x y . 'removeEdge' x y == 'const' False
-- hasEdge x y                  == 'elem' (x,y) . 'edgeList'
-- @
hasEdge :: Eq a => a -> a -> Graph a -> Bool
hasEdge :: a -> a -> Graph a -> Bool
hasEdge a
s a
t Graph a
g = (Int -> Int)
-> (a -> Int -> Int)
-> ((Int -> Int) -> (Int -> Int) -> Int -> Int)
-> ((Int -> Int) -> (Int -> Int) -> Int -> Int)
-> Graph a
-> Int
-> Int
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Int -> Int
forall a. a -> a
id a -> Int -> Int
v (Int -> Int) -> (Int -> Int) -> Int -> Int
forall a t. (Eq a, Num a) => (t -> a) -> (t -> Int) -> t -> Int
o (Int -> Int) -> (Int -> Int) -> Int -> Int
forall t p t.
(Eq t, Num t, Num p) =>
(t -> t) -> (t -> p) -> t -> p
c Graph a
g Int
0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2
  where
    v :: a -> Int -> Int
v a
x Int
0   = if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
s then Int
1 else Int
0
    v a
x Int
_   = if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
t then Int
2 else Int
1
    o :: (t -> a) -> (t -> Int) -> t -> Int
o t -> a
x t -> Int
y t
a = case t -> a
x t
a of
        a
0 -> t -> Int
y t
a
        a
1 -> if t -> Int
y t
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2 then Int
2 else Int
1
        a
_ -> Int
2 :: Int
    c :: (t -> t) -> (t -> p) -> t -> p
c t -> t
x t -> p
y t
a = case t -> t
x t
a of { t
2 -> p
2; t
res -> t -> p
y t
res }
{-# INLINE hasEdge #-}
{-# SPECIALISE hasEdge :: Int -> Int -> Graph Int -> Bool #-}

-- | The number of vertices in a graph.
-- Complexity: /O(s * log(n))/ time.
--
-- Good consumer.
--
-- @
-- vertexCount 'empty'             ==  0
-- vertexCount ('vertex' x)        ==  1
-- vertexCount                   ==  'length' . 'vertexList'
-- vertexCount x \< vertexCount y ==> x \< y
-- @
vertexCount :: Ord a => Graph a -> Int
vertexCount :: Graph a -> Int
vertexCount = Set a -> Int
forall a. Set a -> Int
Set.size (Set a -> Int) -> (Graph a -> Set a) -> Graph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Set a
forall a. Ord a => Graph a -> Set a
vertexSet
{-# INLINE [2] vertexCount #-}
{-# RULES "vertexCount/Int" vertexCount = vertexIntCountR #-}

-- Like 'vertexCount' but specialised for graphs with vertices of type 'Int'.
vertexIntCountR :: Graph Int -> Int
vertexIntCountR :: Graph Int -> Int
vertexIntCountR = IntSet -> Int
IntSet.size (IntSet -> Int) -> (Graph Int -> IntSet) -> Graph Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> IntSet
vertexIntSetR
{-# INLINE vertexIntCountR #-}

-- | The number of edges in a graph.
-- Complexity: /O(s + m * log(m))/ time. Note that the number of edges /m/ of a
-- graph can be quadratic with respect to the expression size /s/.
--
-- Good consumer.
--
-- @
-- edgeCount 'empty'      == 0
-- edgeCount ('vertex' x) == 0
-- edgeCount ('edge' x y) == 1
-- edgeCount            == 'length' . 'edgeList'
-- @
edgeCount :: Ord a => Graph a -> Int
edgeCount :: Graph a -> Int
edgeCount = AdjacencyMap a -> Int
forall a. AdjacencyMap a -> Int
AM.edgeCount (AdjacencyMap a -> Int)
-> (Graph a -> AdjacencyMap a) -> Graph a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap
{-# INLINE [2] edgeCount #-}
{-# RULES "edgeCount/Int" edgeCount = edgeCountIntR #-}

-- Like 'edgeCount' but specialised for graphs with vertices of type 'Int'.
edgeCountIntR :: Graph Int -> Int
edgeCountIntR :: Graph Int -> Int
edgeCountIntR = AdjacencyIntMap -> Int
AIM.edgeCount (AdjacencyIntMap -> Int)
-> (Graph Int -> AdjacencyIntMap) -> Graph Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> AdjacencyIntMap
toAdjacencyIntMap
{-# INLINE edgeCountIntR #-}

-- | The sorted list of vertices of a given graph.
-- Complexity: /O(s * log(n))/ time and /O(n)/ memory.
--
-- Good consumer of graphs and producer of lists.
--
-- @
-- vertexList 'empty'      == []
-- vertexList ('vertex' x) == [x]
-- vertexList . 'vertices' == 'Data.List.nub' . 'Data.List.sort'
-- @
vertexList :: Ord a => Graph a -> [a]
vertexList :: Graph a -> [a]
vertexList = Set a -> [a]
forall a. Set a -> [a]
Set.toAscList (Set a -> [a]) -> (Graph a -> Set a) -> Graph a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Set a
forall a. Ord a => Graph a -> Set a
vertexSet
{-# INLINE [2] vertexList #-}
{-# RULES "vertexList/Int" vertexList = vertexIntListR #-}

-- Like 'vertexList' but specialised for graphs with vertices of type 'Int'.
vertexIntListR :: Graph Int -> [Int]
vertexIntListR :: Graph Int -> [Int]
vertexIntListR = IntSet -> [Int]
IntSet.toList (IntSet -> [Int]) -> (Graph Int -> IntSet) -> Graph Int -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> IntSet
vertexIntSetR
{-# INLINE vertexIntListR #-}

-- | The sorted list of edges of a graph.
-- Complexity: /O(s + m * log(m))/ time and /O(m)/ memory. Note that the number of
-- edges /m/ of a graph can be quadratic with respect to the expression size /s/.
--
-- Good consumer of graphs and producer of lists.
--
-- @
-- edgeList 'empty'          == []
-- edgeList ('vertex' x)     == []
-- edgeList ('edge' x y)     == [(x,y)]
-- edgeList ('star' 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . 'edges'        == 'Data.List.nub' . 'Data.List.sort'
-- edgeList . 'transpose'    == 'Data.List.sort' . 'map' 'Data.Tuple.swap' . edgeList
-- @
edgeList :: Ord a => Graph a -> [(a, a)]
edgeList :: Graph a -> [(a, a)]
edgeList = AdjacencyMap a -> [(a, a)]
forall a. AdjacencyMap a -> [(a, a)]
AM.edgeList (AdjacencyMap a -> [(a, a)])
-> (Graph a -> AdjacencyMap a) -> Graph a -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap
{-# INLINE [2] edgeList #-}
{-# RULES "edgeList/Int" edgeList = edgeIntListR #-}

-- Like 'edgeList' but specialised for graphs with vertices of type 'Int'.
edgeIntListR :: Graph Int -> [(Int, Int)]
edgeIntListR :: Graph Int -> [(Int, Int)]
edgeIntListR = AdjacencyIntMap -> [(Int, Int)]
AIM.edgeList (AdjacencyIntMap -> [(Int, Int)])
-> (Graph Int -> AdjacencyIntMap) -> Graph Int -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> AdjacencyIntMap
toAdjacencyIntMap
{-# INLINE edgeIntListR #-}

-- | The set of vertices of a given graph.
-- Complexity: /O(s * log(n))/ time and /O(n)/ memory.
--
-- Good consumer.
--
-- @
-- vertexSet 'empty'      == Set.'Set.empty'
-- vertexSet . 'vertex'   == Set.'Set.singleton'
-- vertexSet . 'vertices' == Set.'Set.fromList'
-- @
vertexSet :: Ord a => Graph a -> Set.Set a
vertexSet :: Graph a -> Set a
vertexSet = Set a
-> (a -> Set a)
-> (Set a -> Set a -> Set a)
-> (Set a -> Set a -> Set a)
-> Graph a
-> Set a
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Set a
forall a. Set a
Set.empty a -> Set a
forall a. a -> Set a
Set.singleton Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.union Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.union
{-# INLINE vertexSet #-}

-- Like 'vertexSet' but specialised for graphs with vertices of type 'Int'.
vertexIntSetR :: Graph Int -> IntSet.IntSet
vertexIntSetR :: Graph Int -> IntSet
vertexIntSetR = IntSet
-> (Int -> IntSet)
-> (IntSet -> IntSet -> IntSet)
-> (IntSet -> IntSet -> IntSet)
-> Graph Int
-> IntSet
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg IntSet
IntSet.empty Int -> IntSet
IntSet.singleton IntSet -> IntSet -> IntSet
IntSet.union IntSet -> IntSet -> IntSet
IntSet.union
{-# INLINE vertexIntSetR #-}

-- | The set of edges of a given graph.
-- Complexity: /O(s * log(m))/ time and /O(m)/ memory.
--
-- Good consumer.
--
-- @
-- edgeSet 'empty'      == Set.'Set.empty'
-- edgeSet ('vertex' x) == Set.'Set.empty'
-- edgeSet ('edge' x y) == Set.'Set.singleton' (x,y)
-- edgeSet . 'edges'    == Set.'Set.fromList'
-- @
edgeSet :: Ord a => Graph a -> Set.Set (a, a)
edgeSet :: Graph a -> Set (a, a)
edgeSet = AdjacencyMap a -> Set (a, a)
forall a. Eq a => AdjacencyMap a -> Set (a, a)
AM.edgeSet (AdjacencyMap a -> Set (a, a))
-> (Graph a -> AdjacencyMap a) -> Graph a -> Set (a, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap
{-# INLINE [2] edgeSet #-}
{-# RULES "edgeSet/Int" edgeSet = edgeIntSetR #-}

-- Like 'edgeSet' but specialised for graphs with vertices of type 'Int'.
edgeIntSetR :: Graph Int -> Set.Set (Int,Int)
edgeIntSetR :: Graph Int -> Set (Int, Int)
edgeIntSetR = AdjacencyIntMap -> Set (Int, Int)
AIM.edgeSet (AdjacencyIntMap -> Set (Int, Int))
-> (Graph Int -> AdjacencyIntMap) -> Graph Int -> Set (Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> AdjacencyIntMap
toAdjacencyIntMap
{-# INLINE edgeIntSetR #-}

-- | The sorted /adjacency list/ of a graph.
-- Complexity: /O(n + m)/ time and memory.
--
-- Good consumer.
--
-- @
-- adjacencyList 'empty'          == []
-- adjacencyList ('vertex' x)     == [(x, [])]
-- adjacencyList ('edge' 1 2)     == [(1, [2]), (2, [])]
-- adjacencyList ('star' 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- 'stars' . adjacencyList        == id
-- @
adjacencyList :: Ord a => Graph a -> [(a, [a])]
adjacencyList :: Graph a -> [(a, [a])]
adjacencyList = AdjacencyMap a -> [(a, [a])]
forall a. AdjacencyMap a -> [(a, [a])]
AM.adjacencyList (AdjacencyMap a -> [(a, [a])])
-> (Graph a -> AdjacencyMap a) -> Graph a -> [(a, [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap
{-# INLINE adjacencyList #-}
{-# SPECIALISE adjacencyList :: Graph Int -> [(Int, [Int])] #-}

-- TODO: This is a very inefficient implementation. Find a way to construct an
-- adjacency map directly, without building intermediate representations for all
-- subgraphs.
-- Convert a graph to 'AM.AdjacencyMap'.
toAdjacencyMap :: Ord a => Graph a -> AM.AdjacencyMap a
toAdjacencyMap :: Graph a -> AdjacencyMap a
toAdjacencyMap = AdjacencyMap a
-> (a -> AdjacencyMap a)
-> (AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a)
-> (AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a)
-> Graph a
-> AdjacencyMap a
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg AdjacencyMap a
forall a. AdjacencyMap a
AM.empty a -> AdjacencyMap a
forall a. a -> AdjacencyMap a
AM.vertex AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.overlay AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
forall a.
Ord a =>
AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
AM.connect
{-# INLINE toAdjacencyMap #-}

-- Like @toAdjacencyMap@ but specialised for graphs with vertices of type 'Int'.
toAdjacencyIntMap :: Graph Int -> AIM.AdjacencyIntMap
toAdjacencyIntMap :: Graph Int -> AdjacencyIntMap
toAdjacencyIntMap = AdjacencyIntMap
-> (Int -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> (AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap)
-> Graph Int
-> AdjacencyIntMap
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg AdjacencyIntMap
AIM.empty Int -> AdjacencyIntMap
AIM.vertex AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.overlay AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
AIM.connect
{-# INLINE toAdjacencyIntMap #-}

-- TODO: Make path a good consumer of lists, that is, express it with 'foldr'.
-- This is not straightforward if we want to preserve efficiency.
-- | The /path/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good producer.
--
-- @
-- path []        == 'empty'
-- path [x]       == 'vertex' x
-- path [x,y]     == 'edge' x y
-- path . 'reverse' == 'transpose' . path
-- @
path :: [a] -> Graph a
path :: [a] -> Graph a
path [a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> case [a]
xs of
    []       -> r
e
    [a
x]      -> a -> r
v a
x
    (a
_ : [a]
ys) -> r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c (Graph a -> r) -> Graph a -> r
forall a b. (a -> b) -> a -> b
$ [(a, a)] -> Graph a
forall a. [(a, a)] -> Graph a
edges ([a] -> [a] -> [(a, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
xs [a]
ys)
{-# INLINE path #-}

-- TODO: Make circuit a good consumer of lists, that is, express it with 'foldr'.
-- This is not straightforward if we want to preserve efficiency.
-- | The /circuit/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good producer.
--
-- @
-- circuit []        == 'empty'
-- circuit [x]       == 'edge' x x
-- circuit [x,y]     == 'edges' [(x,y), (y,x)]
-- circuit . 'reverse' == 'transpose' . circuit
-- @
circuit :: [a] -> Graph a
circuit :: [a] -> Graph a
circuit [a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> case [a]
xs of
    []       -> r
e
    (a
x : [a]
xs) -> r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c (Graph a -> r) -> Graph a -> r
forall a b. (a -> b) -> a -> b
$ [a] -> Graph a
forall a. [a] -> Graph a
path ([a] -> Graph a) -> [a] -> Graph a
forall a b. (a -> b) -> a -> b
$ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]
{-# INLINE circuit #-}

-- | The /clique/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- clique []         == 'empty'
-- clique [x]        == 'vertex' x
-- clique [x,y]      == 'edge' x y
-- clique [x,y,z]    == 'edges' [(x,y), (x,z), (y,z)]
-- clique (xs ++ ys) == 'connect' (clique xs) (clique ys)
-- clique . 'reverse'  == 'transpose' . clique
-- @
clique :: [a] -> Graph a
clique :: [a] -> Graph a
clique [a]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
_ r -> r -> r
c -> r -> (r -> r -> r) -> (a -> r) -> [a] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
c a -> r
v [a]
xs
{-# INLINE clique #-}

-- | The /biclique/ on two lists of vertices.
-- Complexity: /O(L1 + L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.
--
-- Good consumer of both arguments and producer of graphs.
--
-- @
-- biclique []      []      == 'empty'
-- biclique [x]     []      == 'vertex' x
-- biclique []      [y]     == 'vertex' y
-- biclique [x1,x2] [y1,y2] == 'edges' [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
-- biclique xs      ys      == 'connect' ('vertices' xs) ('vertices' ys)
-- @
biclique :: [a] -> [a] -> Graph a
biclique :: [a] -> [a] -> Graph a
biclique [a]
xs [a]
ys = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> case (r -> r -> r) -> [r] -> Maybe r
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe r -> r -> r
o ((a -> r) -> [a] -> [r]
forall a b. (a -> b) -> [a] -> [b]
map a -> r
v [a]
xs) of
    Maybe r
Nothing -> r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c (Graph a -> r) -> Graph a -> r
forall a b. (a -> b) -> a -> b
$ [a] -> Graph a
forall a. [a] -> Graph a
vertices [a]
ys
    Just r
xs -> case (r -> r -> r) -> [r] -> Maybe r
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe r -> r -> r
o ((a -> r) -> [a] -> [r]
forall a b. (a -> b) -> [a] -> [b]
map a -> r
v [a]
ys) of
        Maybe r
Nothing -> r
xs
        Just r
ys -> r -> r -> r
c r
xs r
ys
{-# INLINE biclique #-}

-- | The /star/ formed by a centre vertex connected to a list of leaves.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- Good consumer of lists and good producer of graphs.
--
-- @
-- star x []    == 'vertex' x
-- star x [y]   == 'edge' x y
-- star x [y,z] == 'edges' [(x,y), (x,z)]
-- star x ys    == 'connect' ('vertex' x) ('vertices' ys)
-- @
star :: a -> [a] -> Graph a
star :: a -> [a] -> Graph a
star a
x [a]
ys = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
_ a -> r
v r -> r -> r
o r -> r -> r
c -> case (r -> r -> r) -> [r] -> Maybe r
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe r -> r -> r
o ((a -> r) -> [a] -> [r]
forall a b. (a -> b) -> [a] -> [b]
map a -> r
v [a]
ys) of
    Maybe r
Nothing -> a -> r
v a
x
    Just r
ys -> r -> r -> r
c (a -> r
v a
x) r
ys
{-# INLINE star #-}

-- | The /stars/ formed by overlaying a list of 'star's. An inverse of
-- 'adjacencyList'.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the total size of the
-- input.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- stars []                      == 'empty'
-- stars [(x, [])]               == 'vertex' x
-- stars [(x, [y])]              == 'edge' x y
-- stars [(x, ys)]               == 'star' x ys
-- stars                         == 'overlays' . 'map' ('uncurry' 'star')
-- stars . 'adjacencyList'         == id
-- 'overlay' (stars xs) (stars ys) == stars (xs ++ ys)
-- @
stars :: [(a, [a])] -> Graph a
stars :: [(a, [a])] -> Graph a
stars [(a, [a])]
xs = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> (r -> r -> r) -> ((a, [a]) -> r) -> [(a, [a])] -> r
forall c a. c -> (c -> c -> c) -> (a -> c) -> [a] -> c
combineR r
e r -> r -> r
o (r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c (Graph a -> r) -> ((a, [a]) -> Graph a) -> (a, [a]) -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> [a] -> Graph a) -> (a, [a]) -> Graph a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> [a] -> Graph a
forall a. a -> [a] -> Graph a
star) [(a, [a])]
xs
{-# INLINE stars #-}

-- | The /tree graph/ constructed from a given 'Tree.Tree' data structure.
-- Complexity: /O(T)/ time, memory and size, where /T/ is the size of the
-- given tree (i.e. the number of vertices in the tree).
--
-- @
-- tree (Node x [])                                         == 'vertex' x
-- tree (Node x [Node y [Node z []]])                       == 'path' [x,y,z]
-- tree (Node x [Node y [], Node z []])                     == 'star' x [y,z]
-- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == 'edges' [(1,2), (1,3), (3,4), (3,5)]
-- @
tree :: Tree.Tree a -> Graph a
tree :: Tree a -> Graph a
tree (Node a
x []) = a -> Graph a
forall a. a -> Graph a
vertex a
x
tree (Node a
x [Tree a]
f ) = a -> [a] -> Graph a
forall a. a -> [a] -> Graph a
star a
x ((Tree a -> a) -> [Tree a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Tree a -> a
forall a. Tree a -> a
rootLabel [Tree a]
f)
         Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
`overlay` [Tree a] -> Graph a
forall a. Forest a -> Graph a
forest ((Tree a -> Bool) -> [Tree a] -> [Tree a]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Tree a -> Bool) -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Tree a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([Tree a] -> Bool) -> (Tree a -> [Tree a]) -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tree a -> [Tree a]
forall a. Tree a -> [Tree a]
subForest) [Tree a]
f)

-- | The /forest graph/ constructed from a given 'Tree.Forest' data structure.
-- Complexity: /O(F)/ time, memory and size, where /F/ is the size of the
-- given forest (i.e. the number of vertices in the forest).
--
-- @
-- forest []                                                  == 'empty'
-- forest [x]                                                 == 'tree' x
-- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == 'edges' [(1,2), (1,3), (4,5)]
-- forest                                                     == 'overlays' . 'map' 'tree'
-- @
forest :: Tree.Forest a -> Graph a
forest :: Forest a -> Graph a
forest = [Graph a] -> Graph a
forall a. [Graph a] -> Graph a
overlays ([Graph a] -> Graph a)
-> (Forest a -> [Graph a]) -> Forest a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Tree a -> Graph a) -> Forest a -> [Graph a]
forall a b. (a -> b) -> [a] -> [b]
map Tree a -> Graph a
forall a. Tree a -> Graph a
tree

-- | Construct a /mesh graph/ from two lists of vertices.
-- Complexity: /O(L1 * L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.
--
-- @
-- mesh xs     []   == 'empty'
-- mesh []     ys   == 'empty'
-- mesh [x]    [y]  == 'vertex' (x, y)
-- mesh xs     ys   == 'box' ('path' xs) ('path' ys)
-- mesh [1..3] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(2,\'b\')), ((2,\'a\'),(2,\'b\'))
--                           , ((2,\'a\'),(3,\'a\')), ((2,\'b\'),(3,\'b\')), ((3,\'a\'),(3,\'b\')) ]
-- @
mesh :: [a] -> [b] -> Graph (a, b)
mesh :: [a] -> [b] -> Graph (a, b)
mesh []  [b]
_   = Graph (a, b)
forall a. Graph a
empty
mesh [a]
_   []  = Graph (a, b)
forall a. Graph a
empty
mesh [a
x] [b
y] = (a, b) -> Graph (a, b)
forall a. a -> Graph a
vertex (a
x, b
y)
mesh [a]
xs  [b]
ys  = [((a, b), [(a, b)])] -> Graph (a, b)
forall a. [(a, [a])] -> Graph a
stars ([((a, b), [(a, b)])] -> Graph (a, b))
-> [((a, b), [(a, b)])] -> Graph (a, b)
forall a b. (a -> b) -> a -> b
$
       [ ((a
a1, b
b1), [(a
a1, b
b2), (a
a2, b
b1)]) | (a
a1, a
a2) <- [(a, a)]
ix, (b
b1, b
b2) <- [(b, b)]
iy ]
    [((a, b), [(a, b)])]
-> [((a, b), [(a, b)])] -> [((a, b), [(a, b)])]
forall a. [a] -> [a] -> [a]
++ [ ((a
lx, b
y1), [(a
lx, b
y2)]) | (b
y1, b
y2) <- [(b, b)]
iy ]
    [((a, b), [(a, b)])]
-> [((a, b), [(a, b)])] -> [((a, b), [(a, b)])]
forall a. [a] -> [a] -> [a]
++ [ ((a
x1, b
ly), [(a
x2, b
ly)]) | (a
x1, a
x2) <- [(a, a)]
ix ]
  where
    lx :: a
lx = [a] -> a
forall a. [a] -> a
last [a]
xs
    ly :: b
ly = [b] -> b
forall a. [a] -> a
last [b]
ys
    ix :: [(a, a)]
ix = [(a, a)] -> [(a, a)]
forall a. [a] -> [a]
init ([a] -> [(a, a)]
forall a. [a] -> [(a, a)]
pairs [a]
xs)
    iy :: [(b, b)]
iy = [(b, b)] -> [(b, b)]
forall a. [a] -> [a]
init ([b] -> [(b, b)]
forall a. [a] -> [(a, a)]
pairs [b]
ys)

-- | Construct a /torus graph/ from two lists of vertices.
-- Complexity: /O(L1 * L2)/ time, memory and size, where /L1/ and /L2/ are the
-- lengths of the given lists.
--
-- @
-- torus xs    []   == 'empty'
-- torus []    ys   == 'empty'
-- torus [x]   [y]  == 'edge' (x,y) (x,y)
-- torus xs    ys   == 'box' ('circuit' xs) ('circuit' ys)
-- torus [1,2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))
--                           , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ]
-- @
torus :: [a] -> [b] -> Graph (a, b)
torus :: [a] -> [b] -> Graph (a, b)
torus [a]
xs [b]
ys = [((a, b), [(a, b)])] -> Graph (a, b)
forall a. [(a, [a])] -> Graph a
stars
    [ ((a
a1, b
b1), [(a
a1, b
b2), (a
a2, b
b1)]) | (a
a1, a
a2) <- [a] -> [(a, a)]
forall a. [a] -> [(a, a)]
pairs [a]
xs, (b
b1, b
b2) <- [b] -> [(b, b)]
forall a. [a] -> [(a, a)]
pairs [b]
ys ]

-- | Auxiliary function for 'mesh' and 'torus'
pairs :: [a] -> [(a, a)]
pairs :: [a] -> [(a, a)]
pairs [] = []
pairs as :: [a]
as@(a
x:[a]
xs) = [a] -> [a] -> [(a, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
as ([a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x])

-- | Construct a /De Bruijn graph/ of a given non-negative dimension using symbols
-- from a given alphabet.
-- Complexity: /O(A^(D + 1))/ time, memory and size, where /A/ is the size of the
-- alphabet and /D/ is the dimension of the graph.
--
-- @
--           deBruijn 0 xs               == 'edge' [] []
-- n > 0 ==> deBruijn n []               == 'empty'
--           deBruijn 1 [0,1]            == 'edges' [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
--           deBruijn 2 "0"              == 'edge' "00" "00"
--           deBruijn 2 "01"             == 'edges' [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
--                                                , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
--           'transpose'   (deBruijn n xs) == 'fmap' 'reverse' $ deBruijn n xs
--           'vertexCount' (deBruijn n xs) == ('length' $ 'Data.List.nub' xs)^n
-- n > 0 ==> 'edgeCount'   (deBruijn n xs) == ('length' $ 'Data.List.nub' xs)^(n + 1)
-- @
deBruijn :: Int -> [a] -> Graph [a]
deBruijn :: Int -> [a] -> Graph [a]
deBruijn Int
0   [a]
_        = [a] -> [a] -> Graph [a]
forall a. a -> a -> Graph a
edge [] []
deBruijn Int
len [a]
alphabet = Graph (Either [a] [a])
skeleton Graph (Either [a] [a])
-> (Either [a] [a] -> Graph [a]) -> Graph [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Either [a] [a] -> Graph [a]
expand
  where
    overlaps :: [[a]]
overlaps = (Int -> [a]) -> [Int] -> [[a]]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ([a] -> Int -> [a]
forall a b. a -> b -> a
const [a]
alphabet) [Int
2..Int
len]
    skeleton :: Graph (Either [a] [a])
skeleton = [(Either [a] [a], Either [a] [a])] -> Graph (Either [a] [a])
forall a. [(a, a)] -> Graph a
edges    [        ([a] -> Either [a] [a]
forall a b. a -> Either a b
Left [a]
s, [a] -> Either [a] [a]
forall a b. b -> Either a b
Right [a]
s)   | [a]
s <- [[a]]
overlaps ]
    expand :: Either [a] [a] -> Graph [a]
expand Either [a] [a]
v = [[a]] -> Graph [a]
forall a. [a] -> Graph a
vertices [ ([a] -> [a]) -> ([a] -> [a]) -> Either [a] [a] -> [a]
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either ([a
a] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++) ([a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
a]) Either [a] [a]
v | a
a <- [a]
alphabet ]

-- | Remove a vertex from a given graph.
-- Complexity: /O(s)/ time, memory and size.
--
-- Good consumer and producer.
--
-- @
-- removeVertex x ('vertex' x)       == 'empty'
-- removeVertex 1 ('vertex' 2)       == 'vertex' 2
-- removeVertex x ('edge' x x)       == 'empty'
-- removeVertex 1 ('edge' 1 2)       == 'vertex' 2
-- removeVertex x . removeVertex x == removeVertex x
-- @
removeVertex :: Eq a => a -> Graph a -> Graph a
removeVertex :: a -> Graph a -> Graph a
removeVertex a
v = (a -> Bool) -> Graph a -> Graph a
forall a. (a -> Bool) -> Graph a -> Graph a
induce (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
v)
{-# SPECIALISE removeVertex :: Int -> Graph Int -> Graph Int #-}

-- | Remove an edge from a given graph.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- removeEdge x y ('edge' x y)       == 'vertices' [x,y]
-- removeEdge x y . removeEdge x y == removeEdge x y
-- removeEdge x y . 'removeVertex' x == 'removeVertex' x
-- removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
-- removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
-- 'size' (removeEdge x y z)         <= 3 * 'size' z
-- @
removeEdge :: Eq a => a -> a -> Graph a -> Graph a
removeEdge :: a -> a -> Graph a -> Graph a
removeEdge a
s a
t = a -> (a -> Bool) -> (a -> Bool) -> Graph a -> Graph a
forall a.
Eq a =>
a -> (a -> Bool) -> (a -> Bool) -> Graph a -> Graph a
filterContext a
s (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=a
s) (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=a
t)
{-# SPECIALISE removeEdge :: Int -> Int -> Graph Int -> Graph Int #-}

-- TODO: Export
-- Filter vertices in a subgraph context.
filterContext :: Eq a => a -> (a -> Bool) -> (a -> Bool) -> Graph a -> Graph a
filterContext :: a -> (a -> Bool) -> (a -> Bool) -> Graph a -> Graph a
filterContext a
s a -> Bool
i a -> Bool
o Graph a
g = Graph a -> (Context a -> Graph a) -> Maybe (Context a) -> Graph a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Graph a
g Context a -> Graph a
go (Maybe (Context a) -> Graph a) -> Maybe (Context a) -> Graph a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> Graph a -> Maybe (Context a)
forall a. (a -> Bool) -> Graph a -> Maybe (Context a)
context (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
s) Graph a
g
  where
    go :: Context a -> Graph a
go (Context [a]
is [a]
os) = (a -> Bool) -> Graph a -> Graph a
forall a. (a -> Bool) -> Graph a -> Graph a
induce (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=a
s) Graph a
g Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
`overlay` Graph a -> Graph a
forall a. Graph a -> Graph a
transpose (a -> [a] -> Graph a
forall a. a -> [a] -> Graph a
star a
s ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
i [a]
is))
                                        Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
`overlay` a -> [a] -> Graph a
forall a. a -> [a] -> Graph a
star            a
s ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
o [a]
os)
{-# SPECIALISE filterContext :: Int -> (Int -> Bool) -> (Int -> Bool) -> Graph Int -> Graph Int #-}

-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a
-- given 'Graph'. If @y@ already exists, @x@ and @y@ will be merged.
-- Complexity: /O(s)/ time, memory and size.
--
-- Good consumer and producer.
--
-- @
-- replaceVertex x x            == id
-- replaceVertex x y ('vertex' x) == 'vertex' y
-- replaceVertex x y            == 'mergeVertices' (== x) y
-- @
replaceVertex :: Eq a => a -> a -> Graph a -> Graph a
replaceVertex :: a -> a -> Graph a -> Graph a
replaceVertex a
u a
v = (a -> a) -> Graph a -> Graph a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> a) -> Graph a -> Graph a) -> (a -> a) -> Graph a -> Graph a
forall a b. (a -> b) -> a -> b
$ \a
w -> if a
w a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
u then a
v else a
w
{-# INLINE replaceVertex #-}
{-# SPECIALISE replaceVertex :: Int -> Int -> Graph Int -> Graph Int #-}

-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: /O(s)/ time, memory and size, assuming that the predicate takes
-- constant time.
--
-- Good consumer and producer.
--
-- @
-- mergeVertices ('const' False) x    == id
-- mergeVertices (== x) y           == 'replaceVertex' x y
-- mergeVertices 'even' 1 (0 * 2)     == 1 * 1
-- mergeVertices 'odd'  1 (3 + 4 * 5) == 4 * 1
-- @
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
mergeVertices a -> Bool
p a
v = (a -> a) -> Graph a -> Graph a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> a) -> Graph a -> Graph a) -> (a -> a) -> Graph a -> Graph a
forall a b. (a -> b) -> a -> b
$ \a
w -> if a -> Bool
p a
w then a
v else a
w
{-# INLINE mergeVertices #-}

-- | Split a vertex into a list of vertices with the same connectivity.
-- Complexity: /O(s + k * L)/ time, memory and size, where /k/ is the number of
-- occurrences of the vertex in the expression and /L/ is the length of the
-- given list.
--
-- Good consumer of lists and producer of graphs.
--
-- @
-- splitVertex x []                  == 'removeVertex' x
-- splitVertex x [x]                 == id
-- splitVertex x [y]                 == 'replaceVertex' x y
-- splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
-- @
splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a
splitVertex :: a -> [a] -> Graph a -> Graph a
splitVertex a
x [a]
us Graph a
g = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c ->
    let split :: a -> r
split a
y = if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y then r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c ([a] -> Graph a
forall a. [a] -> Graph a
vertices [a]
us) else a -> r
v a
y in
    r -> (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
foldg r
e a -> r
split r -> r -> r
o r -> r -> r
c Graph a
g
{-# INLINE splitVertex #-}
{-# SPECIALISE splitVertex :: Int -> [Int] -> Graph Int -> Graph Int #-}

-- | Transpose a given graph.
-- Complexity: /O(s)/ time, memory and size.
--
-- Good consumer and producer.
--
-- @
-- transpose 'empty'       == 'empty'
-- transpose ('vertex' x)  == 'vertex' x
-- transpose ('edge' x y)  == 'edge' y x
-- transpose . transpose == id
-- transpose ('box' x y)   == 'box' (transpose x) (transpose y)
-- 'edgeList' . transpose  == 'Data.List.sort' . 'map' 'Data.Tuple.swap' . 'edgeList'
-- @
transpose :: Graph a -> Graph a
transpose :: Graph a -> Graph a
transpose Graph a
g = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> (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
foldg r
e a -> r
v r -> r -> r
o ((r -> r -> r) -> r -> r -> r
forall a b c. (a -> b -> c) -> b -> a -> c
flip r -> r -> r
c) Graph a
g
{-# INLINE transpose #-}

-- | Construct the /induced subgraph/ of a given graph by removing the
-- vertices that do not satisfy a given predicate.
-- Complexity: /O(s)/ time, memory and size, assuming that the predicate takes
-- constant time.
--
-- Good consumer and producer.
--
-- @
-- induce ('const' True ) x      == x
-- induce ('const' False) x      == 'empty'
-- induce (/= x)               == 'removeVertex' x
-- induce p . induce q         == induce (\\x -> p x && q x)
-- 'isSubgraphOf' (induce p x) x == True
-- @
induce :: (a -> Bool) -> Graph a -> Graph a
induce :: (a -> Bool) -> Graph a -> Graph a
induce a -> Bool
p = Graph (Maybe a) -> Graph a
forall a. Graph (Maybe a) -> Graph a
induceJust (Graph (Maybe a) -> Graph a)
-> (Graph a -> Graph (Maybe a)) -> Graph a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> Graph a -> Graph (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\a
a -> if a -> Bool
p a
a then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing)
{-# INLINE induce #-}

-- | Construct the /induced subgraph/ of a given graph by removing the vertices
-- that are 'Nothing'.
-- Complexity: /O(s)/ time, memory and size.
--
-- Good consumer and producer.
--
-- @
-- induceJust ('vertex' 'Nothing')                               == 'empty'
-- induceJust ('edge' ('Just' x) 'Nothing')                        == 'vertex' x
-- induceJust . 'fmap' 'Just'                                    == 'id'
-- induceJust . 'fmap' (\\x -> if p x then 'Just' x else 'Nothing') == 'induce' p
-- @
induceJust :: Graph (Maybe a) -> Graph a
induceJust :: Graph (Maybe a) -> Graph a
induceJust Graph (Maybe a)
g = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> Maybe r -> r
forall a. a -> Maybe a -> a
fromMaybe r
e (Maybe r -> r) -> Maybe r -> r
forall a b. (a -> b) -> a -> b
$
    Maybe r
-> (Maybe a -> Maybe r)
-> (Maybe r -> Maybe r -> Maybe r)
-> (Maybe r -> Maybe r -> Maybe r)
-> Graph (Maybe a)
-> Maybe r
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Maybe r
forall a. Maybe a
Nothing ((a -> r) -> Maybe a -> Maybe r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> r
v) ((r -> r -> r) -> Maybe r -> Maybe r -> Maybe r
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k r -> r -> r
o) ((r -> r -> r) -> Maybe r -> Maybe r -> Maybe r
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k r -> r -> r
c) Graph (Maybe a)
g
  where
    k :: (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k t -> t -> t
_ Maybe t
x        Maybe t
Nothing  = Maybe t
x -- Constant folding to get rid of Empty leaves
    k t -> t -> t
_ Maybe t
Nothing  Maybe t
y        = Maybe t
y
    k t -> t -> t
f (Just t
x) (Just t
y) = t -> Maybe t
forall a. a -> Maybe a
Just (t -> t -> t
f t
x t
y)
{-# INLINE induceJust #-}

-- NB: This is not a good producer since it requires an Eq instance on the
-- produced structure.
-- | Simplify a graph expression. Semantically, this is the identity function,
-- but it simplifies a given expression according to the laws of the algebra.
-- The function does not compute the simplest possible expression,
-- but uses heuristics to obtain useful simplifications in reasonable time.
-- Complexity: the function performs /O(s)/ graph comparisons. It is guaranteed
-- that the size of the result does not exceed the size of the given expression.
--
-- Good consumer.
--
-- @
-- simplify              == id
-- 'size' (simplify x)     <= 'size' x
-- simplify 'empty'       '===' 'empty'
-- simplify 1           '===' 1
-- simplify (1 + 1)     '===' 1
-- simplify (1 + 2 + 1) '===' 1 + 2
-- simplify (1 * 1 * 1) '===' 1 * 1
-- @
simplify :: Ord a => Graph a -> Graph a
simplify :: Graph a -> Graph a
simplify = Graph a
-> (a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> Graph a
-> Graph a
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Graph a
forall a. Graph a
Empty a -> Graph a
forall a. a -> Graph a
Vertex ((Graph a -> Graph a -> Graph a) -> Graph a -> Graph a -> Graph a
forall g. Eq g => (g -> g -> g) -> g -> g -> g
simple Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay) ((Graph a -> Graph a -> Graph a) -> Graph a -> Graph a -> Graph a
forall g. Eq g => (g -> g -> g) -> g -> g -> g
simple Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect)
{-# INLINE simplify #-}
{-# SPECIALISE simplify :: Graph Int -> Graph Int #-}

simple :: Eq g => (g -> g -> g) -> g -> g -> g
simple :: (g -> g -> g) -> g -> g -> g
simple g -> g -> g
op g
x g
y
    | g
x g -> g -> Bool
forall a. Eq a => a -> a -> Bool
== g
z    = g
x
    | g
y g -> g -> Bool
forall a. Eq a => a -> a -> Bool
== g
z    = g
y
    | Bool
otherwise = g
z
  where
    z :: g
z = g -> g -> g
op g
x g
y
{-# SPECIALISE simple :: (Int -> Int -> Int) -> Int -> Int -> Int #-}

-- | Left-to-right /relational composition/ of graphs: vertices @x@ and @z@ are
-- connected in the resulting graph if there is a vertex @y@, such that @x@ is
-- connected to @y@ in the first graph, and @y@ is connected to @z@ in the
-- second graph. There are no isolated vertices in the result. This operation is
-- associative, has 'empty' and single-'vertex' graphs as /annihilating zeroes/,
-- and distributes over 'overlay'.
-- Complexity: /O(n * m * log(n))/ time, /O(n + m)/ memory, and /O(m1 + m2)/
-- size, where /n/ and /m/ stand for the number of vertices and edges in the
-- resulting graph, while /m1/ and /m2/ are the number of edges in the original
-- graphs. Note that the number of edges in the resulting graph may be
-- quadratic, i.e. /m = O(m1 * m2)/, but the algebraic representation requires
-- only /O(m1 + m2)/ operations to list them.
--
-- Good consumer of both arguments and good producer.
--
-- @
-- compose 'empty'            x                == 'empty'
-- compose x                'empty'            == 'empty'
-- compose ('vertex' x)       y                == 'empty'
-- compose x                ('vertex' y)       == 'empty'
-- compose x                (compose y z)    == compose (compose x y) z
-- compose x                ('overlay' y z)    == 'overlay' (compose x y) (compose x z)
-- compose ('overlay' x y)    z                == 'overlay' (compose x z) (compose y z)
-- compose ('edge' x y)       ('edge' y z)       == 'edge' x z
-- compose ('path'    [1..5]) ('path'    [1..5]) == 'edges' [(1,3), (2,4), (3,5)]
-- compose ('circuit' [1..5]) ('circuit' [1..5]) == 'circuit' [1,3,5,2,4]
-- 'size' (compose x y)                        <= 'edgeCount' x + 'edgeCount' y + 1
-- @
compose :: Ord a => Graph a -> Graph a -> Graph a
compose :: Graph a -> Graph a -> Graph a
compose Graph a
x Graph a
y = (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a.
(forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
buildg ((forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
 -> Graph a)
-> (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r)
-> Graph a
forall a b. (a -> b) -> a -> b
$ \r
e a -> r
v r -> r -> r
o r -> r -> r
c -> r -> Maybe r -> r
forall a. a -> Maybe a -> a
fromMaybe r
e (Maybe r -> r) -> Maybe r -> r
forall a b. (a -> b) -> a -> b
$
  (r -> r -> r) -> [r] -> Maybe r
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe r -> r -> r
o
    [ r -> (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
foldg r
e a -> r
v r -> r -> r
o r -> r -> r
c ([a] -> [a] -> Graph a
forall a. [a] -> [a] -> Graph a
biclique [a]
xs [a]
ys)
    | a
ve <- Set a -> [a]
forall a. Set a -> [a]
Set.toList (AdjacencyMap a -> Set a
forall a. AdjacencyMap a -> Set a
AM.vertexSet AdjacencyMap a
mx Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
`Set.union` AdjacencyMap a -> Set a
forall a. AdjacencyMap a -> Set a
AM.vertexSet AdjacencyMap a
my)
    , let xs :: [a]
xs = Set a -> [a]
forall a. Set a -> [a]
Set.toList (a -> AdjacencyMap a -> Set a
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet a
ve AdjacencyMap a
mx), Bool -> Bool
not ([a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs)
    , let ys :: [a]
ys = Set a -> [a]
forall a. Set a -> [a]
Set.toList (a -> AdjacencyMap a -> Set a
forall a. Ord a => a -> AdjacencyMap a -> Set a
AM.postSet a
ve AdjacencyMap a
my), Bool -> Bool
not ([a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
ys) ]
  where
    mx :: AdjacencyMap a
mx = Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap (Graph a -> Graph a
forall a. Graph a -> Graph a
transpose Graph a
x)
    my :: AdjacencyMap a
my = Graph a -> AdjacencyMap a
forall a. Ord a => Graph a -> AdjacencyMap a
toAdjacencyMap Graph a
y
{-# INLINE compose #-}

-- | Compute the /Cartesian product/ of graphs.
-- Complexity: /O(s1 * s2)/ time, memory and size, where /s1/ and /s2/ are the
-- sizes of the given graphs.
--
-- @
-- box ('path' [0,1]) ('path' "ab") == 'edges' [ ((0,\'a\'), (0,\'b\'))
--                                       , ((0,\'a\'), (1,\'a\'))
--                                       , ((0,\'b\'), (1,\'b\'))
--                                       , ((1,\'a\'), (1,\'b\')) ]
-- @
-- Up to isomorphism between the resulting vertex types, this operation is
-- /commutative/, /associative/, /distributes/ over 'overlay', has singleton
-- graphs as /identities/ and 'empty' as the /annihilating zero/. Below @~~@
-- stands for equality up to an isomorphism, e.g. @(x,@ @()) ~~ x@.
--
-- @
-- box x y               ~~ box y x
-- box x (box y z)       ~~ box (box x y) z
-- box x ('overlay' y z)   == 'overlay' (box x y) (box x z)
-- box x ('vertex' ())     ~~ x
-- box x 'empty'           ~~ 'empty'
-- 'transpose'   (box x y) == box ('transpose' x) ('transpose' y)
-- 'vertexCount' (box x y) == 'vertexCount' x * 'vertexCount' y
-- 'edgeCount'   (box x y) <= 'vertexCount' x * 'edgeCount' y + 'edgeCount' x * 'vertexCount' y
-- @
box :: Graph a -> Graph b -> Graph (a, b)
box :: Graph a -> Graph b -> Graph (a, b)
box Graph a
x Graph b
y = Graph (a, b) -> Graph (a, b) -> Graph (a, b)
forall a. Graph a -> Graph a -> Graph a
overlay (Graph (b -> (a, b))
fx Graph (b -> (a, b)) -> Graph b -> Graph (a, b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Graph b
y) (Graph (a -> (a, b))
fy Graph (a -> (a, b)) -> Graph a -> Graph (a, b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Graph a
x)
  where
    fx :: Graph (b -> (a, b))
fx = Graph (b -> (a, b))
-> (a -> Graph (b -> (a, b)))
-> (Graph (b -> (a, b))
    -> Graph (b -> (a, b)) -> Graph (b -> (a, b)))
-> (Graph (b -> (a, b))
    -> Graph (b -> (a, b)) -> Graph (b -> (a, b)))
-> Graph a
-> Graph (b -> (a, b))
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Graph (b -> (a, b))
forall a. Graph a
empty ((b -> (a, b)) -> Graph (b -> (a, b))
forall a. a -> Graph a
vertex ((b -> (a, b)) -> Graph (b -> (a, b)))
-> (a -> b -> (a, b)) -> a -> Graph (b -> (a, b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.      (,)) Graph (b -> (a, b)) -> Graph (b -> (a, b)) -> Graph (b -> (a, b))
forall a. Graph a -> Graph a -> Graph a
overlay Graph (b -> (a, b)) -> Graph (b -> (a, b)) -> Graph (b -> (a, b))
forall a. Graph a -> Graph a -> Graph a
overlay Graph a
x
    fy :: Graph (a -> (a, b))
fy = Graph (a -> (a, b))
-> (b -> Graph (a -> (a, b)))
-> (Graph (a -> (a, b))
    -> Graph (a -> (a, b)) -> Graph (a -> (a, b)))
-> (Graph (a -> (a, b))
    -> Graph (a -> (a, b)) -> Graph (a -> (a, b)))
-> Graph b
-> Graph (a -> (a, b))
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Graph (a -> (a, b))
forall a. Graph a
empty ((a -> (a, b)) -> Graph (a -> (a, b))
forall a. a -> Graph a
vertex ((a -> (a, b)) -> Graph (a -> (a, b)))
-> (b -> a -> (a, b)) -> b -> Graph (a -> (a, b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> (a, b)) -> b -> a -> (a, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,)) Graph (a -> (a, b)) -> Graph (a -> (a, b)) -> Graph (a -> (a, b))
forall a. Graph a -> Graph a -> Graph a
overlay Graph (a -> (a, b)) -> Graph (a -> (a, b)) -> Graph (a -> (a, b))
forall a. Graph a -> Graph a -> Graph a
overlay Graph b
y

-- | /Sparsify/ a graph by adding intermediate 'Left' @Int@ vertices between the
-- original vertices (wrapping the latter in 'Right') such that the resulting
-- graph is /sparse/, i.e. contains only O(s) edges, but preserves the
-- reachability relation between the original vertices. Sparsification is useful
-- when working with dense graphs, as it can reduce the number of edges from
-- O(n^2) down to O(n) by replacing cliques, bicliques and similar densely
-- connected structures by sparse subgraphs built out of intermediate vertices.
-- Complexity: O(s) time, memory and size.
--
-- @
-- 'Data.List.sort' . 'Algebra.Graph.ToGraph.reachable' x       == 'Data.List.sort' . 'Data.Either.rights' . 'Algebra.Graph.ToGraph.reachable' ('Data.Either.Right' x) . sparsify
-- 'vertexCount' (sparsify x) <= 'vertexCount' x + 'size' x + 1
-- 'edgeCount'   (sparsify x) <= 3 * 'size' x
-- 'size'        (sparsify x) <= 3 * 'size' x
-- @
sparsify :: Graph a -> Graph (Either Int a)
sparsify :: Graph a -> Graph (Either Int a)
sparsify Graph a
graph = Graph (Either Int a)
res
  where
    (Graph (Either Int a)
res, Int
end) = State Int (Graph (Either Int a))
-> Int -> (Graph (Either Int a), Int)
forall s a. State s a -> s -> (a, s)
runState ((Int -> Int -> State Int (Graph (Either Int a)))
-> (a -> Int -> Int -> State Int (Graph (Either Int a)))
-> ((Int -> Int -> State Int (Graph (Either Int a)))
    -> (Int -> Int -> State Int (Graph (Either Int a)))
    -> Int
    -> Int
    -> State Int (Graph (Either Int a)))
-> ((Int -> Int -> State Int (Graph (Either Int a)))
    -> (Int -> Int -> State Int (Graph (Either Int a)))
    -> Int
    -> Int
    -> State Int (Graph (Either Int a)))
-> Graph a
-> Int
-> Int
-> State Int (Graph (Either Int a))
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Int -> Int -> State Int (Graph (Either Int a))
forall (m :: * -> *) a b.
Monad m =>
a -> a -> m (Graph (Either a b))
e a -> Int -> Int -> State Int (Graph (Either Int a))
forall (m :: * -> *) b a.
Monad m =>
b -> a -> a -> m (Graph (Either a b))
v (Int -> Int -> State Int (Graph (Either Int a)))
-> (Int -> Int -> State Int (Graph (Either Int a)))
-> Int
-> Int
-> State Int (Graph (Either Int a))
forall (f :: * -> *) t t a.
Applicative f =>
(t -> t -> f (Graph a))
-> (t -> t -> f (Graph a)) -> t -> t -> f (Graph a)
o (Int -> Int -> State Int (Graph (Either Int a)))
-> (Int -> Int -> State Int (Graph (Either Int a)))
-> Int
-> Int
-> State Int (Graph (Either Int a))
forall (m :: * -> *) t t a t.
(Monad m, Num t) =>
(t -> t -> StateT t m (Graph a))
-> (t -> t -> StateT t m (Graph a))
-> t
-> t
-> StateT t m (Graph a)
c Graph a
graph Int
0 Int
end) Int
1
    e :: a -> a -> m (Graph (Either a b))
e     a
s a
t  = Graph (Either a b) -> m (Graph (Either a b))
forall (m :: * -> *) a. Monad m => a -> m a
return (Graph (Either a b) -> m (Graph (Either a b)))
-> Graph (Either a b) -> m (Graph (Either a b))
forall a b. (a -> b) -> a -> b
$ [Either a b] -> Graph (Either a b)
forall a. [a] -> Graph a
path   [a -> Either a b
forall a b. a -> Either a b
Left a
s,          a -> Either a b
forall a b. a -> Either a b
Left a
t]
    v :: b -> a -> a -> m (Graph (Either a b))
v b
x   a
s a
t  = Graph (Either a b) -> m (Graph (Either a b))
forall (m :: * -> *) a. Monad m => a -> m a
return (Graph (Either a b) -> m (Graph (Either a b)))
-> Graph (Either a b) -> m (Graph (Either a b))
forall a b. (a -> b) -> a -> b
$ [Either a b] -> Graph (Either a b)
forall a. [a] -> Graph a
clique [a -> Either a b
forall a b. a -> Either a b
Left a
s, b -> Either a b
forall a b. b -> Either a b
Right b
x, a -> Either a b
forall a b. a -> Either a b
Left a
t]
    o :: (t -> t -> f (Graph a))
-> (t -> t -> f (Graph a)) -> t -> t -> f (Graph a)
o t -> t -> f (Graph a)
x t -> t -> f (Graph a)
y t
s t
t  = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay (Graph a -> Graph a -> Graph a)
-> f (Graph a) -> f (Graph a -> Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t
s t -> t -> f (Graph a)
`x` t
t f (Graph a -> Graph a) -> f (Graph a) -> f (Graph a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> t
s t -> t -> f (Graph a)
`y` t
t
    c :: (t -> t -> StateT t m (Graph a))
-> (t -> t -> StateT t m (Graph a))
-> t
-> t
-> StateT t m (Graph a)
c t -> t -> StateT t m (Graph a)
x t -> t -> StateT t m (Graph a)
y t
s t
t  = do
        t
m <- StateT t m t
forall (m :: * -> *) s. Monad m => StateT s m s
get
        t -> StateT t m ()
forall (m :: * -> *) s. Monad m => s -> StateT s m ()
put (t
m t -> t -> t
forall a. Num a => a -> a -> a
+ t
1)
        Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay (Graph a -> Graph a -> Graph a)
-> StateT t m (Graph a) -> StateT t m (Graph a -> Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t
s t -> t -> StateT t m (Graph a)
`x` t
m StateT t m (Graph a -> Graph a)
-> StateT t m (Graph a) -> StateT t m (Graph a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> t
m t -> t -> StateT t m (Graph a)
`y` t
t

-- | Sparsify a graph whose vertices are integers in the range @[1..n]@, where
-- @n@ is the first argument of the function, producing an array-based graph
-- representation from "Data.Graph" (introduced by King and Launchbury, hence
-- the name of the function). In the resulting graph, vertices @[1..n]@
-- correspond to the original vertices, and all vertices greater than @n@ are
-- introduced by the sparsification procedure.
--
-- Complexity: /O(s)/ time and memory. Note that thanks to sparsification, the
-- resulting graph has a linear number of edges with respect to the size of the
-- original algebraic representation even though the latter can potentially
-- contain a quadratic /O(s^2)/ number of edges.
--
-- @
-- 'Data.List.sort' . 'Algebra.Graph.ToGraph.reachable' k                 == 'Data.List.sort' . 'filter' (<= n) . 'flip' 'Data.Graph.reachable' k . sparsifyKL n
-- 'length' ('Data.Graph.vertices' $ sparsifyKL n x) <= 'vertexCount' x + 'size' x + 1
-- 'length' ('Data.Graph.edges'    $ sparsifyKL n x) <= 3 * 'size' x
-- @
sparsifyKL :: Int -> Graph Int -> KL.Graph
sparsifyKL :: Int -> Graph Int -> Graph
sparsifyKL Int
n Graph Int
graph = (Int, Int) -> [(Int, Int)] -> Graph
KL.buildG (Int
1, Int
next Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ((Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2) (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
forall a. a -> [a] -> [a]
: List (Int, Int) -> [Item (List (Int, Int))]
forall l. IsList l => l -> [Item l]
Exts.toList (List (Int, Int)
res :: List KL.Edge))
  where
    (List (Int, Int)
res, Int
next) = State Int (List (Int, Int)) -> Int -> (List (Int, Int), Int)
forall s a. State s a -> s -> (a, s)
runState ((Int -> Int -> State Int (List (Int, Int)))
-> (Int -> Int -> Int -> State Int (List (Int, Int)))
-> ((Int -> Int -> State Int (List (Int, Int)))
    -> (Int -> Int -> State Int (List (Int, Int)))
    -> Int
    -> Int
    -> State Int (List (Int, Int)))
-> ((Int -> Int -> State Int (List (Int, Int)))
    -> (Int -> Int -> State Int (List (Int, Int)))
    -> Int
    -> Int
    -> State Int (List (Int, Int)))
-> Graph Int
-> Int
-> Int
-> State Int (List (Int, Int))
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Int -> Int -> State Int (List (Int, Int))
forall (m :: * -> *) a p p. (Monad m, IsList a) => p -> p -> m a
e Int -> Int -> Int -> State Int (List (Int, Int))
forall (m :: * -> *) a b.
(Monad m, IsList a, Item a ~ (b, b)) =>
b -> b -> b -> m a
v (Int -> Int -> State Int (List (Int, Int)))
-> (Int -> Int -> State Int (List (Int, Int)))
-> Int
-> Int
-> State Int (List (Int, Int))
forall (f :: * -> *) b t t.
(Applicative f, Semigroup b) =>
(t -> t -> f b) -> (t -> t -> f b) -> t -> t -> f b
o (Int -> Int -> State Int (List (Int, Int)))
-> (Int -> Int -> State Int (List (Int, Int)))
-> Int
-> Int
-> State Int (List (Int, Int))
forall (m :: * -> *) t b.
(Monad m, Num t, Semigroup b, IsList b, Item b ~ (t, t)) =>
(t -> t -> StateT t m b)
-> (t -> t -> StateT t m b) -> t -> t -> StateT t m b
c Graph Int
graph (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2)) (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
3)
    e :: p -> p -> m a
e     p
_ p
_   = a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> m a) -> a -> m a
forall a b. (a -> b) -> a -> b
$ [Item a] -> a
forall l. IsList l => [Item l] -> l
Exts.fromList []
    v :: b -> b -> b -> m a
v b
x   b
s b
t   = a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> m a) -> a -> m a
forall a b. (a -> b) -> a -> b
$ [Item a] -> a
forall l. IsList l => [Item l] -> l
Exts.fromList [(b
s,b
x), (b
x,b
t)]
    o :: (t -> t -> f b) -> (t -> t -> f b) -> t -> t -> f b
o t -> t -> f b
x t -> t -> f b
y t
s t
t   = b -> b -> b
forall a. Semigroup a => a -> a -> a
(<>) (b -> b -> b) -> f b -> f (b -> b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t
s t -> t -> f b
`x` t
t f (b -> b) -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> t
s t -> t -> f b
`y` t
t
    c :: (t -> t -> StateT t m b)
-> (t -> t -> StateT t m b) -> t -> t -> StateT t m b
c t -> t -> StateT t m b
x t -> t -> StateT t m b
y t
s t
t   = do
        t
m <- StateT t m t
forall (m :: * -> *) s. Monad m => StateT s m s
get
        t -> StateT t m ()
forall (m :: * -> *) s. Monad m => s -> StateT s m ()
put (t
m t -> t -> t
forall a. Num a => a -> a -> a
+ t
1)
        (\b
xs b
ys -> [Item b] -> b
forall l. IsList l => [Item l] -> l
Exts.fromList [(t
s,t
m), (t
m,t
t)] b -> b -> b
forall a. Semigroup a => a -> a -> a
<> b
xs b -> b -> b
forall a. Semigroup a => a -> a -> a
<> b
ys) (b -> b -> b) -> StateT t m b -> StateT t m (b -> b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t
s t -> t -> StateT t m b
`x` t
m StateT t m (b -> b) -> StateT t m b -> StateT t m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> t
m t -> t -> StateT t m b
`y` t
t

{- Note [The rules of foldg]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The rules for foldg work very similarly to GHC's mapFB rules; see a note below
this line: http://hackage.haskell.org/package/base/docs/src/GHC.Base.html#mapFB.

* The expressions are first inlined to allow the compiler to apply the main rule
  "foldg/buildg" that states that the composition of a good producer (expressed
  via 'buildg') and a good consumer (expressed via 'foldg') can be fused to
  avoid the construction of an intermediate structure.

* If this inlining is made blindly, it can lead to unneeded operations. They are
  optimised via the "foldg/id" rule.

* 'composeR' is here to allow further optimisation. As a high-order function, it
  benefits from inlining in the final phase.

* The "composeR/composeR" rule optimises compositions of 'composeR' chains.
-}

composeR :: (b -> c) -> (a -> b) -> a -> c
composeR :: (b -> c) -> (a -> b) -> a -> c
composeR = (b -> c) -> (a -> b) -> a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.)
{-# INLINE [1] composeR #-}

-- Rewrite rules for algebraic graph fusion.
{-# RULES

-- Fuse a 'foldg' followed by a 'buildg':
"foldg/buildg" forall e v o c (g :: forall b. b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> b).
    foldg e v o c (buildg g) = g e v o c

-- Fuse 'composeR' chains (see the definition of the bind operator).
"composeR/composeR" forall c f g.
    composeR (composeR c f) g = composeR c (f . g)

-- Rewrite identity (which can appear in the inlining of 'buildg') to a more
-- efficient one.
"foldg/id"
    foldg Empty Vertex Overlay Connect = id

#-}

-- 'Focus' on a specified subgraph.
focus :: (a -> Bool) -> Graph a -> Focus a
focus :: (a -> Bool) -> Graph a -> Focus a
focus a -> Bool
f = Focus a
-> (a -> Focus a)
-> (Focus a -> Focus a -> Focus a)
-> (Focus a -> Focus a -> Focus a)
-> Graph a
-> Focus a
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg Focus a
forall a. Focus a
emptyFocus ((a -> Bool) -> a -> Focus a
forall a. (a -> Bool) -> a -> Focus a
vertexFocus a -> Bool
f) Focus a -> Focus a -> Focus a
forall a. Focus a -> Focus a -> Focus a
overlayFoci Focus a -> Focus a -> Focus a
forall a. Focus a -> Focus a -> Focus a
connectFoci
{-# INLINE focus #-}

-- | The 'Context' of a subgraph comprises its 'inputs' and 'outputs', i.e. all
-- the vertices that are connected to the subgraph's vertices. Note that inputs
-- and outputs can belong to the subgraph itself. In general, there are no
-- guarantees on the order of vertices in 'inputs' and 'outputs'; furthermore,
-- there may be repetitions.
data Context a = Context { Context a -> [a]
inputs :: [a], Context a -> [a]
outputs :: [a] }
    deriving (Context a -> Context a -> Bool
(Context a -> Context a -> Bool)
-> (Context a -> Context a -> Bool) -> Eq (Context a)
forall a. Eq a => Context a -> Context a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Context a -> Context a -> Bool
$c/= :: forall a. Eq a => Context a -> Context a -> Bool
== :: Context a -> Context a -> Bool
$c== :: forall a. Eq a => Context a -> Context a -> Bool
Eq, Int -> Context a -> ShowS
[Context a] -> ShowS
Context a -> String
(Int -> Context a -> ShowS)
-> (Context a -> String)
-> ([Context a] -> ShowS)
-> Show (Context a)
forall a. Show a => Int -> Context a -> ShowS
forall a. Show a => [Context a] -> ShowS
forall a. Show a => Context a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Context a] -> ShowS
$cshowList :: forall a. Show a => [Context a] -> ShowS
show :: Context a -> String
$cshow :: forall a. Show a => Context a -> String
showsPrec :: Int -> Context a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Context a -> ShowS
Show)

-- | Extract the 'Context' of a subgraph specified by a given predicate. Returns
-- @Nothing@ if the specified subgraph is empty.
--
-- Good consumer.
--
-- @
-- context ('const' False) x                   == Nothing
-- context (== 1)        ('edge' 1 2)          == Just ('Context' [   ] [2  ])
-- context (== 2)        ('edge' 1 2)          == Just ('Context' [1  ] [   ])
-- context ('const' True ) ('edge' 1 2)          == Just ('Context' [1  ] [2  ])
-- context (== 4)        (3 * 1 * 4 * 1 * 5) == Just ('Context' [3,1] [1,5])
-- @
context :: (a -> Bool) -> Graph a -> Maybe (Context a)
context :: (a -> Bool) -> Graph a -> Maybe (Context a)
context a -> Bool
p Graph a
g | Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
f      = Context a -> Maybe (Context a)
forall a. a -> Maybe a
Just (Context a -> Maybe (Context a)) -> Context a -> Maybe (Context a)
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> Context a
forall a. [a] -> [a] -> Context a
Context (List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (List a -> [a]) -> List a -> [a]
forall a b. (a -> b) -> a -> b
$ Focus a -> List a
forall a. Focus a -> List a
is Focus a
f) (List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (List a -> [a]) -> List a -> [a]
forall a b. (a -> b) -> a -> b
$ Focus a -> List a
forall a. Focus a -> List a
os Focus a
f)
            | Bool
otherwise = Maybe (Context a)
forall a. Maybe a
Nothing
  where
    f :: Focus a
f = (a -> Bool) -> Graph a -> Focus a
forall a. (a -> Bool) -> Graph a -> Focus a
focus a -> Bool
p Graph a
g
{-# INLINE context #-}