Institute of Computer Science
Faculty of Engineering, Christian-Albrechts-University of Kiel
| Computer-Aided Program
Development Institute of Computer Science Faculty of Engineering, Christian-Albrechts-University of Kiel |
|
| RelView Examples - Graph-theoretic Algorithms |
{************************************************************
Computation of the vector of cutpoints (articulation points)
of an undirected and loop-free graph using DFS and a charac-
terization of cutpoints given in Lemma 5.5 of the textbook
"The design and analysis of computer algorithms" from Aho,
Hopcroft, and Ullman. Confer p. 182
************************************************************}
CutPoints(E)
DECL F, B, C, c
BEG F = Dfs(E);
C = rtc(F);
B = C^ & E;
c = (-dom(F^) & dom(F*-I(F)*F^ & I(F))) |
(dom(F^) & dom(F & ((ipa(C) \ -B^) / C)))
RETURN c
END.
{************************************************************
Computation of the dominator tree of a rooted directed and
acyclic graph g = (V,R) with root init(L) following a idea
of the Aho-Ullman book
************************************************************}
DominatorTree(R)
DECL del(R,x) = R & -(x*L1n(R)) & -(Ln1(R)*x^);
reach(R,x) = (x^ * rtc(R))^;
T, v, i, p, q
BEG i = init(Ln1(R));
T = ipa(i * L1n(R));
p = next(i);
WHILE -empty(next(p)) DO
v = -(reach(del(R,p),i) | p);
WHILE -empty(v) DO
q = point(v);
IF eq(T*p,T*q)
THEN T = (T & -(Ln1(R)*q^)) | p*q^ FI;
v = v & -q
OD;
p = next(p)
OD
RETURN T
END.
{************************************************************
Computation of a closed Eulerian path in an undirected, Eu-
lerian graph using the algorithm of Fleury. The result is a
relation which - from left to righy - column-wise describes
the list of points
************************************************************}
EulerPath(E)
DECL edge(E) = atom(E) | atom(E)^;
isbridge(E,e) = -incl(e,trans(E & -e));
v, S, e, C, Res
BEG v = point(Ln1(E));
S = E;
Res = v;
WHILE -empty(S) DO
C = S & ((v*L1n(S)) | (v*L1n(S))^);
IF empty(C & -edge(C)) THEN e = C
ELSE e = edge(C);
C = C & -e;
WHILE isbridge(S,e) DO
e = edge(C);
C = C & -e
OD FI;
v = e * v;
S = S & -e;
Res = conc(Res,v)
OD
RETURN Res
END.
{************************************************************
Computation of a directed spanning tree of a connected and
undirected graph following Prim's method
************************************************************}
Prim(E)
DECL T, v
BEG T = O(E);
v = point(dom(E));
WHILE -empty(-v) DO
T = T | atom(v * -v^ & E);
v = v | ran(T)
OD
RETURN T
END.
{***********************************************************
Computation of a spanning forest of an undirected graph
with Kruskal's method using a relational implementation
of the union-find structure (initial, find, union)
***********************************************************}
Kruskal(E)
DECL initial(E) = O(E);
find(C,x) = rtc(C)^ * x & -dom(C);
union(C,x,y) = C | y * x^;
K, F, C, e, x, y
BEG K = E;
F = O(E);
C = initial(E);
WHILE -empty(K) DO
e = atom(K);
x = find(C,dom(e));
y = find(C,ran(e));
IF eq(x,y) THEN K = K & -(e | e^)
ELSE K = K & -(e | e^);
F = F | e | e^;
C = union(C,x,y) FI
OD
RETURN F
END.
{***********************************************************
Computation of an inclusion maximal forest of a undirected
graph using J. Ravelo's development (see RelMiCS 3 procee-
dings pages 291-300)
***********************************************************}
MaximalForest(E)
DECL F, K, C, e
BEG F = O(E);
K = E;
C = I(E);
WHILE -empty(K) DO
e = atom(K);
IF -incl(e,C) THEN F = F | e | e^;
C = C * (I(E) | e | e^) * C ;
K = K & -(e | e^)
ELSE K = K & -(e | e^) FI
OD
RETURN F
END.
{************************************************************
Computation of a hamiltonian circuit of a directed graph if
it exists. Otherwise the result is empty. The program uses
the backtracking approach as presented by A. Srivastav in
the Fortgeschrittenenpraktikum at Kiel University, SS 1999
************************************************************}
Ham(R,v,m,s)
DECL n, w, p, res
BEG res = O(R);
n = m | v;
IF empty(-n)
THEN IF incl(s,R^*v) THEN res = v * s^ FI
ELSE w = R^ * v & -n;
WHILE -empty(w) & empty(res) DO
p = point(w);
w = w & -p;
res = Ham(R,p,n,s)
OD;
IF -empty(res) THEN res = v * p^ | res FI FI
RETURN res
END.
Hamilton(R)
DECL p
BEG p = point(Ln1(R))
RETURN Ham(R,p,O(p),p)
END.
{************************************************************
Computation of the reflexive transitive closure of a direc-
ted graph using Warshall's approach (see RelMiCS 1 volume)
************************************************************}
Warshall(R)
DECL Q, p, x
BEG Q = R;
x = Ln1(R);
WHILE -empty(x) DO
p = point(x);
Q = Q | (Q * p) * (p^ * Q);
x = x & -p
OD
RETURN I(R) | Q
END.
{************************************************************
Enumeration of the kernels of an arbitrary directed graph
following the HOA 93 paper of Berghammer et al.
************************************************************}
KernelVector(R)
DECL absorb(R,e,O) = -(e | R * e) \ O;
stable(R,e,O) = (e & R * e) \ O;
Epsi
BEG Epsi = epsi(dom(R))
RETURN absorb(R,Epsi,On1(R)) & stable(R,Epsi,On1(R))
END.
KernelList(R)
DECL Res
BEG Res = epsi(dom(R)) * inj(KernelVector(R))^
RETURN Res
END.
{************************************************************
Computation of a kernel of a bichromatic directed graph fol-
lowing von Karger and Berghammer (see IPL 1997). Input is a
pair (R,B) of relations which constitutes a 2-colouring of
the arcs
************************************************************}
KernelBichrom(R,B)
DECL m, n, r, x
BEG m = On1(R);
x = -dom(R);
WHILE -eq(m,x) DO
m = x;
x = -(R * -(R * m))
OD;
n = Ln1(R);
x = -(R * -dom(R));
WHILE -eq(n,x) DO
n = x;
x = -(R * -(R * n))
OD;
r = n & -m
RETURN m | (r & -(B * r))
END.
{************************************************************
Computation of a kernel of a bipartite directed graph follo-
wing the book of Schmidt and Stroehlein. Input is the assoc-
iated relation B. The program first computes a vector which
defines a bipartition
************************************************************}
Bipart(B)
DECL Q, Res, v, w
BEG Q = B | B^;
IF incl(rtc(Q*Q)*Q,-I(B))
THEN v = rtc(Q*Q) * point(Ln1(B));
w = v | Q * v;
WHILE -eq(w,Ln1(w)) DO
v = v | rtc(Q*Q) * point(-w);
w = v | Q * v
OD;
Res = v
ELSE Res = error FI
RETURN Res
END.
KernelB(B)
DECL tau(B,x) = -(B * -(B * x));
b, k1, k2, v
BEG b = Bipart(B);
k1 = O(b);
v = tau(B,k1);
WHILE -eq(k1,v) DO
k1 = v;
v = tau(B,k1)
OD;
k2 = L(b);
v = tau(B,k2);
WHILE -eq(k2,v) DO
k2 = v;
v = tau(B,k2)
OD
RETURN (b & k2) | (-b & k1)
END.
{************************************************************
Computation of a kernel of a bipartite directed graph follo-
wing the the HOA 93 paper of Berghammer et al. Input are two
relations R : X <-> Y and S : Y <-> X which constitute a bi
partition of B : X+Y <-> X+Y
************************************************************}
KernelRS(R,S)
DECL alpha(R,x) = -(R * x);
beta(S,y) = -(S * y);
k, v, w
BEG k = Ln1(R);
v = alpha(R,beta(S,k));
WHILE -eq(k,v) DO
k = v;
v = alpha(R,beta(S,k))
OD;
k = On1(S);
w = beta(S,alpha(R,k));
WHILE -eq(k,w) DO
k = w;
w = beta(S,alpha(R,k))
OD
RETURN v + w
END.
{************************************************************
Computation of the only kernel of a Noetherian (cycle-free)
directed graph as least fixed point of the monotone mapping
tau(x) = -(R * -(R * x)); see Schmidt and Stroehlein book
************************************************************}
KernelCf(R)
DECL k, v
BEG k = On1(R);
v = -(R * -(R * k));
WHILE -eq(k,v) DO
k = v;
v = -(R * -(R * k))
OD
RETURN k
END.
{************************************************************
Computation of the column-wise representation of the strong-
ly connected components of a directed graph
************************************************************}
Scc(R)
DECL B, S, p, x
BEG B = rtc(R) & rtc(R)^;
S = B * point(Ln1(R));
x = -S;
WHILE -empty(x) DO
p = point(x);
S = conc(S, B * p);
x = x & -(B * p)
OD
RETURN S
END.
{************************************************************
Computation of a vertex base of a directed graph by taking
exactly one vertex from each initial strongly connected com-
ponent
************************************************************}
VertexBase(R)
DECL S, v, c, b
BEG S = rtc(R) & rtc(R^);
c = S * point(Ln1(S));
IF incl(R*c,c) THEN b = point(c)
ELSE b = O(c) FI;
v = -c;
WHILE -empty(v) DO
c = S * point(v);
IF incl(R*c,c) THEN b = b | point(c) FI;
v = v & -c
OD
RETURN b
END.
{************************************************************
Computation of an inclusion maximum matching of an arbitrary
undirected and loop-free graph (see scriptum of Emden-Weinert
et al.)
************************************************************}
MaximalMatch(R)
DECL M, H, e, v
BEG M = O(R);
H = R;
WHILE -empty(H) DO
e = atom(H);
v = dom(e) | ran(e);
M = M | e | e^;
H = del(H,v)
OD
RETURN M
END.
{************************************************************
Computation of a maximum matching of bipartite graph using
the program of Thomas Bache, Alexandra Bunge, and Christian
Kasper from the Fortgeschrittenenpraktikum "Effiziente Al-
gorithmen" WS 99/00 Uni Kiel
************************************************************}
AltPath(R,M,MT,RohneM,RohneMT,v,b)
DECL erg, vR, vRR, x, y, z
BEG vR = (RohneM * v);
IF incl(b,vR)
THEN erg = atom((v * b^) & RohneM)
ELSE vRR = MT * vR;
erg = AltPath(R,M,MT,RohneM,RohneMT,vRR,b);
z = dom(erg) & -dom(erg^);
y = point((M * z) & vR);
x = point((RohneM * y) & v);
erg = erg | x * y^ | y * z^ FI
RETURN erg
END.
AugPath(R,M,RmM) = rtc(RmM * M) * RmM & -(L(M) * M) & -(M * L(M)).
MaximumMatch(R)
DECL symDiff(A,B) = (A & -B) | (B & -A);
M, RohneM, AltP, a, b, H, ab
BEG M = MaximalMatch(R); {* instead of O(R) *}
RohneM = R & -M;
H = AugPath(R,M,RohneM);
WHILE -empty(H) DO
ab = atom(H);
a = dom(ab);
b = ran(ab);
AltP = sc(AltPath(R,M,M^,RohneM,RohneM^,a,b));
M = symDiff(M,AltP);
RohneM = R & -M;
H = AugPath(R,M,RohneM)
OD
RETURN M
END.
{************************************************************
Computation of the transitive reduction of a cyclefree di-
rected graph by inverting Warshall's algorithm
************************************************************}
TransRedCf(R)
DECL Q, p, x
BEG Q = trans(R);
x = Ln1(R);
WHILE -empty(x) DO
p = point(x);
Q = Q & -((Q * p) * (p^ * Q));
x = x & -p
OD
RETURN Q
END.
{************************************************************
Computation of a topological sorting of a cyclefree directed
graph by removing sources again and again. Result is a line-
ar strict-order in which the graph's relation can be embed-
ded
************************************************************}
TopSortOrd(R)
DECL Res, v, p
BEG Res = O(R);
v = point(sources(R));
WHILE -universal(v) DO
p = point(-v & -(R^ * -v));
Res = Res | (v & -p) * p^;
v = v | p
OD
RETURN Res
END.
{************************************************************
Fast version of a BFS program which is due to Thorsten
Hoffmann (Ph.D thesis, Kiel University, 2002)
************************************************************}
Bfs(R,s)
DECL T, a, p, u, v, w, x, y
BEG v = s;
x = s;
y = R^ * x & -v;
T = v * y^;
WHILE -empty(y) DO
v = v | y;
x = y;
y = R^ * x & -v;
u = x;
w = y;
WHILE -empty(w) DO
p = point(u);
a = R^ * p & w;
T = T | p * a^;
u = u & -p;
w = w & -a
OD
OD
RETURN T
END.
{************************************************************
Iterative computation of the directed dfs-forest of a di-
rected graph g = (V,R) following Thorsten Hoffmann's ap-
proach (Ph.D. thesis, Kiel University, 2002). The argument
W of Dfs is an ordering on the vertices which determines
how the succes- sors of a vertex are visited
************************************************************}
DfsTree(R,W,v,r)
DECL p, q, w, T
BEG T = O(R);
w = v | r;
p = r;
WHILE -empty(p) DO
q = min(W,R^*p & -w);
IF empty(q) THEN p = T * p
ELSE w = w | q;
T = T | p * q^;
p = q FI
OD
RETURN T
END.
Dfs(R,W)
DECL v, r, F, T
BEG F = O(R);
v = On1(R);
WHILE -empty(-v) DO
r = min(W,-v);
T = DfsTree(R,W,v,r);
F = F | T;
v = v | r | ran(F)
OD
RETURN F
END.