A Space Efficient Graph Data Structure Implementation in C#

In my last post I described how to store graph structure adjacency information in a way that is very efficient in terms of space. The idea is to store adjacency information in a lower triangular matrix where the 0s and 1s representing not-adjacent and are-adjacent are stored in a bit array. To realize a graph structure we need an additional layer of abstraction which allows us to write code like this:

string graphFile = “data.txt”;
MyGraph g = new MyGraph(graphFile, “SIMPLE”);
bool a = g.AreAdjacent(0, 5); // returns false for data below
int n = g.NumberNeighbors(0); // returns 3 for data below

In other words we want to be able to load data from an external file which is in some particular format, and we need information such as whether or not two nodes are adjacent to each other, and how many neighbors (the degree) a node has.

Suppose a “simple” data file looks like:

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

The first line means node 0 is connected to nodes 1, 3, and 4. This is just a made-up format and there are many real formats used in research. The constructor helper iterates through the file and stores adjacency information into the lower triangular matrix.

Here is some code that does this:

public class MyGraph // graph which uses a lower triangular matrix
{
private LowerTriangularBitMatrix data; // program defined helper class.
private int numberNodes;
private int numberEdges;
private int[] numberNeighbors; // for NumberNeighbors method

public MyGraph(string graphFile, string fileFormat) // ctor
{
if (fileFormat.ToUpper() == “DIMACS”)
LoadDimacsFormatGraph(graphFile);
else if (fileFormat.ToUpper() == “SIMPLE”)
LoadSimpleFormatGraph(graphFile);
else
throw new Exception(“Format ” + fileFormat + ” not supported”);
}

private void LoadSimpleFormatGraph(string graphFile)
{
FileStream ifs = new FileStream(graphFile, FileMode.Open);
StreamReader sr = new StreamReader(ifs);
string line = “”;
string[] tokens = null;
string[] subTokens = null;

// count number of lines == number of nodes
int numNodes = 0;
int numEdges = 0;
while ((sr.ReadLine() != null))
{
++numNodes;
}
sr.Close(); ifs.Close();

this.data = new LowerTriangularBitMatrix(numNodes);

// second pass, parse and store
int fromNode = -1;
int toNode = -1;
ifs = new FileStream(graphFile, FileMode.Open); // reopen file
sr = new StreamReader(ifs);
while ((line = sr.ReadLine()) != null)
{
line = line.Trim();
tokens = line.Split(‘:’); // separate from-node and to-nodes
tokens[0] = tokens[0].Trim();
tokens[1] = tokens[1].Trim();
fromNode = int.Parse(tokens[0]);
subTokens = tokens[1].Split(‘ ‘); // get the to-nodes
for (int i = 0; i < subTokens.Length; ++i)
{
toNode = int.Parse(subTokens[i]);
if (fromNode < toNode)
{
// because storage is a lower tiangular matrix
this.data.SetValue(fromNode, toNode, true);
++numEdges;
}
}
}
sr.Close(); ifs.Close();

// third pass, get number-adjacent
// iterate through the LowerTriangularBitMatrix data
// by using GetData, which works on a virtual n x n matrix
// we can avoid dealing with the physical representation

this.numberNeighbors = new int[numNodes];
for (int row = 0; row < numNodes; ++row)
{
int count = 0;
for (int col = 0; col < numNodes; ++col)
{
if (data.GetValue(row, col) == true)
++count;
}
numberNeighbors[row] = count;
}

this.numberNodes = numNodes;
this.numberEdges = numEdges;
return;
} // LoadSimpleFormatGraph

private void LoadDimacsFormatGraph(string graphFile)
{
// DIMACS is a ‘real’ format . . .
}

public int NumberNodes
{
get { return this.numberNodes; }
}

public int NumberEdges
{
get { return this.numberEdges; }
}

public int NumberNeighbors(int node)
{
return this.numberNeighbors[node];
}

public bool AreAdjacent(int nodeA, int nodeB)
{
// GetData takes care of row < col or row > col
if (this.data.GetValue(nodeA, nodeB) == true)
return true;
else
return false;
}

public override string ToString()
{
string s = “”;
for (int i = 0; i < this.data.Dim; ++i)
{
s += i + “: “;
for (int j = 0; j < this.data.Dim; ++j)
{
if (this.data.GetValue(i, j) == true)
s += j + ” “;
}
s += Environment.NewLine;
}
return s;
}

// ———————————————————–
private class LowerTriangularBitMatrix // storage helper
{
// see last blog post
}
// ————————————————————

} // MyGraph

Advertisements
This entry was posted in Software Test Automation. Bookmark the permalink.