TIP: Half Size Triangular Matrix

CodeGuru content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.

Often, when dealing with graphs or other data types, you need to store a large distance matrix. By its nature, this matrix is
symmetric, which means that cells in the upper right are the same as the cells in the lower left. For example, cell (1,2) is equal to cell (2,1). For large matrices, this redundancy can waste a lot of space—especially when double precision is required.

The technique described here allows you to use a 1D array to store only half of the matrix. A simple function outputs the 1D index when given the row, column, and size of the 2D matrix.

This function came about when I noticed that the first key number on each row was noticed to be row*N-TriangleNumber. Where row is the row number (starting with 0), N is the size of the matrix (elements per side), and TriangleNumber is an integer sequence defined by N(N+1)/2. See: http:www.research.att.com/%7Enjas/sequences/A000217 for more info on that.

For example, when N=4, the key numbers are 0, 4, 7, and 9. Create this matrix like so:

  0 1 2 3
0 0 1 2 3
1   4 5 6
2     7 8
3       9

From this equation, row*N-N(N+1)/2, it is easy to get the rest of the indices.

Here is the Trag_eq() function that gives you the index into the 1D array. Note that the size of the 1D array is (N*N-N)/2+N.

int Trag_eq(int row, int col, int N)
{
   if (row <= col)
      return row*N - (row-1)*((row-1) + 1)/2 + col - row;
   else if (col<row)
      return col*N - (col-1)*((col-1) + 1)/2 + row - col;
}

Then, to set or read cells, it is simply array[Trag_eq(r,c,N)].

There is a slightly less useful variant to this, but it can save you more space in some situations. When you are not dealing with diagonal entries, (row = column), you can use this function instead:

int Trag_noeq(int row, int col, int N)
{
   //assert(row != col);    //You can add this in if you like
   if (row<col)
      return row*(N-1) - (row-1)*((row-1) + 1)/2 + col - row - 1;
   else if (col<row)
      return col*(N-1) - (col-1)*((col-1) + 1)/2 + row - col - 1;
   else
      return -1;
}

The usage is the same, except the size of the 1D array is now (N*N-N)/2—a savings of N. And now, you have to be more careful about indexing so you don’t access element -1 of the 1D array.

You can also do the *reverse* of the previously mentioned formulas. Where the index into the 1D triangular matrix is given, and the row and column of the corresponding 2D square matrix is output. It turns out that this is a bit more difficult. The reason is that the key numbers for a certain sized matrix are a function of the row. So you have to iterate until you find the right row for the specified index.

Here are the reverse functions. Similar to above there are two functions, one for with and one for without diagonal entries. The order of this operation is O(N). Where N is the length of one side of the 2D square matrix. But since the loop breaks after it finds the right row, the average case is O(N/2).

void Trag_reverse_eq(int index, int N, int& row, int& col)
{
   row = 0;
   int keyafter;
   do
   {
       row++;
       keyafter = row * N - (row - 1) * row / 2;
   } while (index >= keyafter);
   row--;
   col = N - keyafter + index;
}

void Trag_reverse_noeq(int index, int N, int& row, int& col)
{
    row = 0;
    int keyafter;
    do
    {
        row++;
        keyafter = row * (N-1) - (row - 1) * row / 2;
    } while (index >= keyafter);
    row--;
    col = N - keyafter + index;
}

Here is an example of how to use these functions. If you have a triangular matrix like this:

0 1 2 3
  4 5 6
    7 8
      9

Which is stored in a 1D array like this:

 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

This is how to call the function to get the row and column of cell number 5:

int row;
int col;
Trag_reverse_eq(5, 4, row, col);
// row is now 1
// col is now 2