Sparse - Degree Matrix and Variations

Come to think of it, the degree matrix and its variations are really sparse. Implementing the degree matrix as a sparse matrix just makes absolute sense!

Degree matrices basically set only the main diagonal of a square matrix, making degree matrices naturally sparse by design. The Mendz.Graphs.Representations.Matrices.Sparse namespace just has to have them implemented.

DegreeMatrix

The DegreeMatrix class follows the same pattern used by the AdjacencyMatrixBase class, that is has a protected parameterized Fill() method and a private static SetEntries() method.

DegreeMatrix.cs
using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public class DegreeMatrix : SparseGraphMatrixBase<int>
    {
        public DegreeMatrix(Graph graph)
            : base(graph, (graph.Order, graph.Order))
        {

        }

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

        protected ConcurrentDictionary<(int row, int column), int> 
            Fill(Action<ConcurrentDictionary<(int row, int column), int>, int, int, 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),
                        edge.Directed);
                });
            return Matrix;
        }

        private static void SetEntries(
            ConcurrentDictionary<(int row, int column), int> matrix, 
            int x, int y, bool directed)
        {
            matrix.AddOrUpdate((x, x), 1, (k, v) => v + 1);
            matrix.AddOrUpdate((y, y), 1, (k, v) => v + 1);
        }
    }
}

Observe that filling the matrix is a parallel loop on the Graph.IndexEdges().

InDegreeMatrix

The InDegreeMatrix derives from the DegreeMatrix. As you can see, the Fill() method is overridden to make sure it calls InDegreeMatrix's private static SetEntries() method.

InDegreeMatrix.cs
using System;
using System.Collections.Concurrent;

namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public class InDegreeMatrix : DegreeMatrix
    {
        public InDegreeMatrix(Graph graph)
            : base(graph)
        {

        }

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

        private static void SetEntries(
            ConcurrentDictionary<(int row, int column), int> matrix, 
            int x, int y, bool directed)
        {
            if (!directed)
            {
                throw new InvalidOperationException("Undirected edges are not supported.");
            }
            matrix.AddOrUpdate((y, y), 1, (k, v) => v + 1);
        }
    }
}

InDegreeMatrix and OutDegreeMatrix have validations to make sure that they are used only with directed graphs.

OutDegreeMatrix

The OutDegreeMatrix derives from the DegreeMatrix. As you can see, the Fill() method is overridden to make sure it calls OutDegreeMatrix's private static SetEntries() method.

OutDegreeMatrix.cs
using System;
using System.Collections.Concurrent;

namespace Mendz.Graphs.Representations.Matrices.Sparse
{
    public class OutDegreeMatrix : DegreeMatrix
    {
        public OutDegreeMatrix(Graph graph)
            : base(graph)
        {

        }

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

        private static void SetEntries(
            ConcurrentDictionary<(int row, int column), int> matrix, 
            int x, int y, bool directed)
        {
            if (!directed)
            {
                throw new InvalidOperationException("Undirected edges are not supported.");
            }
            matrix.AddOrUpdate((x, x), 1, (k, v) => v + 1);
        }
    }
}

Quick and easy, right?