Ravishing Journey

Cycle and its detection in graphs

on September 20, 2013

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cyclecircuitcircle, or polygon; see Cycle graph. A cycle in a directed graph is called a directed cycle.

The term cycle may also refer to:

• An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycleintegral cycle, etc.
• An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.

Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.

Cycle detection :

• Undirected Graphs :

An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). Equivalently, all the back edges, which DFS skips over, are part of cycles. In the case of undirected graphs, only O(n) time is required, since at most n – 1 edges can be tree edges (where n is the number of vertices).

• Directed Graphs :

Basically this post has been written to explain the simple and straight forward way to detect cycle in a directed graph. The method explained below is the simple and correct way to do it.

directed graph has a cycle if and only if a DFS finds a back edge. Forward and cross edges do not necessarily indicate cycles. Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

An easy way to do this is to attempt a topological-order traversal using the algorithm given in Section . This algorithm only visits all the vertices of a directed graph if that graph contains no cycles.

To see why this is so, consider the directed cyclic graph shown in Figure . The topological traversal algorithm begins by computing the in-degrees of the vertices. (The number shown below each vertex in Figure is the in-degree of that vertex). Figure: A directed cyclic graph.

At each step of the traversal, a vertex with in-degree of zero is visited. After a vertex is visited, the vertex and all the edges emanating from that vertex are removed from the graph. Notice that if we remove vertex a and edge (a,b) from , all the remaining vertices have in-degrees of one. The presence of the cycle prevents the topological-order traversal from completing.

Therefore, the a simple way to test whether a directed graph is cyclic is to attempt a topological traversal of its vertices. If all the vertices are not visited, the graph must be cyclic.

Below program  gives the implementation of the isCyclic method of the AbstractGraph class. This boolean-valued accessor returns true if the graph is cyclic. The implementation simply makes uses a visitor that counts the number of vertices visited during a topologicalOrderTraversal of the graph. Program: AbstractGraph class isCyclic method.

The worst-case running time of the isCyclic method is determined by the time taken by the topologicalOrderTraversal. Since , the running time of isCyclic is when adjacency matrices are used to represent the graph and when adjacency lists are used.

Applications :

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.

1. Khuram Ali says: