I’ve been looking at graph data structures recently. I needed to generate very large (1,000,000 nodes) randomly connected, unweighted, undirected graphs. The main problem was the graph representation. One design I came up with, which works pretty well, is to store graph adjacency information in a lower triangular bit matrix, where the bit matrix is really an adjacency list of bit arrays. In the image below, in the upper left hand corner I have a graph with five nodes. In the lower left is a bit matrix representation, which works very well in most situations. The 0s and 1s are not integers, they are bits and each row is a .NET BitArray array to save space. But notice that when space is at a premium, because an undirected graph is symmetric we can store just the lower left part of the bit matrix as shown in the right side of the image below. We don’t need to explicitly store the entries on main diagonal which we’ll assume are all 0s if a node cannot be connected to itself.

Testing the implementation is not trivial and there are a lot of boundary conditions to check.

Here is an implementation of a LowerTriangularBitMatrix in C# which can be used to create a space-efficient graph.

private class LowerTriangularBitMatrix

{

private BitArray[] data; // in System.Collections

public readonly int Dim;

public LowerTriangularBitMatrix(int n)

{

this.data = new BitArray[n – 1];

// we will not store the main diagonal so the first row

// has no cols and so is not needed

for (int i = 0; i < data.Length; ++i)

{

data[i] = new BitArray(i + 1); // see picture

}

this.Dim = n;

}

public void SetValue(int row, int col, bool value)

{

// assumes row != col

if (row > col)

data[row – 1][col] = value; // normal

else

data[col – 1][row] = value; // the symmetric part

}

public bool GetValue(int row, int col)

{

if (row == col) return false; // main diagonal values

if (row > col)

return data[row – 1][col];

else

return data[col – 1][row];

}

public override string ToString()

{

string s = “”;

s += “x” + Environment.NewLine; // first row diagonal value

for (int i = 0; i < data.Length; ++i)

{

for (int j = 0; j < data[i].Length; ++j)

{

if (data[i][j] == true) s += “1 “; else s += “0 “;

}

s += “x “; // trailing implied diagonal value

s += Environment.NewLine;

}

return s;

}

} // class LowerTriangularBitMatrix

Although the LowerTriangularBitMatrix class is intended to be a private store for a graph data structure, if you make the scope public, example calls could be:

LowerTriangularBitMatrix m = new LowerTriangularBitMatrix(5);

m.SetValue(0, 1, true); // row 0, col 1

m.SetValue(3, 0, true); // row 3, col 0

. . .

bool v = m.GetValue(0,3); // value at row 0 col 3 (indexes [2][0])

. . .

Console.WriteLine(m.ToString());

This implementation is efficient in terms of space and to determine if two nodes are adjacent to each other or not. It’s not so efficient if you need to determine a set of all nodes which are adjacent to a given node.