Finding All Bounded-Length Simple Cycles in a Directed Graph

Finding all simple cycles in a directed graph is a classical computer science problem, for which an elegant algorithm was published by Johnson [10]. An optimal and asymptotically faster algorithm for undirected graphs was proposed by Birmelé et al. [6].

The number of cycles in a complete graph grows exponentially with the number of vertices, $n$. Even sparse graphs, such as planar graphs, can have an exponential number of cycles [8]. A more tractable problem that arises in real applications is that of finding all simple cycles of a given length $k$ or of length bounded by $k$, where $k$ is typically a small integer. This has applications in the analysis of social networks, communications graphs, and financial transaction graphs, etc. Despite its several applications, to the best of our knowledge, no deterministic algorithm for specifically this problem has been proposed to date. The closest problem that has been studied is that of finding $c$ shortest simple cycles by Agarwal and Ramachandran [2, 3]. Their $O(cne)$ algorithm for enumerating the first $c$ cycles in nondecreasing order in a graph with $n$ vertrices and $e$ edges can be easily adapted to find all cycle with at most $k$ edges by stopping as soon as the first cycle of length greater than $k$ is found. Monien [13] gave an $O(ne)$ algorithm for finding and reporting a cycle of length $k$ for any $k\geq 3$, where $n$ is the number of vertices and $e$ is the number of edges in the graph. Alon et al. [4] presented an algorithm that improved this bound to $O(e^{2-2/k})$, reducing the running time for small values of $k$.

In this paper, we present a relatively simple, but fast and powerful new algorithm for finding all simple cycles of length less than or equal to $k$ in sparse directed graphs. We show that for graphs with a nearly uniform vertex degree $d$, our algorithm takes $O((c+n)(k-1)d^{k})$ time, where $c$ is the total number of cycles discovered, $d=e/n$, and $k>1$. While our analysis for the running time addresses only a class of sparse graphs, we provide empirical and experimental evidence of the efficiency of the algorithm for general sparse graphs as well. For the class of graphs analyzed, the running time increases linearly with the size of the graph or the number of cycles discovered because for a given $k$ and a given graph, $kd^{k}$ is a constant, albeit relatively large. The algorithm is not only practical to implement, but also lends itself to easy and scalable parallelization, thus extending its suitability for real applications.

The remainder of the paper is organized as follows. We start with an overview of Johnson’s algorithm [10] for finding all simple cycles in Section 2, since our algorithm uses a similar overall strategy to avoid futile searches. We describe our algorithm in detail in Section 3. Sections 4 and 5 contain correctness proofs and complexity analysis, respectively. Experimental results on large graphs related to real applications are presented in Section 6. Finally, Section 7 contains concluding remarks and directions for future work.

Johnson’s algorithm [10] combines depth-first search (DFS) and backtracking with an astute strategy of blocking and unblocking vertices to prevent fruitless searches and can find all simple cycles in a directed graph in $O((c+1)(n+e))$ time. It remains the best-known algorithm for this problem to date. At the time of its publication, it was a significant improvement over the previous fastest algorithm [15], whose worst-case complexity is $O(e.n(c+1))$.

In each of its steps, Johnson’s algorithm searches for cycles that start and end at a vertex $s$, in the strongly connected component [14] of the subgraph induced by vertices in $\{s,s+1,\ldots,n\}$. Thus, step $s$ outputs all cycles in which $s$ is the vertex with the smallest index (henceforth, referred to as the ”smallest vertex”). Such cycle searches are performed for all values of $s$ from $1$ to $n-1$ for which the strongly connected component has more than $1$ vertex.

