Sparse - Adjacency Matrix

In Mendz.Graphs, representing graphs as matrices follow similar coding patterns. This is basically because they all derive from the GraphMatrixBase class. Thus, it shouldn't be surprising to see that the codes for sparse matrices look a lot like their dense matrix counterparts.

Let's start by defining Mendz.Graphs..Sparse.AdjacencyMatrixBase.

AdjacencyMatrixBase.cs
using Mendz.Library;
using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public abstract class AdjacencyMatrixBase<T> : SparseGraphMatrixBase<T>
    {
        protected Func<int, Edge, T> Adjacent { get; set; }

        protected T NonAdjacent { get; set; }

        protected T Diagonal { get; set; }

        public override T this[int row, int column]
        {
            get
            {
                Matrix<T>.CheckCoordinates(Size, row, column);
                if (Matrix.ContainsKey((row, column)))
                {
                    return Matrix[(row, column)];
                }
                else
                {
                    return (row == column) ? Diagonal : NonAdjacent;
                }
            }
        }

        protected AdjacencyMatrixBase(Graph graph, 
            Func<int, Edge, T> adjacent, 
            T nonadjacent = default(T), 
            T diagonal = default(T))
            : base(graph, (graph.Order, graph.Order))
        {
            Adjacent = adjacent;
            NonAdjacent = nonadjacent;
            Diagonal = diagonal;
        }

        public override ConcurrentDictionary<(int row, int column), T> Fill()
        {
            return Fill((matrix, x, y, value, directed) => 
                SetEntries(matrix, x, y, value, directed));
        }

        protected ConcurrentDictionary<(int row, int column), T> 
            Fill(Action<ConcurrentDictionary<(int row, int column), T>, int, int, T, bool> 
                setEntries)
        {
            Initialize();
            var indexedVertices = Graph.IndexVertices();
            var indexedEdges = Graph.IndexEdges();
            Parallel.For(0, indexedEdges.Length, (z) =>
            {
                Edge edge = indexedEdges[z];
                setEntries(Matrix,
                    Array.BinarySearch<Vertex>(indexedVertices, edge.Tail),
                    Array.BinarySearch<Vertex>(indexedVertices, edge.Head),
                    Adjacent(z, edge), edge.Directed);
            });
            return Matrix;
        }

        private static void SetEntries(
            ConcurrentDictionary<(int row, int column), T> matrix, 
            int x, int y, T value, bool directed)
        {
            matrix.TryAdd((x, y), value);
            if (x != y)
            {
                if (!directed)
                {
                    matrix.TryAdd((y, x), value);
                }
            }
        }
    }
}

If this looks familiar, that's because it looks a lot like the code for Mendz.Graphs..Dense.AdjacencyMatrixBase! However, there are key differences that I want to point out. Observe the ff.:

• The abstract Fill() method is implemented to call a protected and parameterized Fill() method that performs the actual looping.
• The protected parameterized Fill() method is designed to accept an action that points to a private static SetEntries() method. The reason for this is to allow derived classes to route calls to their own implementation or version of a private static SetEntries() method.
• The SetEntries() method is private static for a reason. It actually goes hand in hand with the decision why SparseGraphMatrixBase uses the ConcurrentDictionary data type. In order to be ready for large graphs, with a higher probability of improving performance and throughput, filling the sparse matrix is a parallel operation. Combined with acting on a ConcurrentDictionary, making SetEntries() private static makes it easily thread-safe.

AdjacencyMatrix

The (1, 0, 0)-adjacency matrix can now be easily defined as follows:

AdjacencyMatrix.cs
namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public class AdjacencyMatrix : AdjacencyMatrixBase<int>
    {
        public AdjacencyMatrix(Graph graph)
            : base(graph, (z, edge) => 1)
        {

        }
    }
}

Looks familiar? ;-)

WeightedAdjacencyMatrix

The weighted adjacency matrix is, likewise, easy:

WeightedAdjacencyMatrix.cs
namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public class WeightedAdjacencyMatrix : AdjacencyMatrixBase<double>
    {
        public WeightedAdjacencyMatrix(Graph graph)
            : base(graph, (z, edge) => edge.Weight)
        {

        }
    }
}

Reminds you of something? ;-)