Cyclic Edge Detector

The cyclic edge detector algorithm presented here is based on a depth first search traversal of a graph. While a basic description of depth first search will be discussed in relation to the algorithm, and the algorithm's goals, more detailed descriptions can be found in other literature such as Weiss in [12], or Goodrich and Tamassia in [15].

Depth first search traverses a graph from a starting location $u$ and visits all the adjacent vertices to $u$ , to discover previously undiscovered vertices in the graph. Once a new vertex $v$ is discovered, the algorithm traverses all adjacent vertices to $v$ then returns to explore other edges out of the vertex from which $v$ was discovered. This property of depth first search is useful for discovering directed cycles in a graph as we can be sure that every vertex in the graph is visited, and every edge traversed. To prevent infinite recursion, depth first search colours each vertex in the graph to indicate it's status in the search. WHITE indicates that the vertex has not been visited before, GREY that a vertex has been discovered, and BLACK indicates that a vertex $v$ is finished, that is, all adjacent vertices to $v$ have been discovered, and $v$ possesses no untraversed outgoing edges.

Depth first search can be extended to have the ability to timestamp a vertex as it is discovered, to indicate when that vertex was discovered in the search[22]. This addition to depth first search can be used to detect when a directed cycle is found. When exploring outgoing edges from a vertex $u$ , if we encounter a vertex $v$ that is grey and has an earlier timestamp than $u$ , then a directed cycle has been found.

The depth first search algorithm classifies the edges it traverses during the search into four categories.

1. Tree Edges - these are edges that are traversed by the depth first search algorithm to discover new parts of the graph.
2. Back Edges - are tree edges $(u, v)$ that allow traversal back from $u$ to an ancestor $v$ in the search. It is back edges that create directed cycles.
3. Forward Edges - are non-tree edges $(u, v)$ that connect a vertex $u$ to some descendant $v$ in the resulting depth first tree. A forward edge is an edge from a GREY vertex to a BLACK vertex. This edge indicates a linking of two subtrees constructed during the depth first search.
4. Cross Edges - Are edges that do not fit into the above sets.

Where the cyclic edge detector algorithm presented differs from that of depth first search, is in the goal of the algorithm. The goal of the cyclic edge detection algorithm is to identify the set of all directed edges that are involved in directed cycles. To do this the algorithm uses the notion of cyclic ancestors. The cyclic ancestor is the originator of the cycle comprised of a set of edges. It is always the vertex in the directed cycle with the earliest timestamp. An example is shown in Fig. . When a back edge has been found, the cyclic ancestor of the cycle is the destination vertex of that back edge. Consequently if the destination of a tree edge has a cyclic ancestor, then that tree edge is part of the cycle. Subsequently the source vertex's cyclic ancestor is that of the destination vertex. From this it can be recursively determined that if a vertex has a path through a cyclic ancestor back to itself, then the edges on that path are part of a directed cycle.

Figure: A graph containing a cycle. The edges of the graph are in the solid purple edges. The dashed blue lines indicates the cyclic ancestor for each vertex. The start point of the cyclic edge detection algorithm is vertex U. The back edge is the edge $(V, U)$ , and since U has the earliest timestamp, it is the cyclic ancestor of this example. The cyclic ancestor of V is U and there is a tree edge $(Y, V)$ , so the cyclic ancestor of Y is the cyclic ancestor of V (which is U) which means the edge $(Y, V)$ is involved in the cycle. This is the same for all tree edges recursively.

Figure: Cyclic edge detection algorithm to show which edges are involved in a directed cycle

An edge is defined as a pair of Nodes. $E_{c}$ is the set of all cyclic edges in the graph $G$ $\mathit{Colours} \leftarrow \mathit{\{WHITE, GREY, BLACK\}}$ struct $\mathit{Node}$ int $\mathit{id}$ TimeStamp $\mathit{stamp}$ Node $\mathit{ca}$ list $\mathit{(Node)\;dests}$ Colours $\mathit{status}$ endstruct list $\mathit(Node)\;nodes$ TimeStamp $\mathit{Time}$ $E_{c} \leftarrow \emptyset$ procedure make_adj_list($V$ ,$E$ ) $\mathit{nodes} \leftarrow \textbf{new}\;\mathit{list(Node)}$ foreach $e \in E$ do $\mathit{nodes}[e\mathit{.first}]\mathit{.dests.push(}e\mathit{.second)}$ $\mathit{nodes}[e\mathit{.first}]\mathit{.status = WHITE}$ endfor return procedure get_highest_ca($n$ ) if $n\mathit{.ca} = n$ then return $n$ else return $\mathit{(get\_highest\_ca(}n\mathit{.ca))}$ endif return procedure detect_cycles foreach $k \in \mathit{nodes}$ do $\mathit{Time} \leftarrow 0$ $\mathit{visit(k)}$ endfor return

procedure visit(int $k$ ) $\mathit{nodes}[k]\mathit{.stamp} \leftarrow ++\mathit{Time}$ $\mathit{nodes}[k]\mathit{.status} \leftarrow GREY$ for $n \in \mathit{nodes}[k]\mathit{.dests}$ do if $n \mathit{.status} \neq \mathit{BLACK}$ then if $n\mathit{.status} = \mathit{WHITE}$ then $\mathit{visit}(n)$ $\mathit{cycleOpen} \leftarrow \left\{\begin{array}{l}\mathit{\textbf{if}}\;n \... ...it{.ca.stamp}\\ \mathit{\textbf{otherwise}}\;n\mathit{.stamp}\end{array}\right.$ if $\mathit{cycleOpen} \le \mathit{nodes}[k]\mathit{.stamp}$ then $\mathit{\textbf{if}}\;n\mathit{.ca} = \emptyset\;\mathit{\textbf{then}}\;n\mathit{.ca} \leftarrow n$ $E_{c} \leftarrow E_{c} \cup\;\{(nodes[k]\mathit{.id,}\;n\mathit{.id)}\}$ $\mathit{\textbf{if}}\;\mathit{nodes}[k]\mathit{.ca} = \emptyset\;\mathit{\textbf{then}}\;\mathit{nodes}[k]\mathit{.ca} \leftarrow n\mathit{.ca}$ if $n\mathit{.ca.stamp} < \mathit{nodes}[k]\mathit{.ca.stamp}$ then $\mathit{nodes}[k]\mathit{.ca} \leftarrow n\mathit{.ca}$ endif endif else if $n\mathit{.ca} \ne \emptyset$ then $\mathit{highest\_ca} \leftarrow \mathit{get\_highest\_ca(}n\mathit{.ca)}$ if $\mathit{highest\_ca.stamp} \le n\mathit{.stamp}\;\&$ $\mathit{highest\_ca.status} \ne \mathit{BLACK}$ then $E_{c} \leftarrow E_{c} \cup\;\{(nodes[k]\mathit{.id,}\;n\mathit{.id)}\}$ $\mathit{\textbf{if}}\;\mathit{nodes}[k]\mathit{.ca} = \emptyset\;\mathit{\textbf{then}}\;\mathit{nodes}[k]\mathit{.ca}$ $\leftarrow \mathit{highest\_ca}$ $\mathit{n}\mathit{.ca} \leftarrow \mathit{highest\_ca}$ endif endif endfor $\mathit{nodes}[k]\mathit{.status} \leftarrow \mathit{BLACK}$ return