module Data.Graph.Inductive.Query.TransClos(
    trc, rc, tc
) where

import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query.BFS (bfen)

{-|
Finds the transitive closure of a directed graph.
Given a graph G=(V,E), its transitive closure is the graph:
G* = (V,E*) where E*={(i,j): i,j in V and there is a path from i to j in G}
-}
tc :: (DynGraph gr) => gr a b -> gr a ()
tc :: forall (gr :: * -> * -> *) a b. DynGraph gr => gr a b -> gr a ()
tc gr a b
g = [(Node, Node, ())]
newEdges forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LNode a]
labNodes gr a b
g
    newEdges :: [(Node, Node, ())]
newEdges = [ (Node
u, Node
v, ()) | (Node
u, a
_) <- [LNode a]
ln, (Node
_, Node
v) <- forall (gr :: * -> * -> *) a b.
Graph gr =>
[(Node, Node)] -> gr a b -> [(Node, Node)]
bfen (forall {gr :: * -> * -> *} {a} {b}.
Graph gr =>
gr a b -> Node -> [(Node, Node)]
outU gr a b
g Node
u) gr a b
g ]
    outU :: gr a b -> Node -> [(Node, Node)]
outU gr a b
gr  = forall a b. (a -> b) -> [a] -> [b]
map forall b. LEdge b -> (Node, Node)
toEdge forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (gr :: * -> * -> *) a b.
Graph gr =>
gr a b -> Node -> [LEdge b]
out gr a b
gr

{-|
Finds the reflexive-transitive closure of a directed graph.
Given a graph G=(V,E), its reflexive-transitive closure is the graph:
G* = (V,E*) where E*={(i,j): i,j in V and either i = j or there is a path from i to j in G}
-}
trc :: (DynGraph gr) => gr a b -> gr a ()
trc :: forall (gr :: * -> * -> *) a b. DynGraph gr => gr a b -> gr a ()
trc gr a b
g = [(Node, Node, ())]
newEdges forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LNode a]
labNodes gr a b
g
    newEdges :: [(Node, Node, ())]
newEdges = [ (Node
u, Node
v, ()) | (Node
u, a
_) <- [LNode a]
ln, (Node
_, Node
v) <- forall (gr :: * -> * -> *) a b.
Graph gr =>
[(Node, Node)] -> gr a b -> [(Node, Node)]
bfen [(Node
u, Node
u)] gr a b
g ]

{-|
Finds the reflexive closure of a directed graph.
Given a graph G=(V,E), its reflexive closure is the graph:
G* = (V,Er union E) where Er = {(i,i): i in V}
-}
rc :: (DynGraph gr) => gr a b -> gr a ()
rc :: forall (gr :: * -> * -> *) a b. DynGraph gr => gr a b -> gr a ()
rc gr a b
g = ([(Node, Node, ())]
newEdges forall a. [a] -> [a] -> [a]
++ [(Node, Node, ())]
oldEdges) forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LNode a]
labNodes gr a b
g
    newEdges :: [(Node, Node, ())]
newEdges = [ (Node
u, Node
u, ()) | (Node
u, a
_) <- [LNode a]
ln ]
    oldEdges :: [(Node, Node, ())]
oldEdges = [ (Node
u, Node
v, ()) | (Node
u, Node
v, b
_) <- forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LEdge b]
labEdges gr a b
g ]