As the algorithm proceeds with DFS starting at vertex $s$, it stacks and blocks the vertices encountered along the way. The search would either lead to $s$, in which case a cycle has been discovered, or lead to a blocked vertex. Backtracking from an unsuccessful search unstacks the vertices, but leaves them blocked. It also adds the current vertex to the Blist of the most recently unstacked vertex, thus leaving a backward trail along an unsuccessful path. Blists are data structures used to remember unsuccessful portions of a path that has been explored. The blocked vertices prevent the search from following the same unsuccessful path, or a portion of it, more than once while the vertices responsible for the failure of the path are still on the stack. When backtracking from a successful path, the algorithm unblocks each unstacked vertex, and recursively unblocks the vertices in the Blist of each vertex being unblocked. The rationale is that a vertex $v$ being unstacked was the reason for blocking the vertices in the backward trails emanating from this vertex. As soon as $v$ leaves the stack after a successful search, all the vertices that it was responsible for blocking can be considered for inclusion in a cycle in a subsequent visit via a DFS path that reaches $v$ with a different stack. For a more detailed description and analysis of the algorithm, the reader is referred to the original paper [10].

We now present an efficient algorithm for finding all elementary cycles of length less than or equal to $k$ in a directed graph $G=(V,E)$ where $V\in\{1,2,\ldots,n\}$ and $(u,v)\in E$ iff there is an edge with source $u\in V$ and destination $v\in V$.

The following three lemmas show that function CYCLE_SEARCH in Figure 2 finds every cycle of length less than or equal to $k$ that includes vertex $s$ in $G^{s}$ exactly once.

Lemmas 1–3 prove that CYCLE_SEARCH yields all valid cycles starting and ending at $s$ in $G^{s}$ exactly once. Since CYCLE_SEARCH is called once for all $s\in\{1,2,\ldots,n\}$ in LC_CYCLES, it can be concluded that LC_CYCLES yields exactly one instance of every valid cycle in the original graph $G$.

