-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.Relation.Transitive
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- An abstract implementation of transitive binary relations. Use
-- "Algebra.Graph.Class" for polymorphic construction and manipulation.
-----------------------------------------------------------------------------
module Algebra.Graph.Relation.Transitive (
    -- * Data structure
    TransitiveRelation, fromRelation, toRelation
    ) where

import Algebra.Graph.Relation
import Control.DeepSeq
import Data.String

import qualified Algebra.Graph.Class as C

-- TODO: Optimise the implementation by caching the results of transitive closure.
{-| The 'TransitiveRelation' data type represents a /transitive binary relation/
over a set of elements. Transitive relations satisfy all laws of the
'Transitive' type class and, in particular, the /closure/ axiom:

@y /= 'empty' ==> x * y + x * z + y * z == x * y + y * z@

For example, the following holds:

@'path' xs == ('clique' xs :: TransitiveRelation Int)@

The 'Show' instance produces transitively closed expressions:

@show (1 * 2         :: TransitiveRelation Int) == "edge 1 2"
show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"@
-}
newtype TransitiveRelation a = TransitiveRelation { TransitiveRelation a -> Relation a
fromTransitive :: Relation a }
    deriving (String -> TransitiveRelation a
(String -> TransitiveRelation a) -> IsString (TransitiveRelation a)
forall a. IsString a => String -> TransitiveRelation a
forall a. (String -> a) -> IsString a
fromString :: String -> TransitiveRelation a
$cfromString :: forall a. IsString a => String -> TransitiveRelation a
IsString, TransitiveRelation a -> ()
(TransitiveRelation a -> ()) -> NFData (TransitiveRelation a)
forall a. NFData a => TransitiveRelation a -> ()
forall a. (a -> ()) -> NFData a
rnf :: TransitiveRelation a -> ()
$crnf :: forall a. NFData a => TransitiveRelation a -> ()
NFData, Integer -> TransitiveRelation a
TransitiveRelation a -> TransitiveRelation a
TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
(TransitiveRelation a
 -> TransitiveRelation a -> TransitiveRelation a)
-> (TransitiveRelation a
    -> TransitiveRelation a -> TransitiveRelation a)
-> (TransitiveRelation a
    -> TransitiveRelation a -> TransitiveRelation a)
-> (TransitiveRelation a -> TransitiveRelation a)
-> (TransitiveRelation a -> TransitiveRelation a)
-> (TransitiveRelation a -> TransitiveRelation a)
-> (Integer -> TransitiveRelation a)
-> Num (TransitiveRelation a)
forall a. (Ord a, Num a) => Integer -> TransitiveRelation a
forall a.
(Ord a, Num a) =>
TransitiveRelation a -> TransitiveRelation a
forall a.
(Ord a, Num a) =>
TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> TransitiveRelation a
$cfromInteger :: forall a. (Ord a, Num a) => Integer -> TransitiveRelation a
signum :: TransitiveRelation a -> TransitiveRelation a
$csignum :: forall a.
(Ord a, Num a) =>
TransitiveRelation a -> TransitiveRelation a
abs :: TransitiveRelation a -> TransitiveRelation a
$cabs :: forall a.
(Ord a, Num a) =>
TransitiveRelation a -> TransitiveRelation a
negate :: TransitiveRelation a -> TransitiveRelation a
$cnegate :: forall a.
(Ord a, Num a) =>
TransitiveRelation a -> TransitiveRelation a
* :: TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
$c* :: forall a.
(Ord a, Num a) =>
TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
- :: TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
$c- :: forall a.
(Ord a, Num a) =>
TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
+ :: TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
$c+ :: forall a.
(Ord a, Num a) =>
TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
Num)

instance Ord a => Eq (TransitiveRelation a) where
    TransitiveRelation a
x == :: TransitiveRelation a -> TransitiveRelation a -> Bool
== TransitiveRelation a
y = TransitiveRelation a -> Relation a
forall a. Ord a => TransitiveRelation a -> Relation a
toRelation TransitiveRelation a
x Relation a -> Relation a -> Bool
forall a. Eq a => a -> a -> Bool
== TransitiveRelation a -> Relation a
forall a. Ord a => TransitiveRelation a -> Relation a
toRelation TransitiveRelation a
y

