    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 [(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 a b. gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty
      where
        ln :: [LNode a]
    ln       = gr a b -> [LNode a]
    forall a b. 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 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 [(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 a b. gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty
      where
        ln :: [LNode a]
    ln       = gr a b -> [LNode a]
    forall a b. 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 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 [(Node, Node, ())] -> [(Node, Node, ())] -> [(Node, Node, ())]
    forall a. [a] -> [a] -> [a]
    ++ [(Node, Node, ())]
    oldEdges) [(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 a b. gr a b
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b
    empty
      where
        ln :: [LNode a]
    ln       = gr a b -> [LNode a]
    forall a b. 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 ]
        oldEdges :: [(Node, Node, ())]
    oldEdges = [ (Node
    u, Node
    v, ()) | (Node
    u, Node
    v, b
    _) <- gr a b -> [(Node, Node, b)]
    forall a b. gr a b -> [LEdge b]
    forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [LEdge b]
    labEdges gr a b
    g ]