About one year ago, my student Qiyuan Hu noticed a strange thing when trying to triangulate the graph of a Qualitative Constraint Network (QCN). In particular, when we apply the triangulation algorithm to a complete graph, it will complain list index out of range
. A simple example can be found in test_triangulation.ipynb. (Please ignore constraints there which are specific for QCN.) The algorithm used is from (Tarjan 1984)^{1}, which consists of two subalgorithms: Maximum Cardinality Search
(MCS
) and Fillin Computation
(FIC
). We checked the details in that paper, and found that the algorithm was implemented correctly and the error is a bug of MCS
. This bug applies to general simple graphs, and is not restricted to the field of Qualitative Spatial Reasoning. I did some simple search and found several implementations of the algorithm, e.g., igraph. However, to the best of my knowledge, I didn’t see any previous discussion on this bug (of course I could be wrong).
def MCS(ConMatrix, neighbors):
a = [None for i in range(len(ConMatrix))]
a_ = [None for i in range(len(ConMatrix))]
Set = [None for i in range(len(ConMatrix))]
Size = [None for i in range(len(ConMatrix))]
for i in range(len(ConMatrix)):
Set[i] = set([])
Size[i] = 0
Set[0].add(i)
j = 0
for i in range(len(ConMatrix)):
v = Set[j].pop()
a[v] = i
a_[i] = v
# # uncomment codes below to fix the bug
# if j==(len(ConMatrix)1):
# break
Size[v] = 1
for u in neighbors[v]:
if Size[u] >= 0:
Set[Size[u]].remove(u)
Size[u] = Size[u] + 1
Set[Size[u]].add(u)
j = j + 1
while j >= 0 and not Set[j]:
j = j  1
return a, a_
So we started to explore the cause of this error. From the error message, we can see that the error is due to trying to access an element in the list by a given index, but the given index is larger than the length of the index minus one (out of range).
The relevant list in our implementation is used to store Set[k]
, which consists of all unnumbered vertices adjacent to exactly $k$ numbered vertices. The range of $k$ is from $0$ to $n1$.
A simple example will be able to illustrate how the error occurs and how we should fix it. Let us consider a complete graph of 3 vertices $v_0,v_1,v_2$. The algorithm MCS
will number the vertices from $0$ to $2$. Initially, all 3 vertices are unnumbered and each of them is adjacent to $0$ numbered vertices, i.e., Set[0]={0, 1, 2}
. A vertex from Set[0]
will be selected and numbered, say $v_0$ is selected and numbered as $0$, then Set[0]={1, 2}
. The neighbors of $v_0$ will be moved from Set[0]
to Set[1]
and now Set[0]={ }
and Set[1]={1,2}
. Then the index $j$ of the set to consider is increased by 1. If the corresponding set is empty, then it means no unnumbered vertex is adjacent to $j$ numbered vertices, so $j$ is decreased until a value s.t. there exists an unnumbered vertex that is adjacent to $j$ numbered vertices. In the case here, $j$ is increased from $0$ to $1$, and Set[1]
is nonempty, so the next loop will have $j$ being $1$.
In the next loop, a vertex in Set[1]
is selected and numbered, say $v_1$. Before increasing $j$ by 1, Set[0]={ }
, Set[1]={ }
, and Set[2]={2}
. Then $j$ becomes $2$ and the next loop will have $j$ being $2$. The vertex $v_2$ in Set[2]
is selected and every Set[k]
($k=0,1,2$) becomes empty. Then $j$ is increased by $1$ and becomes $3$, but there is no Set[3]
, so an error of list index out of range
will be raised.
It can be seen from the above example that, when $j=n1$, we are about to number vertices adjacent to $n1$ numbered vertices. Note that there can only be one such vertex that is adjacent to $n1$ numbered vertices, that is, the last unnumbered vertex. So when $j=n1$, there is no need to do anything but to number the last unnumbered vertex.
Therefore, a simple fix is to add a check right after numbering a vertex, to see if $j$ is $n1$, and if so then we just stop the numbering process. A fixed implementation can be found in triangulation.py.

Robert E. Tarjan, Mihalis Yannakakis. Simple LinearTime Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing, 1984, 13(3): 566–579. ↩