instance Ord a => Ord (TransitiveRelation a) where
    compare :: TransitiveRelation a -> TransitiveRelation a -> Ordering
compare TransitiveRelation a
x TransitiveRelation a
y = Relation a -> Relation a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (TransitiveRelation a -> Relation a
forall a. Ord a => TransitiveRelation a -> Relation a
toRelation TransitiveRelation a
x) (TransitiveRelation a -> Relation a
forall a. Ord a => TransitiveRelation a -> Relation a
toRelation TransitiveRelation a
y)

instance (Ord a, Show a) => Show (TransitiveRelation a) where
    show :: TransitiveRelation a -> String
show = Relation a -> String
forall a. Show a => a -> String
show (Relation a -> String)
-> (TransitiveRelation a -> Relation a)
-> TransitiveRelation a
-> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TransitiveRelation a -> Relation a
forall a. Ord a => TransitiveRelation a -> Relation a
toRelation

-- TODO: To be derived automatically using GeneralizedNewtypeDeriving in GHC 8.2
instance Ord a => C.Graph (TransitiveRelation a) where
    type Vertex (TransitiveRelation a) = a
    empty :: TransitiveRelation a
empty       = Relation a -> TransitiveRelation a
forall a. Relation a -> TransitiveRelation a
TransitiveRelation Relation a
forall a. Relation a
empty
    vertex :: Vertex (TransitiveRelation a) -> TransitiveRelation a
vertex      = Relation a -> TransitiveRelation a
forall a. Relation a -> TransitiveRelation a
TransitiveRelation (Relation a -> TransitiveRelation a)
-> (a -> Relation a) -> a -> TransitiveRelation a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Relation a
forall a. a -> Relation a
vertex
    overlay :: TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
overlay TransitiveRelation a
x TransitiveRelation a
y = Relation a -> TransitiveRelation a
forall a. Relation a -> TransitiveRelation a
TransitiveRelation (Relation a -> TransitiveRelation a)
-> Relation a -> TransitiveRelation a
forall a b. (a -> b) -> a -> b
$ TransitiveRelation a -> Relation a
forall a. TransitiveRelation a -> Relation a
fromTransitive TransitiveRelation a
x Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
`overlay` TransitiveRelation a -> Relation a
forall a. TransitiveRelation a -> Relation a
fromTransitive TransitiveRelation a
y
    connect :: TransitiveRelation a
-> TransitiveRelation a -> TransitiveRelation a
connect TransitiveRelation a
x TransitiveRelation a
y = Relation a -> TransitiveRelation a
forall a. Relation a -> TransitiveRelation a
TransitiveRelation (Relation a -> TransitiveRelation a)
-> Relation a -> TransitiveRelation a
forall a b. (a -> b) -> a -> b
$ TransitiveRelation a -> Relation a
forall a. TransitiveRelation a -> Relation a
fromTransitive TransitiveRelation a
x Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
`connect` TransitiveRelation a -> Relation a
forall a. TransitiveRelation a -> Relation a
fromTransitive TransitiveRelation a
y

instance Ord a => C.Transitive (TransitiveRelation a)

-- | Construct a transitive relation from a 'Relation'.
-- Complexity: /O(1)/ time.
fromRelation :: Relation a -> TransitiveRelation a
fromRelation :: Relation a -> TransitiveRelation a
fromRelation = Relation a -> TransitiveRelation a
forall a. Relation a -> TransitiveRelation a
TransitiveRelation

-- | Extract the underlying relation.
-- Complexity: /O(n * m * log(m))/ time.
toRelation :: Ord a => TransitiveRelation a -> Relation a
toRelation :: TransitiveRelation a -> Relation a
toRelation = Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a
transitiveClosure (Relation a -> Relation a)
-> (TransitiveRelation a -> Relation a)
-> TransitiveRelation a
-> Relation a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TransitiveRelation a -> Relation a
forall a. TransitiveRelation a -> Relation a
fromTransitive