A bug in the algorithm for triangulating a graph by (Tarjan 1984)

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)¹, which consists of two sub-algorithms: Maximum Cardinality Search (MCS) and Fill-in 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 $n-1$.

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 non-empty, 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=n-1$, we are about to number vertices adjacent to $n-1$ numbered vertices. Note that there can only be one such vertex that is adjacent to $n-1$ numbered vertices, that is, the last unnumbered vertex. So when $j=n-1$, 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 $n-1$, and if so then we just stop the numbering process. A fixed implementation can be found in triangulation.py.