Understanding Tiernan's Algorithm

Question

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.

Answer 1

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.

Answer 2

This is not standard terminology. Rather, as the text says, $H$ contains the list of vertices closed to each vertex. So a vertex $u$ is closed to a vertex $v$ iff $H[v]$ contains $u$ (for the exact form of the condition, consult the algorithm). I suggest you continue reading the article and try to understand the algorithm. You can then come up with what being closed means semantically in the context of the algorithm.