NETWORK Procedure

Cycle Enumeration

A path in a graph is a sequence of links such that the to node of each link is the from node of the next link. An elementary cycle is a path in which the starting node and the ending node are the same and no node appears more than twice in the sequence.

In PROC NETWORK, you can find (or just count) the elementary cycles of an input graph by specifying the CYCLE statement. The options for this statement are described in the section CYCLE Statement. To find the cycles and report them in an output data table, use either the OUTCYCLESNODES= option or the OUTCYCLESLINKS= option. To simply count the cycles, omit the output data table options. You can also use the SOURCE= option in the CYCLE statement to specify a source node. This results in enumerating only the cycles that contain the specified source node.

For undirected graphs, each link represents two directed links. For this reason, the following cycles are filtered out: trivial cycles () and duplicate cycles that are found by traversing a cycle in both directions ( and ).

By default, PROC NETWORK uses depth-first search to quickly identify whether a cycle exists. This algorithm runs in time . This algorithm should scale to very large graphs. If filters are used or if the specified maximum number of cycles (MAXCYCLES=) is greater than 1, then enumerative algorithms are used.

The default algorithm that PROC NETWORK uses to enumerate cycles when the value of the MAXLENGTH= option is greater than 20 (ALGORITHM=BACKTRACK) is a variant of the algorithm in Johnson (1975). This algorithm runs in time , where c is the number of elementary cycles in the graph. So the algorithm should scale to large graphs that contain few cycles. However, some graphs can have a very large number of cycles, so the algorithm might not scale. The default when the value of the MAXLENGTH= option is less than or equal to 20 (ALGORITHM=BUILD) is described in Liu and Wang (2006). This algorithm is usually much faster than the backtracking algorithm when the length of the cycles is sufficiently restricted.

If MAXCYCLES=ALL and there are many cycles, the output data tables can become very large. It might be beneficial to check the number of cycles before you try to create an output data table. For more information about these options, see the section CYCLE Statement.

Output Data Tables

Depending on the specified options, the cycle algorithm produces additional output data tables as described in the following section.

OUTCYCLESNODES= Data Table

The OUTCYCLESNODES= data table describes the enumerated cycles as a sequence of nodes. This data table contains the following columns:

cycle: the cycle identifier
order: the order (sequence) of the node in the cycle
node: the node label

OUTCYCLESLINKS= Data Table

The OUTCYCLESLINKS= data table describes the enumerated cycles as a sequence of links. This data table contains the following columns:

cycle: the cycle identifier
order: the order (sequence) of the link in the cycle
from: the from node label
to: the to node label

The cycle identifiers are numbered sequentially, starting from the value of the INDEXOFFSET= option in the PROC NETWORK statement.

Cycle Enumeration of a Directed Graph

This section provides a simple example of using the cycle enumeration algorithm on the directed graph G shown in Figure 95. For a more detailed example involving both cycle enumeration and transitive closure, see Transitive Closure for Identification of Circular Dependencies in a Bug Tracking System.

Figure 95: Directed Graph G

The directed graph G can be represented by the following links data table, mylib.LinkSetIn:

data mylib.LinkSetIn;
   input from $ to $ @@;
   datalines;
A B  A E  B C  C A  C D
D E  D F  E B  E C  F E
;

The following statements count the number of cycles in the graph (without storing them):

proc network
   direction    = directed
   links        = mylib.LinkSetIn;
   cycle
      maxCycles = all;
run;
%put &_NETWORK_;

The result is written to the log of the NETWORK procedure, as shown in Figure 96.

Figure 96: PROC NETWORK Log: Count the Number of Cycles in a Directed Graph

NOTE: ------------------------------------------------------------------------------------------

NOTE: Running NETWORK.

NOTE: ------------------------------------------------------------------------------------------

NOTE: The number of nodes in the input graph is 6.

NOTE: The number of links in the input graph is 10.

NOTE: Processing cycle enumeration using 1 threads across 1 machines.

NOTE: The algorithm found 7 cycles.

NOTE: Processing cycle enumeration used 0.00 (cpu: 0.00) seconds.

NOTE: The Cloud Analytic Services server processed the request in 0.214243 seconds.

STATUS=OK PROBLEM_TYPE=CYCLE SOLUTION_STATUS=OK NUM_CYCLES=7 CPU_TIME=0.60 REAL_TIME=0.21

