Collected Algorithms from the CACM

Algorithm 491

Basic Cycle Generation

Norman E. Gibbs [Recd. 13 July 1971]
Department of Mathematics, College of William and Mary, Williamsburg, VA 23185

This work was partially supported by NASA under Grant NGL-47-006-058.

Key Words and Phrases:
Graphs, basic cycle, fundamental cycle, spanning tree, vertex adjacency matrix
CR Categories:
5.32, 3.24
Language:
PL/I

Description

The PL/I procedure BASIC_GENERATOR is an implementation of Paton's algorithm [1] for finding a set of basic (fundamental) cycles of a finite undirected graph from its vertex adjacency matrix.

The input parameters to the procedure are:

  1. A modified form of the vertex adjacency matrix, called A (see assumption 3 below).
  2. The number of vertices of the graph, called N.
  3. The number of edges of the graph, called EDGES.

The output of the procedure is an array of bit strings, called B. The jth bit of Bi is 1 if and only if the ith basic cycle contains the edge labelled j.

The following assumptions are made by the procedure:

  1. The graph is finite, connected, undirected, and without loops or multiple edges
  2. The vertices are labelled 1, 2, …, N.
  3. The vertex adjacency matrix A has an adge table coded into its lower triangular part. The following PL/I code could be used to generate the table: 
    
E = 0;
DO I = 2 TO N;
 DO J = 1 TO I - 1;
  IF A(I,J) ! = 0 THEN
   DO;
    E = E + 1;
    A(I,J) = E;
   END;
 END;
END;
  4. A is not the vertex adjacency matrix of a tree.

The algorithm is:

Step 1.
Let vertex 1 be the root of the spanning tree. Start forming the spanning tree by placing all edges of the form {1,W} into the the tree. At the same time, place all vertices W into a push-down list called STACK.
Step 2.
Lat Z be the last vertex added to STACK (i.e. the top of the stack). If STACK is empty then stop. If STACK is not empty, then remove Z from STACK and go to step 3.
Step 3.
Consider all edges {Z, W} which have not been examined. If all edges have been examined, go to step 2. Otherwise, for each edge {Z, W} do the following:
  1. If W is in the tree generate the basic cycle formed by adding {Z, W} to the tree and repeat step 3.
  2. If W is not in the tree, add {Z, W} to the tree, W to STACK, and repeat step 3.

For details on the algorithm and the production of the basic cycles, Paton's original paper should be consulted. This paper also discusses two other algorithms for basic cycle generation and contains performance statistics.

BASIC_GENERATOR has been implemented using the IBM PL/I F-level compiler (version 5.1) and has been tested on approximately 200 graphs

Reference

  1. Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.

Algorithm


BASIC_GENERATOR:
PROCEDURE (A,N,EDGES,B);
/*  BASIC_GENERATOR GENERATES A SET OF BASIC (FUNDAMENTAL)
    CYCLES FROM THE VERTES ADJACENCY MATRIX OF A CONNECTED 
    UNIDIRECTED GRAPH WITHOUT LOOPS OF MULTIPLE EDGES. THE
    PROCEDURE IS A PL/I IMPLEMEMTATION OF KIETH PATON'S
    ALGORITHM DESCRIBED IN CACM 12, 9 (SEPTEMBER 1969),
    514-518.                                             */
  DECLARE
    (A(*,*),N,EDGES) BINARY FIXED (15,0),
    B(*) BIT (EDGES),
    BASIC BINARY FIXED (15,0) INITIAL (0),
    T BIT (N) INITIAL ('0'B),
    STACK CONTROLLED BINARY FIXED (15,0),
    (Z,W,J) BINARY FIXED (15,0)
    PREV(N) BINARY FIXED (25,0) INITIAL ((N)0);
/*     A IS AN N BY N VERTEX ADJACENCY MATRIX OF THE GRAPH.
         THE LOWER TRIANGULAR PORTION CONAINTS AN EDGE 
	 TABLE.  IF J>>K AND A(J,K)=M THEN EDGE M JOINS
	 VERTICES J AND K IN THE GRAPH. IF A(J,K)¬=0 AND
	 J>K THEN A(K,J)=1. THE UPPER TRIANGULAR PART OF A
	 IS DESTROYED IN THE PROCESS,  BUT CAN BE EASILY 
	 RECOVERED FROM THE LOWER TRIANGULAR PART. (INPUT)
       N IS THE NUMBER OF VERTICES IN THE GRAPH (INPUT)
   EDGES IS THE NUMBER OF EDGES IN THE GRAPH (INPUT)
       B WILL BE THE SET OF BASIC CYCLES GENERATED.  THE
         K TH BIT OF B(J) IS 1 IF AND ONLY IF THE J TH
	 BASIC CYCLE CONTAINS THE EDGE LABELLED K (OUTPUT)
   BASIC IS USED TO INDED TEH BASIC CYCLES AS THEY ARE
         GENERATED.
       T IS USED TO KEEP TRACK OF THE VERTICES CURRENTLY
         IN THE SPANNING TREE.
   STACK IS A PUSHDOWN LIST USED TO HOLD THE VERTICES OF 
         THE SPANNING TREE WHICH HAVE NOT YET BEEN 
	 EXAMINED.
       Z IS THE VERTEX IF THE SPANNING TREE CURRENTLY BEING
         EXAMINED.
       W IS USED TO FIND EDGES WHICH CONNECT TO Z.
    PREV IS AN ARRAY USED IN THE PRODUCTION OF THE BASIC
         CYCLES.  IF PREV(K)=J THEN (K,J) IS AN EDGE OF THE
	 TREE WITH J NEARER THE ROOT.                    */
/* INITIALIZATION SECTION--NOTE THAT VERTEX 1 IS ALWAYS
   THE ROOT                                              */
  B='0'B;
  SUBSTR(T,1,1)='1'B;
  ALLOCATE STACK;
  STACK=0;
  ALLOCATE STACK;
  STACK=1;
NEW_Z:
  Z=STACK;
  IF Z=0 THEN RETURN;
  ELSE
    DO;
      FREE STACK;
      DO W=2 TO N;
        IF A(MIN(Z,W),MAX(Z,W))=1 THEN
	  DO;
	    IF SUBSTR(T,W,1) THEN
/*  THE EDGE CONNECTING Z AND W CREATES A BASIC CYCLE.   */
              DO;
	        BASIC=BASIC+1;
		SUBSTR(B(BASIC),A(MAX(W,PREV(W)),
		  MIN(W,PREV(W))),1)='1'B;
		SUBSTR(B(BASIC),A(MAX(Z,W),MIN(Z,W)),
		  1)='1'B;
		A(MIN(Z,1),MAX(Z,W))=0;
		J=Z;
		DO WHILE(J¬=PREV(W));
		  SUBSTR(B(BASIC),A(MAX(PREV(J),J),
		    MIN(PREV(J),J)),1)='1'B;
		  J=PREV(J);
		END;
	      END;
	    ELSE
/*  THE EDGE CONNECTING Z AND W SHOULD BE PLACED IN THE 
    TREE                                                 */
              DO;
	        PREV(W)=Z;
		SUBSTR(T,W,1)='1'B;
		ALLOCATE STACK;
		STACK=W;
		A(MIN(Z,W),MAX(Z,W))=0;
	      END;
	  END;
      END;
      GO TO NEW_Z;
    END;
END BASIC_GENERATOR;