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:
- The extension vertex cannot be in P.
- The extension vertex value must be larger than that of the first vertex of P.
- 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
$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