[Solved]: Understanding Tiernan’s Algorithm

Problem Detail: I am currently working through Tiernan’s paper, “An efficient search algorithm to find the elementary circuits of a graph” (published 1970), and I am stuck on point 3 of the following excerpt:

The algorithm is named EC for “elementary circuit.” The function blocks of EC are denoted EC1, EC2, etc. EC requires that there be assigned to the vertices, in any order, the integer designators 1, 2, .-., N. The algorithm utilizes two principal arrays in addition to that describing the graph. The first is a one-dimensional array, P, containing the vertices of an elementary path. The second is a two-dimensional array, H, and is initially zeroed. Elementary path building in P is the basic process of EC. The first path is started as vertex 1. A path is extended from its end, one arc at a time, with three conditions checked before a tentative extension is performed:

  1. The extension vertex cannot be in P.
  2. The extension vertex value must be larger than that of the first vertex of P.
  3. The extension vertex cannot be closed to the last vertex in P. H contains the list of vertices closed to each vertex.

What does Tiernan mean by point 3? I’ve tried googling the term “closed to [some vertex]”, but the results were not entirely helpful.

Asked By : janvdl

Answered By : janvdl

I think I have managed to figure it out from the paper, and would like to leave my explanation for the next person who struggles with this concept. From my understanding, Tiernan means nothing of a mathematical nature when he says “$u$ is closed to $v$”. He’s actually trying to say “$u$ is closed off to $v$”, i.e. no longer accessible. By following along with Tiernan’s paper and his example, his algorithm manages to discover a cycle with the following vertices:

$v_1, v_2, v_4, v_3, v_5$

Now that he has discovered a cycle, he removes the last vertex $v_5$ to see whether another vertex, say $v_x$, can be added to the remaining nodes, e.g. $v_1,v_2,v_4,v_3,v_x$, in the hopes of finding another cycle. However, to avoid rediscovering the same cycle (such that $v_x ne v_5$), the vertex $v_5$ is now closed to $v_3$ and $v_3$ cannot extend an arc to it again. In the matrix $H$, we now have $H[3,1] = v_5$ (or simply $5$ since Tiernan requires unique integer labels for each vertex). If $v_3$ would become closed to another vertex before $v_3$ was removed from $P$ (to backtrace and attempt to discover cycles using $v_1, v_2, v_4, v_x$), then that vertex would be placed in $H[3,2]$. In a nutshell, “closed to” should actually be “closed off to/inaccesible” due to the fact that the node was already used as the last node in either a cycle, or a “non-cyclic dead end”. This prevents the algorithm from rediscovering the same cycles over and over.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25977

Leave a Reply