-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.NonEmpty
-- 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 data type 'Graph' for algebraic graphs that are known
-- to be non-empty at compile time. To avoid name clashes with "Algebra.Graph",
-- this module can be imported qualified:
--
-- @
-- import qualified Algebra.Graph.NonEmpty as NonEmpty
-- @
--
-- The naming convention generally follows that of "Data.List.NonEmpty": we use
-- suffix @1@ to indicate the functions whose interface must be changed compared
-- to "Algebra.Graph", e.g. 'vertices1'.
--
-----------------------------------------------------------------------------
module Algebra.Graph.NonEmpty (
    -- * Non-empty algebraic graphs
    Graph (..), toNonEmpty,

    -- * Basic graph construction primitives
    vertex, edge, overlay, overlay1, connect, vertices1, edges1, overlays1,
    connects1,

    -- * Graph folding
    foldg1,

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

    -- * Graph properties
    size, hasVertex, hasEdge, vertexCount, edgeCount, vertexList1, edgeList,
    vertexSet, edgeSet,

    -- * Standard families of graphs
    path1, circuit1, clique1, biclique1, star, stars1, tree, mesh1, torus1,

    -- * Graph transformation
    removeVertex1, removeEdge, replaceVertex, mergeVertices, splitVertex1,
    transpose, induce1, induceJust1, simplify, sparsify, sparsifyKL,

    -- * Graph composition
    box
    ) where

import Control.DeepSeq
import Control.Monad
import Control.Monad.Trans.State
import Data.List.NonEmpty (NonEmpty (..))
import Data.String

import Algebra.Graph.Internal

import qualified Algebra.Graph                 as G
import qualified Algebra.Graph.ToGraph         as T
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.List.NonEmpty            as NonEmpty
import qualified Data.Set                      as Set
import qualified Data.Tree                     as Tree
import qualified GHC.Exts                      as Exts

{-| Non-empty algebraic graphs, which are constructed using three primitives:
'vertex', 'overlay' and 'connect'. See module "Algebra.Graph" for algebraic
graphs that can be empty.

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 'signum' method of the type class 'Num' cannot be implemented and
will throw an error. Furthermore, 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 satisfies the following laws of non-empty algebraic graphs.

    * 'overlay' is commutative, associative and idempotent:

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

    * 'connect' is associative:

        > 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

    * 'connect' satisfies absorption and saturation:

        > 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, defined as the number of vertex leaves (note that /n/ <= /s/). If
@g@ is a 'Graph', the corresponding /n/, /m/ and /s/ can be computed as follows:

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

Converting a 'Graph' to the corresponding
'Algebra.Graph.NonEmpty.AdjacencyMap.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 'Ord' 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@

@x     <= x + y
x + y <= x * y@
-}
data Graph a = Vertex a
             | Overlay (Graph a) (Graph a)
             | Connect (Graph a) (Graph a)
             deriving (a -> Graph b -> Graph a
(a -> b) -> Graph a -> Graph b
(forall a b. (a -> b) -> Graph a -> Graph b)
-> (forall a b. a -> Graph b -> Graph a) -> Functor Graph
forall a b. a -> Graph b -> Graph a
forall a b. (a -> b) -> Graph a -> Graph b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Graph b -> Graph a
$c<$ :: forall a b. a -> Graph b -> Graph a
fmap :: (a -> b) -> Graph a -> Graph b
$cfmap :: forall a b. (a -> b) -> Graph a -> Graph b
Functor, 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)

instance NFData a => NFData (Graph a) where
    rnf :: Graph a -> ()
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

instance T.ToGraph (Graph a) where
    type ToVertex (Graph a) = a
    foldg :: r
-> (ToVertex (Graph a) -> r)
-> (r -> r -> r)
-> (r -> r -> r)
-> Graph a
-> r
foldg r
_ = (ToVertex (Graph a) -> r)
-> (r -> r -> r) -> (r -> r -> r) -> Graph a -> r
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1
    hasEdge :: ToVertex (Graph a) -> ToVertex (Graph a) -> Graph a -> Bool
hasEdge = ToVertex (Graph a) -> ToVertex (Graph a) -> Graph a -> Bool
forall a. Eq a => a -> a -> Graph a -> Bool
hasEdge

-- | __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      = String -> Graph a -> Graph a
forall a. HasCallStack => String -> a
error String
"NonEmpty.Graph.signum cannot be implemented."
    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

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
eq

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
ord

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