The following statements return the first cycle that is found in the graph:

proc network
   direction         = directed
   links             = mylib.LinkSetIn;
   cycle
      outCyclesNodes = mylib.CyclesNodes
      outCyclesLinks = mylib.CyclesLinks;
run;

The output data table mylib.CyclesNodes now contains the nodes of the first cycle that is found in the input graph, as shown in Figure 97.

Figure 97: Nodes of the First Cycle Found in a Directed Graph

cycle	order	node
1	1	A
1	2	B
1	3	C
1	4	A

The output data table mylib.CyclesLinks now contains the links of the first cycle that is found in the input graph, as shown in Figure 98.

Figure 98: Links of the First Cycle Found in a Directed Graph

cycle	order	from	to
1	1	A	B
1	2	B	C
1	3	C	A

The first cycle that is found in the input graph is shown graphically in Figure 99.

Figure 99:

The following statements return all the cycles in the graph:

proc network
   direction         = directed
   links             = mylib.LinkSetIn;
   cycle
      maxCycles      = all
      outCyclesNodes = mylib.CyclesNodes;
run;

The output data table mylib.CyclesNodes now contains the nodes of all the cycles in the input graph, as shown in Figure 100.

Figure 100: Nodes of All Cycles in a Directed Graph

cycle	order	node
1	1	A
1	2	B
1	3	C
1	4	A
2	1	A
2	2	E
2	3	B
2	4	C
2	5	A
3	1	A
3	2	E
3	3	C
3	4	A
4	1	B
4	2	C
4	3	D
4	4	E
4	5	B
5	1	B
5	2	C
5	3	D
5	4	F
5	5	E
5	6	B
6	1	C
6	2	D
6	3	E
6	4	C
7	1	C
7	2	D
7	3	F
7	4	E
7	5	C

The six additional cycles are shown graphically in Figure 101 through Figure 103.

Figure 101: Cycles

Figure 102: Cycles

Figure 103: Cycles

The following statements return all the cycles in the graph, with the additional specification that node F be a source node:

proc network
   direction         = directed
   links             = mylib.LinkSetIn;
   cycle
      maxCycles      = all
      source         = F
      outCyclesNodes = mylib.CyclesNodes;
run;

The output data table mylib.CyclesNodes now contains the nodes of all the cycles in the input graph that include node F, as shown in Figure 104.

Figure 104: Nodes of All Cycles with Source Node F in a Directed Graph

cycle	order	node
1	1	F
1	2	E
1	3	B
1	4	C
1	5	D
1	6	F
2	1	F
2	2	E
2	3	C
2	4	D
2	5	F

The two resulting cycles are shown graphically in Figure 105.

Figure 105: Cycles Containing Node F

Last updated: August 07, 2026

cycle	order	node
1	1	A
1	2	B
1	3	C
1	4	A
2	1	A
2	2	E
2	3	B
2	4	C
2	5	A
3	1	A
3	2	E
3	3	C
3	4	A
4	1	B
4	2	C
4	3	D
4	4	E
4	5	B
5	1	B
5	2	C
5	3	D
5	4	F
5	5	E
5	6	B
6	1	C
6	2	D
6	3	E
6	4	C
7	1	C
7	2	D
7	3	F
7	4	E
7	5	C

cycle	order	node
1	1	A
1	2	B
1	3	C
1	4	A
2	1	A
2	2	E
2	3	B
2	4	C
2	5	A
3	1	A
3	2	E
3	3	C
3	4	A
4	1	B
4	2	C
4	3	D
4	4	E
4	5	B
5	1	B
5	2	C
5	3	D
5	4	F
5	5	E
5	6	B
6	1	C
6	2	D
6	3	E
6	4	C
7	1	C
7	2	D
7	3	F
7	4	E
7	5	C

cycle	order	node
1	1	A
1	2	B
1	3	C
1	4	A
2	1	A
2	2	E
2	3	B
2	4	C
2	5	A
3	1	A
3	2	E
3	3	C
3	4	A
4	1	B
4	2	C
4	3	D
4	4	E
4	5	B
5	1	B
5	2	C
5	3	D
5	4	F
5	5	E
5	6	B
6	1	C
6	2	D
6	3	E
6	4	C
7	1	C
7	2	D
7	3	F
7	4	E
7	5	C