The Matrix

What is the matrix? No, this article is not about the movie. This article actually kicks off a new series on graph theory, graphs and their representations. So far, I've covered representing graphs as an adjacency list. Now, it's time to represent graphs as matrices.

The simplest definition I can find of the matrix is in Wikipedia:

In mathematics, a matrix (plural matrices) is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns.

If you've been programming for quite a while, this easily translates to a two-dimensional array. It's really that simple. But in the context of graph theory, it's actually a little more than that.

A matrix can be dense or sparse. Basically, it's like saying whether there are many stuffs in it or if there are few stuffs in it. To say that a matrix is "dense" or "sparse" is actually a subjective declaration of an observed state. Note that there is no strict guidance that quantifies whether a matrix can be considered dense or sparse. There is no universally defined threshold of sparsity.

While a matrix being dense or sparse is conceptual in mathematics, in programming, however, dense matrix and sparse matrix are actually physical data structures. There are many ways to define them. There are many types to choose from. Mendz.Graphs chooses the following paths.

Dense Matrix

Mendz.Graphs.Representations.Matrices provides DenseGraphMatrixBase.

DenseGraphMatrixBase.cs
namespace Mendz.Graphs.Representations.Matrices
{
    public abstract class DenseGraphMatrixBase<T> : GraphMatrixBase<T[,]>
    {
        public T this[int row, int column]
        {
            get
            {
                return Matrix[row, column];
            }
        }

        protected DenseGraphMatrixBase(Graph graph, (int rows, int columns) size) 
            : base(graph, size)
        {

        }
    }
}

This code defines an abstract class DenseGraphMatrixBase, the base class for defining dense matrices. It inherits GraphMatrixBase to set the dense matrix as a two-dimensional array of type T (T[,]). DenseGraphMatrixBase also exposes an indexer for accessing items in the Matrix. In Mendz.Graphs, derived classes are in the Mendz.Graphs.Representations.Matrices.Dense namespace.

Sparse Matrix

The problem with a dense matrix, it's big. If you have 2500 vertices for example, creating a 2500x2500 matrix translates to 6,250,000 elements. If most of the elements would not be set, a sparse matrix can absolutely help save memory. This is achieved by creating a list instead. In some contexts, a sparse matrix is also referred to as a sparse array.

Mendz.Graphs.Representations.Matrices provides SparseGraphMatrixBase.

SparseGraphMatrixBase.cs
using System;
using System.Collections.Concurrent;

namespace Mendz.Graphs.Representations.Matrices
{
    public abstract class SparseGraphMatrixBase<T> 
        : GraphMatrixBase<ConcurrentDictionary<(int row, int column), T>>
    {
        public virtual T this[int row, int column]
        {
            get
            {
                Matrix<T>.CheckCoordinates(Size, row, column);
                if (Matrix.ContainsKey((row, column)))
                {
                    return Matrix[(row, column)];
                }
                else
                {
                    return default(T);
                }
            }
        }

        protected SparseGraphMatrixBase(Graph graph, (int rows, int columns) size)
            : base(graph, size)
        {
            
        }

        public override void Initialize()
        {
            Matrix = new ConcurrentDictionary<(int row, int column), T>();
        }
    }
}

This code defines an abstract class SparseGraphMatrixBase, the base class for defining sparse matrices. It inherits GraphMatrixBase setting the sparse matrix as a (int rows, int columns) tuple keyed dictionary of type T. SparseGraphMatrixBase also exposes an indexer for accessing items in the Matrix. Note that it validates the indexes passed against the virtual "shape and size" of the matrix. This feature is important because there is really no physical matrix with full rows and columns in SparseGraphMatrixBase. The indexer instead simulates the behavior like as if it's getting entries from a two-dimensional array. In Mendz.Graphs, derived classes are in the Mendz.Graphs.Representations.Matrices.Sparse namespace.

Now, let's get organized. In the Mendz.Graphs project, under the Representations\Matrices folder, I created sub-folders for Dense and Sparse. The Dense sub-folder will contain dense matrix implementations. The Sparse sub-folder will contain the sparse matrix implementations. At this point, this is how Mendz.Graphs looks like.



Understand that Mendz.Graphs is not a intended to be a Math library. Mendz.Graphs is all about graph data and representing them. Thus, the focus of Mendz.Graphs.Representations.Matrices is how that "rectangular array" mentioned in the matrix definition can be created, initialized and filled with graph data. The matrices that you create using Mendz.Graphs can be passed to Math libraries that support operations with matrices. There are many .Net compatible Math/numerical libraries available like Math.NET, ALGLIB and MATLAB. See also this list from Wikipedia. A quick search works to find them, too!

Updated SparseGraphMatrixBase's indexer to use the Mendz.Library.Matrix.CheckCoordinates() method.