Dense - Adjacency Matrix

In graph theory, the adjacency matrix is defined as a square matrix used to represent a finite graph, where the elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph (Wikipedia).

The basic definition over-simplifies. There are actually many variations of the adjacency matrix. Fortunately, there is a pattern to them. The pattern can be summed up as (a, b, c)-adjacency matrix such that A_i,j = a if i and j are adjacent, b if not, and c on the diagonal. The (a, b, c)-adjacency matrix pattern inspired the creation of the AdjacencyMatrixBase.

AdjacencyMatrixBase.cs
using Mendz.Library;
using System;

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

        protected T NonAdjacent { get; set; }
        
        protected T Diagonal { get; set; }

        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 void Initialize()
        {
            Matrix = SquareMatrix<T>.Create(Size.rows, NonAdjacent, Diagonal);
        }

        public override T[,] Fill()
        {
            Initialize();
            var indexedVertices = Graph.IndexVertices();
            var indexedEdges = Graph.IndexEdges();
            for (int z = 0; z < 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;
        }

        protected virtual void SetEntries(T[,] matrix, 
            int x, int y, T value, bool directed)
        {
            matrix[x, y] = value;
            if (x != y)
            {
                if (!directed)
                {
                    matrix[y, x] = value;
                }
            }
        }
    }
}

The AdjacencyMatrixBase extends the DenseGraphMatrixBase. AdjacencyMatrixBase adds the "(a, b, c)" properties Adjacent, NonAdjacent and Diagonal respectively. The Adjacent property is a function that can accept an edge's index in Graph.IndexEdges(), and an edge instance as input. The NonAdjacent and Diagonal properties can be any value of type T. Initialize() is implemented to create a square matrix in the graph's order with the entries initialized to the given NonAdjacent and Diagonal initial values. Fill() loops on the graph's edges to SetEntries() in the matrix using the Adjacent function.

AdjacencyMatrix

With the AdjacencyMatrixBase in place, creating an AdjacencyMatrix is a breeze.

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

        }
    }
}

This code defines an AdjacencyMatrix class wherein the entries for adjacent values are set to 1, and the rest set to 0's. The AdjacencyMatrix implements the default definition of an adjacency matrix.

WeightedAdjacencyMatrix

While the AdjacencyMatrix is concerned only with indicating if vertices are neighbors or not, the WeightedAdjacencyMatrix goes beyond that by providing instead a piece of information from the edge itself, specifically the Edge.Weight property.

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

        }
    }
}

This code implements the weighted adjacency matrix, where the adjacent entries are set to the edge's weight. Note that the weighted adjacency matrix is of type double.

Mendz.Graphs intentionally does not include algorithms. I encourage developers to build their own algorithm library or libraries based on Mendz.Graphs.