Computer-Aided Program Development
Institute of Computer Science
Faculty of Engineering, Christian-Albrechts-University of Kiel
Logo of the Working Group
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.


 
Rudolf Berghammer - rub@informatik.uni-kiel.de
Last modified: 15-Aug-2012, 11:02:12 CEST