# 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  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;
``````