1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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 g = newEdges `insEdges` insNodes ln empty
where
ln = labNodes g
newEdges = [ (u, v, ()) | (u, _) <- ln, (_, v) <- bfen (outU g u) g ]
outU gr = map toEdge . out 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 g = newEdges `insEdges` insNodes ln empty
where
ln = labNodes g
newEdges = [ (u, v, ()) | (u, _) <- ln, (_, v) <- bfen [(u, u)] 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 g = (newEdges ++ oldEdges) `insEdges` insNodes ln empty
where
ln = labNodes g
newEdges = [ (u, u, ()) | (u, _) <- ln ]
oldEdges = [ (u, v, ()) | (u, v, _) <- labEdges g ]
|