-- TODO: Find a more efficient equality check.
-- | Check if two graphs are equal by converting them to their adjacency maps.
eq :: Ord a => Graph a -> Graph a -> Bool
eq :: Graph a -> Graph a -> Bool
eq Graph a
x Graph a
y = Graph a -> AdjacencyMap (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
x AdjacencyMap a -> AdjacencyMap a -> Bool
forall a. Eq a => a -> a -> Bool
== Graph a -> AdjacencyMap (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
y
{-# NOINLINE [1] eq #-}
{-# RULES "eqInt" eq = eqInt #-}

-- Like @eq@ but specialised for graphs with vertices of type 'Int'.
eqInt :: Graph Int -> Graph Int -> Bool
eqInt :: Graph Int -> Graph Int -> Bool
eqInt Graph Int
x Graph Int
y = Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
x AdjacencyIntMap -> AdjacencyIntMap -> Bool
forall a. Eq a => a -> a -> Bool
== Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
y

-- TODO: Find a more efficient comparison.
-- Compare two graphs by converting them to their adjacency maps.
ord :: Ord a => Graph a -> Graph a -> Ordering
ord :: Graph a -> Graph a -> Ordering
ord Graph a
x Graph a
y = AdjacencyMap a -> AdjacencyMap a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Graph a -> AdjacencyMap (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
x) (Graph a -> AdjacencyMap (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
y)
{-# NOINLINE [1] ord #-}
{-# RULES "ordInt" ord = ordInt #-}

-- Like @ord@ but specialised for graphs with vertices of type 'Int'.
ordInt :: Graph Int -> Graph Int -> Ordering
ordInt :: Graph Int -> Graph Int -> Ordering
ordInt Graph Int
x Graph Int
y = AdjacencyIntMap -> AdjacencyIntMap -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
x) (Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
y)

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 = Graph (a -> b)
f Graph (a -> b) -> ((a -> b) -> Graph b) -> Graph b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ((a -> b) -> Graph a -> Graph b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Graph a
x)

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 = (a -> Graph b)
-> (Graph b -> Graph b -> Graph b)
-> (Graph b -> Graph b -> Graph b)
-> Graph a
-> Graph b
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 a -> Graph b
f Graph b -> Graph b -> Graph b
forall a. Graph a -> Graph a -> Graph a
Overlay Graph b -> Graph b -> Graph b
forall a. Graph a -> Graph a -> Graph a
Connect Graph a
g

-- | Convert an algebraic graph (from "Algebra.Graph") into a non-empty
-- algebraic graph. Returns 'Nothing' if the argument is 'G.empty'.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- toNonEmpty 'G.empty'       == Nothing
-- toNonEmpty ('T.toGraph' x) == Just (x :: 'Graph' a)
-- @
toNonEmpty :: G.Graph a -> Maybe (Graph a)
toNonEmpty :: Graph a -> Maybe (Graph a)
toNonEmpty = Maybe (Graph a)
-> (a -> Maybe (Graph a))
-> (Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a))
-> (Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a))
-> Graph a
-> Maybe (Graph a)
forall b a.
b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
G.foldg Maybe (Graph a)
forall a. Maybe a
Nothing (Graph a -> Maybe (Graph a)
forall a. a -> Maybe a
Just (Graph a -> Maybe (Graph a))
-> (a -> Graph a) -> a -> Maybe (Graph a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Graph a
forall a. a -> Graph a
Vertex) ((Graph a -> Graph a -> Graph a)
-> Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a)
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
go Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay) ((Graph a -> Graph a -> Graph a)
-> Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a)
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
go Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect)
  where
    go :: (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
go t -> t -> t
_ Maybe t
Nothing  Maybe t
y        = Maybe t
y
    go t -> t -> t
_ Maybe t
x        Maybe t
Nothing  = Maybe t
x
    go 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)

-- | Construct the graph comprising /a single isolated vertex/. An alias for the
-- constructor 'Vertex'.
--
-- @
-- '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
u a
v = 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
u) (a -> Graph a
forall a. a -> Graph a
vertex a
v)

-- | /Overlay/ two graphs. An alias for the constructor 'Overlay'. This is a
-- commutative, associative and idempotent operation.
-- Complexity: /O(1)/ time and memory, /O(s1 + s2)/ size.
--
-- @
-- '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 #-}

-- | Overlay a possibly empty graph (from "Algebra.Graph") with a non-empty
-- graph. If the first argument is 'G.empty', the function returns the second
-- argument; otherwise it is semantically the same as 'overlay'.
-- Complexity: /O(s1)/ time and memory, and /O(s1 + s2)/ size.
--
-- @
--                overlay1 'G.empty' x == x
-- x /= 'G.empty' ==> overlay1 x     y == overlay (fromJust $ toNonEmpty x) y
-- @
overlay1 :: G.Graph a -> Graph a -> Graph a
overlay1 :: Graph a -> Graph a -> Graph a
overlay1 = (Graph a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> Maybe (Graph a)
-> Graph a
-> Graph a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Graph a -> Graph a
forall a. a -> a
id Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay (Maybe (Graph a) -> Graph a -> Graph a)
-> (Graph a -> Maybe (Graph a)) -> Graph a -> Graph a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph a -> Maybe (Graph a)
forall a. Graph a -> Maybe (Graph a)
toNonEmpty

-- | /Connect/ two graphs. An alias for the constructor 'Connect'. This is an
-- associative operation, 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)/.
--
-- @
-- '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 #-}

-- | 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.
--
-- @
-- vertices1 [x]           == 'vertex' x
-- 'hasVertex' x . vertices1 == 'elem' x
-- 'vertexCount' . vertices1 == 'length' . 'Data.List.NonEmpty.nub'
-- 'vertexSet'   . vertices1 == Set.'Set.fromList' . 'Data.List.NonEmpty.toList'
-- @
vertices1 :: NonEmpty a -> Graph a
vertices1 :: NonEmpty a -> Graph a
vertices1 = NonEmpty (Graph a) -> Graph a
forall a. NonEmpty (Graph a) -> Graph a
overlays1 (NonEmpty (Graph a) -> Graph a)
-> (NonEmpty a -> NonEmpty (Graph a)) -> NonEmpty a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Graph a) -> NonEmpty a -> NonEmpty (Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Graph a
forall a. a -> Graph a
vertex
{-# NOINLINE [1] vertices1 #-}

-- | Construct the graph from a list of edges.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- @
-- edges1 [(x,y)]     == 'edge' x y
-- edges1             == 'overlays1' . 'fmap' ('uncurry' 'edge')
-- 'edgeCount' . edges1 == 'Data.List.NonEmpty.length' . 'Data.List.NonEmpty.nub'
-- @
edges1 :: NonEmpty (a, a) -> Graph a
edges1 :: NonEmpty (a, a) -> Graph a
edges1  = NonEmpty (Graph a) -> Graph a
forall a. NonEmpty (Graph a) -> Graph a
overlays1 (NonEmpty (Graph a) -> Graph a)
-> (NonEmpty (a, a) -> NonEmpty (Graph a))
-> NonEmpty (a, a)
-> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, a) -> Graph a) -> NonEmpty (a, a) -> NonEmpty (Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((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
edge)

-- | 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.
--
-- @
-- overlays1 [x]   == x
-- overlays1 [x,y] == 'overlay' x y
-- @
overlays1 :: NonEmpty (Graph a) -> Graph a
overlays1 :: NonEmpty (Graph a) -> Graph a
overlays1 = (Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
forall a.
(Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
concatg1 Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
overlay
{-# INLINE [2] overlays1 #-}

-- | 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.
--
-- @
-- connects1 [x]   == x
-- connects1 [x,y] == 'connect' x y
-- @
connects1 :: NonEmpty (Graph a) -> Graph a
connects1 :: NonEmpty (Graph a) -> Graph a
connects1 = (Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
forall a.
(Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
concatg1 Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
connect
{-# INLINE [2] connects1 #-}

-- Auxiliary function, similar to 'sconcat'.
concatg1 :: (Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
concatg1 :: (Graph a -> Graph a -> Graph a) -> NonEmpty (Graph a) -> Graph a
concatg1 Graph a -> Graph a -> Graph a
combine (Graph a
x :| [Graph a]
xs) = Graph a -> (Graph a -> Graph a) -> Maybe (Graph a) -> Graph a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Graph a
x (Graph a -> Graph a -> Graph a
combine Graph a
x) (Maybe (Graph a) -> Graph a) -> Maybe (Graph a) -> Graph a
forall a b. (a -> b) -> a -> b
$ (Graph a -> Graph a -> Graph a) -> [Graph a] -> Maybe (Graph a)
forall a. (a -> a -> a) -> [a] -> Maybe a
foldr1Safe Graph a -> Graph a -> Graph a
combine [Graph a]
xs

-- | 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: 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.
--
-- @
-- foldg1 'vertex'    'overlay' 'connect'        == id
-- foldg1 'vertex'    'overlay' ('flip' 'connect') == 'transpose'
-- foldg1 ('const' 1) (+)     (+)            == 'size'
-- foldg1 (== x)    (||)    (||)           == 'hasVertex' x
-- @
foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 a -> b
v b -> b -> b
o b -> b -> b
c = Graph a -> b
go
  where
    go :: Graph a -> b
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)

-- | 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/.
--
-- @
-- isSubgraphOf x             ('overlay' x y) ==  True
-- isSubgraphOf ('overlay' x y) ('connect' x y) ==  True
-- isSubgraphOf ('path1' xs)    ('circuit1' 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 (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
x) (Graph a -> AdjacencyMap (ToVertex (Graph a))
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> AdjacencyMap (ToVertex t)
T.toAdjacencyMap Graph a
y)
{-# NOINLINE [1] 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
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
x) (Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap Graph Int
y)

-- | Structural equality on graph expressions.
-- Complexity: /O(s)/ time.
--
-- @
--     x === x     == True
-- x + y === x + y == True
-- 1 + 2 === 2 + 1 == False
-- x + y === x * y == False
-- @
(===) :: Eq a => Graph a -> Graph a -> Bool
(Vertex  a
x1   ) === :: Graph a -> Graph a -> Bool
=== (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 ===

-- | The /size/ of a graph, i.e. the number of leaves of the expression.
-- Complexity: /O(s)/ time.
--
-- @
-- 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 = (a -> Int)
-> (Int -> Int -> Int) -> (Int -> Int -> Int) -> Graph a -> Int
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 (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
(+)

-- | Check if a graph contains a given vertex.
-- Complexity: /O(s)/ time.
--
-- @
-- hasVertex x ('vertex' y) == (x == y)
-- @
hasVertex :: Eq a => a -> Graph a -> Bool
hasVertex :: a -> Graph a -> Bool
hasVertex a
v = (a -> Bool)
-> (Bool -> Bool -> Bool)
-> (Bool -> Bool -> Bool)
-> Graph a
-> Bool
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
v) Bool -> Bool -> Bool
(||) Bool -> Bool -> Bool
(||)
{-# SPECIALISE hasVertex :: Int -> Graph Int -> Bool #-}

-- See the Note [The implementation of hasEdge] in "Algebra.Graph".
-- | Check if a graph contains a given edge.
-- Complexity: /O(s)/ time.
--
-- @
-- 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 = (a -> Int -> Int)
-> ((Int -> Int) -> (Int -> Int) -> Int -> Int)
-> ((Int -> Int) -> (Int -> Int) -> Int -> Int)
-> Graph a
-> Int
-> Int
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 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 }
{-# SPECIALISE hasEdge :: Int -> Int -> Graph Int -> Bool #-}

-- | The number of vertices in a graph.
-- Complexity: /O(s * log(n))/ time.
--
-- @
-- vertexCount ('vertex' x)        ==  1
-- vertexCount                   ==  'length' . 'vertexList'
-- vertexCount x \< vertexCount y ==> x \< y
-- @
vertexCount :: Ord a => Graph a -> Int
vertexCount :: Graph a -> Int
vertexCount = Graph a -> Int
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Int
T.vertexCount
{-# RULES "vertexCount/Int" vertexCount = vertexIntCount #-}
{-# INLINE [1] vertexCount #-}

-- Like 'vertexCount' but specialised for Graph with vertices of type 'Int'.
vertexIntCount :: Graph Int -> Int
vertexIntCount :: Graph Int -> Int
vertexIntCount = 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
vertexIntSet

-- | 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/.
--
-- @
-- edgeCount ('vertex' x) == 0
-- edgeCount ('edge' x y) == 1
-- edgeCount            == 'length' . 'edgeList'
-- @
edgeCount :: Ord a => Graph a -> Int
edgeCount :: Graph a -> Int
edgeCount = Graph a -> Int
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Int
T.edgeCount
{-# INLINE [1] edgeCount #-}
{-# RULES "edgeCount/Int" edgeCount = edgeCountInt #-}

-- Like 'edgeCount' but specialised for graphs with vertices of type 'Int'.
edgeCountInt :: Graph Int -> Int
edgeCountInt :: Graph Int -> Int
edgeCountInt = AdjacencyIntMap -> Int
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Int
T.edgeCount (AdjacencyIntMap -> Int)
-> (Graph Int -> AdjacencyIntMap) -> Graph Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap

-- | The sorted list of vertices of a given graph.
-- Complexity: /O(s * log(n))/ time and /O(n)/ memory.
--
-- @
-- vertexList1 ('vertex' x)  == [x]
-- vertexList1 . 'vertices1' == 'Data.List.NonEmpty.nub' . 'Data.List.NonEmpty.sort'
-- @
vertexList1 :: Ord a => Graph a -> NonEmpty a
vertexList1 :: Graph a -> NonEmpty a
vertexList1 = [a] -> NonEmpty a
forall a. [a] -> NonEmpty a
NonEmpty.fromList ([a] -> NonEmpty a) -> (Graph a -> [a]) -> Graph a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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
{-# RULES "vertexList1/Int" vertexList1 = vertexIntList1 #-}
{-# INLINE [1] vertexList1 #-}

-- | Like 'vertexList1' but specialised for Graph with vertices of type 'Int'.
vertexIntList1 :: Graph Int -> NonEmpty Int
vertexIntList1 :: Graph Int -> NonEmpty Int
vertexIntList1 = [Int] -> NonEmpty Int
forall a. [a] -> NonEmpty a
NonEmpty.fromList ([Int] -> NonEmpty Int)
-> (Graph Int -> [Int]) -> Graph Int -> NonEmpty Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toAscList (IntSet -> [Int]) -> (Graph Int -> IntSet) -> Graph Int -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> IntSet
vertexIntSet

-- | 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/.
--
-- @
-- edgeList ('vertex' x)     == []
-- edgeList ('edge' x y)     == [(x,y)]
-- edgeList ('star' 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . 'edges1'       == 'Data.List.nub' . 'Data.List.sort' . 'Data.List.NonEmpty.toList'
-- edgeList . 'transpose'    == 'Data.List.sort' . 'map' 'Data.Tuple.swap' . edgeList
-- @
edgeList :: Ord a => Graph a -> [(a, a)]
edgeList :: Graph a -> [(a, a)]
edgeList = Graph a -> [(a, a)]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [(ToVertex t, ToVertex t)]
T.edgeList
{-# RULES "edgeList/Int" edgeList = edgeIntList #-}
{-# INLINE [1] edgeList #-}

-- Like 'edgeList' but specialised for Graph with vertices of type 'Int'.
edgeIntList :: Graph Int -> [(Int, Int)]
edgeIntList :: Graph Int -> [(Int, Int)]
edgeIntList = AdjacencyIntMap -> [(Int, Int)]
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> [(ToVertex t, ToVertex t)]
T.edgeList (AdjacencyIntMap -> [(Int, Int)])
-> (Graph Int -> AdjacencyIntMap) -> Graph Int -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph Int -> AdjacencyIntMap
forall t. (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
T.toAdjacencyIntMap

-- | The set of vertices of a given graph.
-- Complexity: /O(s * log(n))/ time and /O(n)/ memory.
--
-- @
-- vertexSet . 'vertex'    == Set.'Set.singleton'
-- vertexSet . 'vertices1' == Set.'Set.fromList' . 'Data.List.NonEmpty.toList'
-- vertexSet . 'clique1'   == Set.'Set.fromList' . 'Data.List.NonEmpty.toList'
-- @
vertexSet :: Ord a => Graph a -> Set.Set a
vertexSet :: Graph a -> Set a
vertexSet = Graph a -> Set a
forall t. (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t)
T.vertexSet

-- Like 'vertexSet' but specialised for graphs with vertices of type 'Int'.
vertexIntSet :: Graph Int -> IntSet.IntSet
vertexIntSet :: Graph Int -> IntSet
vertexIntSet = Graph Int -> IntSet
forall t. (ToGraph t, ToVertex t ~ Int) => t -> IntSet
T.vertexIntSet

-- | The set of edges of a given graph.
-- Complexity: /O(s * log(m))/ time and /O(m)/ memory.
--
-- @
-- edgeSet ('vertex' x) == Set.'Set.empty'
-- edgeSet ('edge' x y) == Set.'Set.singleton' (x,y)
-- edgeSet . 'edges1'   == Set.'Set.fromList' . 'Data.List.NonEmpty.toList'
-- @
edgeSet :: Ord a => Graph a -> Set.Set (a, a)
edgeSet :: Graph a -> Set (a, a)
edgeSet = Graph a -> Set (a, a)
forall t.
(ToGraph t, Ord (ToVertex t)) =>
t -> Set (ToVertex t, ToVertex t)
T.edgeSet

-- | The /path/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- @
-- path1 [x]       == 'vertex' x
-- path1 [x,y]     == 'edge' x y
-- path1 . 'Data.List.NonEmpty.reverse' == 'transpose' . path1
-- @
path1 :: NonEmpty a -> Graph a
path1 :: NonEmpty a -> Graph a
path1 (a
x :| []    ) = a -> Graph a
forall a. a -> Graph a
vertex a
x
path1 (a
x :| (a
y:[a]
ys)) = NonEmpty (a, a) -> Graph a
forall a. NonEmpty (a, a) -> Graph a
edges1 ((a
x, a
y) (a, a) -> [(a, a)] -> NonEmpty (a, a)
forall a. a -> [a] -> NonEmpty a
:| [a] -> [a] -> [(a, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys) [a]
ys)

-- | The /circuit/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- @
-- circuit1 [x]       == 'edge' x x
-- circuit1 [x,y]     == 'edges1' [(x,y), (y,x)]
-- circuit1 . 'Data.List.NonEmpty.reverse' == 'transpose' . circuit1
-- @
circuit1 :: NonEmpty a -> Graph a
circuit1 :: NonEmpty a -> Graph a
circuit1 (a
x :| [a]
xs) = NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
path1 (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x])

-- | The /clique/ on a list of vertices.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the length of the
-- given list.
--
-- @
-- clique1 [x]        == 'vertex' x
-- clique1 [x,y]      == 'edge' x y
-- clique1 [x,y,z]    == 'edges1' [(x,y), (x,z), (y,z)]
-- clique1 (xs '<>' ys) == 'connect' (clique1 xs) (clique1 ys)
-- clique1 . 'Data.List.NonEmpty.reverse'  == 'transpose' . clique1
-- @
clique1 :: NonEmpty a -> Graph a
clique1 :: NonEmpty a -> Graph a
clique1 = NonEmpty (Graph a) -> Graph a
forall a. NonEmpty (Graph a) -> Graph a
connects1 (NonEmpty (Graph a) -> Graph a)
-> (NonEmpty a -> NonEmpty (Graph a)) -> NonEmpty a -> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Graph a) -> NonEmpty a -> NonEmpty (Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Graph a
forall a. a -> Graph a
vertex
{-# NOINLINE [1] clique1 #-}

-- | 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.
--
-- @
-- biclique1 [x1,x2] [y1,y2] == 'edges1' [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
-- biclique1 xs      ys      == 'connect' ('vertices1' xs) ('vertices1' ys)
-- @
biclique1 :: NonEmpty a -> NonEmpty a -> Graph a
biclique1 :: NonEmpty a -> NonEmpty a -> Graph a
biclique1 NonEmpty a
xs NonEmpty a
ys = Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
connect (NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
vertices1 NonEmpty a
xs) (NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
vertices1 NonEmpty a
ys)

-- | 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.
--
-- @
-- star x []    == 'vertex' x
-- star x [y]   == 'edge' x y
-- star x [y,z] == 'edges1' [(x,y), (x,z)]
-- @
star :: a -> [a] -> Graph a
star :: a -> [a] -> Graph a
star a
x []     = a -> Graph a
forall a. a -> Graph a
vertex a
x
star a
x (a
y:[a]
ys) = 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) (NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
vertices1 (NonEmpty a -> Graph a) -> NonEmpty a -> Graph a
forall a b. (a -> b) -> a -> b
$ a
y a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
ys)
{-# INLINE star #-}

-- | The /stars/ formed by overlaying a non-empty list of 'star's.
-- Complexity: /O(L)/ time, memory and size, where /L/ is the total size of the
-- input.
--
-- @
-- stars1 [(x, [] )]               == 'vertex' x
-- stars1 [(x, [y])]               == 'edge' x y
-- stars1 [(x, ys )]               == 'star' x ys
-- stars1                          == 'overlays1' . 'fmap' ('uncurry' 'star')
-- 'overlay' (stars1 xs) (stars1 ys) == stars1 (xs '<>' ys)
-- @
stars1 :: NonEmpty (a, [a]) -> Graph a
stars1 :: NonEmpty (a, [a]) -> Graph a
stars1 = NonEmpty (Graph a) -> Graph a
forall a. NonEmpty (Graph a) -> Graph a
overlays1 (NonEmpty (Graph a) -> Graph a)
-> (NonEmpty (a, [a]) -> NonEmpty (Graph a))
-> NonEmpty (a, [a])
-> Graph a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, [a]) -> Graph a) -> NonEmpty (a, [a]) -> NonEmpty (Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((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)
{-# INLINE stars1 #-}

-- | 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 []]])                       == 'path1' [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 []]]) == 'edges1' [(1,2), (1,3), (3,4), (3,5)]
-- @
tree :: Tree.Tree a -> Graph a
tree :: Tree a -> Graph a
tree (Tree.Node a
x [Tree a]
f) = NonEmpty (Graph a) -> Graph a
forall a. NonEmpty (Graph a) -> Graph a
overlays1 (NonEmpty (Graph a) -> Graph a) -> NonEmpty (Graph a) -> Graph a
forall a b. (a -> b) -> a -> b
$ 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
Tree.rootLabel [Tree a]
f) Graph a -> [Graph a] -> NonEmpty (Graph a)
forall a. a -> [a] -> NonEmpty a
:| (Tree a -> Graph a) -> [Tree a] -> [Graph a]
forall a b. (a -> b) -> [a] -> [b]
map Tree a -> Graph a
forall a. Tree a -> Graph a
tree [Tree a]
f

-- | 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.
--
-- @
-- mesh1 [x]     [y]        == 'vertex' (x, y)
-- mesh1 xs      ys         == 'box' ('path1' xs) ('path1' ys)
-- mesh1 [1,2,3] [\'a\', \'b\'] == 'edges1' [ ((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\')) ]
-- @
mesh1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
mesh1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
mesh1 (a
x :| []) NonEmpty b
ys        = (a
x, ) (b -> (a, b)) -> Graph b -> Graph (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> NonEmpty b -> Graph b
forall a. NonEmpty a -> Graph a
path1 NonEmpty b
ys
mesh1 NonEmpty a
xs        (b
y :| []) = (, b
y) (a -> (a, b)) -> Graph a -> Graph (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
path1 NonEmpty a
xs
mesh1 xs :: NonEmpty a
xs@(a
x1 :| a
x2 : [a]
xt) ys :: NonEmpty b
ys@(b
y1 :| b
y2 : [b]
yt) =
    let star :: a -> a -> a -> Graph a
star a
i a
j a
o = (a -> Graph a
forall a. a -> Graph a
vertex a
i Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
`overlay` a -> Graph a
forall a. a -> Graph a
vertex a
j) 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
o
        innerStars :: Graph (a, b)
innerStars = NonEmpty (Graph (a, b)) -> Graph (a, b)
forall a. NonEmpty (Graph a) -> Graph a
overlays1 (NonEmpty (Graph (a, b)) -> Graph (a, b))
-> NonEmpty (Graph (a, b)) -> Graph (a, b)
forall a b. (a -> b) -> a -> b
$ do
                (a
x1, a
x2) <- NonEmpty a -> NonEmpty a -> NonEmpty (a, a)
forall a b. NonEmpty a -> NonEmpty b -> NonEmpty (a, b)
NonEmpty.zip NonEmpty a
xs (a
x2 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xt)
                (b
y1, b
y2) <- NonEmpty b -> NonEmpty b -> NonEmpty (b, b)
forall a b. NonEmpty a -> NonEmpty b -> NonEmpty (a, b)
NonEmpty.zip NonEmpty b
ys (b
y2 b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
:| [b]
yt)
                Graph (a, b) -> NonEmpty (Graph (a, b))
forall (m :: * -> *) a. Monad m => a -> m a
return (Graph (a, b) -> NonEmpty (Graph (a, b)))
-> Graph (a, b) -> NonEmpty (Graph (a, b))
forall a b. (a -> b) -> a -> b
$ (a, b) -> (a, b) -> (a, b) -> Graph (a, b)
forall a. a -> a -> a -> Graph a
star (a
x1, b
y2) (a
x2, b
y1) (a
x2, b
y2)
    in
    ((a
x1, ) (b -> (a, b)) -> Graph b -> Graph (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> NonEmpty b -> Graph b
forall a. NonEmpty a -> Graph a
path1 NonEmpty b
ys) Graph (a, b) -> Graph (a, b) -> Graph (a, b)
forall a. Graph a -> Graph a -> Graph a
`overlay` ((, b
y1) (a -> (a, b)) -> Graph a -> Graph (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
path1 NonEmpty a
xs) Graph (a, b) -> Graph (a, b) -> Graph (a, b)
forall a. Graph a -> Graph a -> Graph a
`overlay` Graph (a, b)
innerStars

-- | 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.
--
-- @
-- torus1 [x]   [y]        == 'edge' (x,y) (x,y)
-- torus1 xs    ys         == 'box' ('circuit1' xs) ('circuit1' ys)
-- torus1 [1,2] [\'a\', \'b\'] == 'edges1' [ ((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\')) ]
-- @
torus1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
torus1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
torus1 NonEmpty a
xs NonEmpty b
ys = NonEmpty ((a, b), [(a, b)]) -> Graph (a, b)
forall a. NonEmpty (a, [a]) -> Graph a
stars1 (NonEmpty ((a, b), [(a, b)]) -> Graph (a, b))
-> NonEmpty ((a, b), [(a, b)]) -> Graph (a, b)
forall a b. (a -> b) -> a -> b
$ do
    (a
x1, a
x2) <- NonEmpty a -> NonEmpty (a, a)
forall a. NonEmpty a -> NonEmpty (a, a)
pairs1 NonEmpty a
xs
    (b
y1, b
y2) <- NonEmpty b -> NonEmpty (b, b)
forall a. NonEmpty a -> NonEmpty (a, a)
pairs1 NonEmpty b
ys
    ((a, b), [(a, b)]) -> NonEmpty ((a, b), [(a, b)])
forall (m :: * -> *) a. Monad m => a -> m a
return ((a
x1, b
y1), [(a
x1, b
y2), (a
x2, b
y1)])
  where
    -- Turn a non-empty list into a cycle and return pairs of neighbours
    pairs1 :: NonEmpty a -> NonEmpty (a, a)
    pairs1 :: NonEmpty a -> NonEmpty (a, a)
pairs1 as :: NonEmpty a
as@(a
x :| [a]
xs) = NonEmpty a -> NonEmpty a -> NonEmpty (a, a)
forall a b. NonEmpty a -> NonEmpty b -> NonEmpty (a, b)
NonEmpty.zip NonEmpty a
as (NonEmpty a -> NonEmpty (a, a)) -> NonEmpty a -> NonEmpty (a, a)
forall a b. (a -> b) -> a -> b
$
        NonEmpty a
-> (NonEmpty a -> NonEmpty a) -> Maybe (NonEmpty a) -> NonEmpty a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| []) (NonEmpty a -> [a] -> NonEmpty a
forall a. NonEmpty a -> [a] -> NonEmpty a
`append1` [a
x]) ([a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
NonEmpty.nonEmpty [a]
xs)
    -- Append a list to a non-empty one
    append1 :: NonEmpty a -> [a] -> NonEmpty a
    append1 :: NonEmpty a -> [a] -> NonEmpty a
append1 (a
x :| [a]
xs) [a]
ys = a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| ([a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys)

-- | Remove a vertex from a given graph. Returns @Nothing@ if the resulting
-- graph is empty.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- removeVertex1 x ('vertex' x)          == Nothing
-- removeVertex1 1 ('vertex' 2)          == Just ('vertex' 2)
-- removeVertex1 x ('edge' x x)          == Nothing
-- removeVertex1 1 ('edge' 1 2)          == Just ('vertex' 2)
-- removeVertex1 x '>=>' removeVertex1 x == removeVertex1 x
-- @
removeVertex1 :: Eq a => a -> Graph a -> Maybe (Graph a)
removeVertex1 :: a -> Graph a -> Maybe (Graph a)
removeVertex1 a
x = (a -> Bool) -> Graph a -> Maybe (Graph a)
forall a. (a -> Bool) -> Graph a -> Maybe (Graph a)
induce1 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x)
{-# SPECIALISE removeVertex1 :: Int -> Graph Int -> Maybe (Graph Int) #-}

-- | Remove an edge from a given graph.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- removeEdge x y ('edge' x y)       == 'vertices1' [x,y]
-- removeEdge x y . removeEdge x y == removeEdge x y
-- 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
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)
G.context (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
s) (Graph a -> Graph (ToVertex (Graph a))
forall t. ToGraph t => t -> Graph (ToVertex t)
T.toGraph Graph a
g)
  where
    go :: Context a -> Graph a
go (G.Context [a]
is [a]
os) = (a -> Bool) -> Graph a -> Graph a
forall a. (a -> Bool) -> Graph a -> Graph a
G.induce (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=a
s) (Graph a -> Graph (ToVertex (Graph a))
forall t. ToGraph t => t -> Graph (ToVertex t)
T.toGraph Graph a
g)     Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
`overlay1`
                           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.
--
-- @
-- 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
{-# 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.
--
-- @
-- 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

-- | 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.
--
-- @
-- splitVertex1 x [x]                 == id
-- splitVertex1 x [y]                 == 'replaceVertex' x y
-- splitVertex1 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
-- @
splitVertex1 :: Eq a => a -> NonEmpty a -> Graph a -> Graph a
splitVertex1 :: a -> NonEmpty a -> Graph a -> Graph a
splitVertex1 a
v NonEmpty a
us Graph a
g = Graph a
g Graph a -> (a -> Graph a) -> Graph a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
w -> if a
w a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
v then NonEmpty a -> Graph a
forall a. NonEmpty a -> Graph a
vertices1 NonEmpty a
us else a -> Graph a
forall a. a -> Graph a
vertex a
w
{-# SPECIALISE splitVertex1 :: Int -> NonEmpty Int -> Graph Int -> Graph Int #-}

-- | Transpose a given graph.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- 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 = (a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> Graph a
-> Graph a
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 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) -> Graph a -> Graph a -> Graph a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
connect)
{-# NOINLINE [1] transpose #-}

{-# RULES
"transpose/Vertex"   forall x. transpose (Vertex x) = Vertex x
"transpose/Overlay"  forall g1 g2. transpose (Overlay g1 g2) = Overlay (transpose g1) (transpose g2)
"transpose/Connect"  forall g1 g2. transpose (Connect g1 g2) = Connect (transpose g2) (transpose g1)

"transpose/overlays1" forall xs. transpose (overlays1 xs) = overlays1 (fmap transpose xs)
"transpose/connects1" forall xs. transpose (connects1 xs) = connects1 (NonEmpty.reverse (fmap transpose xs))

"transpose/vertices1" forall xs. transpose (vertices1 xs) = vertices1 xs
"transpose/clique1"   forall xs. transpose (clique1 xs) = clique1 (NonEmpty.reverse xs)
 #-}

-- | Construct the /induced subgraph/ of a given graph by removing the
-- vertices that do not satisfy a given predicate. Returns @Nothing@ if the
-- resulting graph is empty.
-- Complexity: /O(s)/ time, memory and size, assuming that the predicate takes
-- constant time.
--
-- @
-- induce1 ('const' True ) x == Just x
-- induce1 ('const' False) x == Nothing
-- induce1 (/= x)          == 'removeVertex1' x
-- induce1 p '>=>' induce1 q == induce1 (\\x -> p x && q x)
-- @
induce1 :: (a -> Bool) -> Graph a -> Maybe (Graph a)
induce1 :: (a -> Bool) -> Graph a -> Maybe (Graph a)
induce1 a -> Bool
p = Graph (Maybe a) -> Maybe (Graph a)
forall a. Graph (Maybe a) -> Maybe (Graph a)
induceJust1 (Graph (Maybe a) -> Maybe (Graph a))
-> (Graph a -> Graph (Maybe a)) -> Graph a -> Maybe (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)

-- | Construct the /induced subgraph/ of a given graph by removing the vertices
-- that are 'Nothing'. Returns 'Nothing' if the resulting graph is empty.
-- Complexity: /O(s)/ time, memory and size.
--
-- @
-- induceJust1 ('vertex' 'Nothing')                               == 'Nothing'
-- induceJust1 ('edge' ('Just' x) 'Nothing')                        == 'Just' ('vertex' x)
-- induceJust1 . 'fmap' 'Just'                                    == 'Just'
-- induceJust1 . 'fmap' (\\x -> if p x then 'Just' x else 'Nothing') == 'induce1' p
-- @
induceJust1 :: Graph (Maybe a) -> Maybe (Graph a)
induceJust1 :: Graph (Maybe a) -> Maybe (Graph a)
induceJust1 = (Maybe a -> Maybe (Graph a))
-> (Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a))
-> (Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a))
-> Graph (Maybe a)
-> Maybe (Graph a)
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 ((a -> Graph a) -> Maybe a -> Maybe (Graph a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Graph a
forall a. a -> Graph a
Vertex) ((Graph a -> Graph a -> Graph a)
-> Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a)
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Overlay) ((Graph a -> Graph a -> Graph a)
-> Maybe (Graph a) -> Maybe (Graph a) -> Maybe (Graph a)
forall t. (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k Graph a -> Graph a -> Graph a
forall a. Graph a -> Graph a -> Graph a
Connect)
  where
    k :: (t -> t -> t) -> Maybe t -> Maybe t -> Maybe t
k t -> t -> t
_ Maybe t
Nothing  Maybe t
a        = Maybe t
a
    k t -> t -> t
_ Maybe t
a        Maybe t
Nothing  = Maybe t
a
    k t -> t -> t
f (Just t
a) (Just t
b) = t -> Maybe t
forall a. a -> Maybe a
Just (t -> t -> t
f t
a t
b)

-- | 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.
--
-- @
-- simplify             ==  id
-- 'size' (simplify x)    <=  'size' x
-- 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 = (a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> (Graph a -> Graph a -> Graph a)
-> Graph a
-> Graph a
forall a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 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)
{-# 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 :: (Graph Int -> Graph Int -> Graph Int) -> Graph Int -> Graph Int -> Graph Int #-}

-- | 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 ('path1' [0,1]) ('path1' [\'a\',\'b\']) == 'edges1' [ ((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', and has
-- singleton graphs as /identities/. 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
-- '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 = (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 a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 ((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 = (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 a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 ((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 ((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 a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 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
    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
$ NonEmpty (Either a b) -> Graph (Either a b)
forall a. NonEmpty a -> Graph a
clique1 (a -> Either a b
forall a b. a -> Either a b
Left a
s Either a b -> [Either a b] -> NonEmpty (Either a b)
forall a. a -> [a] -> NonEmpty a
:| [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 -> 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 a b.
(a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
foldg1 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)
    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