We first analyze the running time of CYCLE_SEARCH for finding all cycles starting and ending at vertex $s$ in graph $G^{s}$. In CYCLE_SEARCH, the Lock values monotonically decrease until a valid cycle is found. Additionally, a vertex cannot be revisited without decreasing its Lock value. This ensures that no vertex is visited more than $k-1$ times before a valid cycle is detected. After a cycle is found, the Lock values of some vertices are relaxed or increased. During the process of relaxing the Lock values, function RELAX_LOCKS does not traverse an edge unless a Lock value can be increased. In the worst case scenario, this cannot happen to any vertex at most $k-1$ times. Therefore, the time associated with finding a valid cycle cannot exceed $O((k-1)(|V^{s}|+|E^{s}|)$, and the time complexity of CYCLE_SEARCH for finding all valid cycles in a given subgraph $G^{s}$ is $O((c_{s}+1)(k-1)(|V^{s}|+|E^{s}|)$, where $c_{s}$ is the number of valid cycles in which the smallest vertex is $s$.

Recall that $G^{s}$ consists of $s$ and all vertices greater than $s$ that are reachable from $s$ within $k-1$ steps of BFS. If $G$ is a sparse graph with a uniform degree $d$, then $|V^{s}|+|E^{s}|$ is $O(d^{k})$ for all $s$. Therefore, the complexity of the overall algorithm for finding all cycles of length $k$ or less in a graph with a uniform degree $d$ is $O(\sum_{s=1}^{n}(c_{s}+1)(k-1)d^{k})$ = $O((c+n)(k-1)d^{k})$, where $k>1$ and $c=\sum_{s=1}^{n}c_{s}$ is the total number of valid cycles in $G$.

In our analysis, we use $d^{k}$ as the upper bound on the size of any $G^{s}$ in the call to CYCLE_SEARCH. For sufficiently large graphs, the size of $G^{s}$ would not increase with $n$ as long as $d=e/n$ stays constant. $G^{s}$ consists of all vertices with a maximum distance of $k-1$ from $s$, and the size of this feasible neighborhood of $s$ depends only the structure of $G$ (unless $G$ is a scale-free network, which is rare [7]). The simplifying assumption of uniform vertex degrees was made to arrive at a closed-form expression for an upper bound on the size of $G^{s}$. For sufficiently large $n$, the size of $G^{s}$ is likely to be independent of $n$ even without this assumption. As a result, for a given $k$ and a given $d$, the overall time of our algorithm would increase only linearly with the number of valid cycles and the number of vertices in the graph. In Section 6, we experimentally examine the growth of the running time with respect to $k$, and therefore with $c$, which itself is likely to grow with $k$.

It should be noted that explicit construction of $G^{s}$ is neither necessary for the correctness of the algorithm, nor does it have a significant effect on its time complexity. By construction, function CYCLE_SEARCH does not visit any vertex whose minimum distance from $s$ is $k$ or greater. By using $G^{s}$ instead of $H^{s}$, CYCLE_SEARCH avoids testing unnecessary edges at the periphery of the feasible neighborhood of $s$ on Line 9. Additionally, explicitly constructing $G^{s}$ with its own local indices improves the memory access locality of a computer implementation of the algorithm and yields better performance.

We present experimental results on a set of large directed graphs obtained from the SNAP data set [12]. Table 1 contains detailed information about each graph. These graphs include social and communication networks, web graphs, product relationships, and professional networks, etc. They range in average density from roughly 1.6 to 18.8. The standard deviation of the out-degrees shows that with the exception of amazon0505, the graphs are fairly nonuniform. This is not surprising, since it has been observed that many social networks are highly skewed graphs and some even exhibit power-law characteristics [5]. For the results reported in this section, a serial implementation of the algorithm in Figures 1–3 was run on a single 3.3 GHz Intel Xeon E5-2667 core. This section contains results from our implementation only because we were unable to find any other practical algorithms or software to solve this problem for comparison on large graphs.

Table 2 shows the number of cycles detected and the running time of our algorithm for $k$ = 4, 5, and 6. While our algorithm detects all simple cycles of length less than or equal to $k$, we do not count and report cycles of length one (self-edges) and two (bidirectional edges) in this table. The table shows that the algorithm successfully detected up to hundreds of billions of cycles on large graphs using a single CPU, with only one run (web-BerkStan graph for $k=6$) that did not complete in several days and had to be aborted. By default, we sort and renumber the vertices of the graph in increasing order of total degree, as discussed in Section 3.4. For $k$ = 5, we also show the running time with this sorting turned off to show the benefit of sorting. The time is worse without sorting for every graph in our test set. In most cases, sorting results in an improvement by a relatively small factor; however, for one graph (wiki-topcats), the difference is so significant that the algorithm may not be practical without sorting.

In Section 5, we derived $O((c+n)(k-1)d^{k})$ as the expression for the time complexity of our algorithm for graphs with a uniform out-degree $d$. We tested the graphs in our test suite from the SNAP data set against this expression for growth of running time with $k$ and $c$. Table 3 shows the ratio $\frac{T}{(c+n)(k-1)\mbox{min}(e,d^{k})}$ for $k=4,5,6$ for these graphs. We used min$(e,d^{k})$ in the denominator because $d^{k}$ is meant to represent the maximum number of edges in each $G^{s}$ in the CYCLE_SEARCH algorithm (Figure 2) for a given $k$ and in practice, it cannot exceed the total number of edges $e$ in the original graph. Table 3 shows that this ratio decreases as $k$ (and therefore, $c$) increase for all the graphs in our test set. Even though our graphs are quite diverse in origin and density, and the distribution of edges over the vertices is highly nonuniform, they all share this trend. The analytically derived running time bound used a simplifying assumption that the vertices had a uniform degree $d$. Experimentally observing that despite non-uniform degrees, the growth in the running time with $k$ and $c$ for every test case is slower than that suggested by the analytical bound is therefore an important finding and reinforces the practicality of our algorithm.

While enumerating simple cycles in directed graphs is a classical computer science problem, in most real applications on very large graphs, only a small fraction of the potentially enormous number of cycles are of interest. There has been relatively little research on discovering interesting cycles and algorithms for these are typically expensive [1], unless the search space can be substantially narrowed based on the definition of interesting cycles, for example, cycles with obligatory vertices or edges [11]. One class of cycle enumeration and detection problems of practical interest involves finding cycles of a limited length. We devised an efficient and practical algorithm for finding all length-constrained simple cycles in a directed graph.

We analytically and experimentally demonstrated the efficiency of the algorithm and showed that a serial implementation could detect billions of cycles on large graphs with millions on edges in a reasonable amount of time. In the future, it would be interesting to study the results of a parallel implementation on even larger graphs. On the analysis side, it would be interesting to explore the derivation of tighter time bounds without simplifying assumptions about the structure of the graphs.