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 :: gr a b -> gr a ()
tc gr a b
g = [(Node, Node, ())]
newEdges [(Node, Node, ())] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` [LNode a] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln gr a ()
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = gr a b -> [LNode a]
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) <- [(Node, Node)] -> gr a b -> [(Node, Node)]
forall (gr :: * -> * -> *) a b.
Graph gr =>
[(Node, Node)] -> gr a b -> [(Node, Node)]
bfen (gr a b -> Node -> [(Node, Node)]
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  = (LEdge b -> (Node, Node)) -> [LEdge b] -> [(Node, Node)]
forall a b. (a -> b) -> [a] -> [b]
map LEdge b -> (Node, Node)
forall b. LEdge b -> (Node, Node)
toEdge ([LEdge b] -> [(Node, Node)])
-> (Node -> [LEdge b]) -> Node -> [(Node, Node)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. gr a b -> Node -> [LEdge b]
forall (gr :: * -> * -> *) a b.
Graph gr =>
gr a b -> Node -> [LEdge b]
out gr a b
gr

{-|
Finds the transitive, reflexive 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 either i = j or there is a path from i to j in G}
-}
trc :: (DynGraph gr) => gr a b -> gr a ()
trc :: gr a b -> gr a ()
trc gr a b
g = [(Node, Node, ())]
newEdges [(Node, Node, ())] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` [LNode a] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln gr a ()
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = gr a b -> [LNode a]
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) <- [(Node, Node)] -> gr a b -> [(Node, Node)]
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 transitive 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 :: gr a b -> gr a ()
rc gr a b
g = [(Node, Node, ())]
newEdges [(Node, Node, ())] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) b a.
DynGraph gr =>
[LEdge b] -> gr a b -> gr a b
`insEdges` [LNode a] -> gr a () -> gr a ()
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
[LNode a] -> gr a b -> gr a b
insNodes [LNode a]
ln gr a ()
forall (gr :: * -> * -> *) a b. Graph gr => gr a b
empty
  where
    ln :: [LNode a]
ln       = gr a b -> [LNode a]
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 ]