Dense - Seidel And Laplacian Adjacency Matrix

Given Mendz.Graphs..Dense.AdjacencyMatrixBase, it's not that difficult to create other types of adjacency matrices. Let's look at two of them: the Seidel adjacency matrix and Laplacian matrix.

SeidelAdjacencyMatrix

The Seidel adjacency matrix is defined as a (-1, 1, 0)-adjacency matrix. With the AdjacencyMatrixBase, you can easily define a SeidelAdjacencyMatrix class the same way:

SeidelAdjacencyMatrix.cs
namespace Mendz.Graphs.Representations.Matrices.Dense
{
    public class SeidelAdjacencyMatrix : AdjacencyMatrixBase<int>
    {
        public SeidelAdjacencyMatrix(Graph graph) 
            : base(graph, (z, edge) => edge.Tail.ID == edge.Head.ID ? 0 : -1, 1)
        {

        }


        protected override void SetEntries(int[,] matrix, 
            int x, int y, int value, bool directed)
        {
            if (x == y)
            {
                throw new InvalidOperationException("Loops are not supported.");
            }
            if (directed)
            {
                throw new InvalidOperationException("Directed edges are not supported.");
            }
            matrix[x, y] = value;
            matrix[y, x] = value;
        }
    }
}

Note that the validity of the SeidelAdjacencyMatrix is best with a simple graph, thus the validation to make sure that the graph is simple.

LaplacianMatix

Another matrix for simple graphs is the Laplacian matrix. Officially, it is L = D - A, where D is a degree matrix and A is an adjacency matrix. Programmatically, this can translate to creating a degree matrix, creating an adjacency matrix and then performing an operation on them to create the Laplacian matrix. With the AdjacencyMatrixBase, you can easily create a LaplacianMatrix class directly with just a graph instance.

LaplacianMatrix.cs
using System;

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

        }

        protected override void SetEntries(int[,] matrix, 
            int x, int y, int value, bool directed)
        {
            if (x == y)
            {
                throw new InvalidOperationException("Loops are not supported.");
            }
            if (directed)
            {
                throw new InvalidOperationException("Directed edges are not supported.");
            }
            matrix[x, x] += 1;
            matrix[y, y] += 1;
            matrix[x, y] = value;
            matrix[y, x] = value;
        }
    }
}

In Mendz.Graphs, a Laplacian matrix is a (-1, 0, d)-adjacency matrix, where d is the degree of the vertex that the diagonal points to in graph.IndexVertices(). Unlike in the other adjacency matrices that we have done so far, where the diagonal is a fixed value, the Laplacian matrix's diagonal is a calculation. In order to achieve this, the SetEntries() method must be overridden.

Note that SetEntries() override makes sure that the edges being worked on are not loops and are undirected (in effect making sure that the LaplacianMatrix is really working on a simple graph). If the parameters pass the checks, the vertex degrees are calculated and the entries assigned with the Adjacent value.

The Seidel adjacency matrix and Laplacian matrix are commonly used in mathematical operations. Remember 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!

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

Update: Renamed LaplacianAdjacencyMatrix to LaplacianMatrix.