Dense - Incidence Matrix

An incidence matrix shows the relationship between a vertex and an edge. An incidence matrix C is a (1, 0)-matrix, where C_v,e is 1 if v and e are linked, otherwise 0. There are variations though when the graph is directed or undirected, and when the incidence matrix is oriented or not (Wikipedia; Wolfram).

The incidence matrix is not necessarily a square matrix. An incidence matrix has the order v x e, where v is the number of vertices (Graph.Order) and e is the number of edges (Graph.Size).

IncidenceMatrix.cs
using Mendz.Library;
using System;

namespace Mendz.Graphs.Representations.Matrices.Dense
{
    public class IncidenceMatrix : DenseGraphMatrixBase<int>
    {
        public bool Oriented { get; set; }

        public IncidenceMatrix(Graph graph)
            : base(graph, (graph.Order, graph.Size))
        {

        }

        public override void Initialize()
        {
            Matrix = Matrix<int>.Create(Size.rows, Size.columns);
        }

        public override int[,] 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),
                    z, edge.Directed, Oriented);
            }
            return Matrix;
        }

        private void SetEntries(int[,] matrix, 
            int x, int y, int z, bool directed, bool oriented)
        {
            if (x == y)
            {
                matrix[x, z] = (directed ? 0 : (oriented ? 0 : 2));
            }
            else
            {
                matrix[x, z] = (directed ? -1 : (oriented ? -1 : 1));
                matrix[y, z] = 1;
            }
        }
    }
}

The incidence matrix is the most confusing matrix to code. Mostly, this is because of the Boolean property Oriented, which indicates if the incidence matrix is oriented or not. When combined with the checks for directed and undirected edges, the complexity can be a headache.

Honestly, it took me a while to put together SetEntries() the way it is now. I had to refactor this many times. Note, however, that I also found many confusing materials describing how the incidence matrix should be valued. Mendz.Graphs chose to use the vertices as rows and edges as columns. That's the easy part. The difficult part is when an entry can become -2/-1/0/1/2 as mentioned in some texts. I mostly used Wikipedia as my reference. If anyone finds a flaw in the implementation above, please do not hesitate to let me know.

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.