Representing Graphs

Mendz.Graphs implements the graph theory's definition of the graph. The Graph class provides features to maintain the Vertices, Edges and their respective indexes. It can also be used to generate the graph's DOT notation. So does the Graph class represent a graph? Well, yes and... not exactly.

In graph theory, a graph G = (V, E):

• Where V is a collection of vertices;
• Where E is a collection of edges; and
• Where an edge is made up of a pair of (u, v) vertices in V.

At its very core, the Graph class is really just a data model. Although the Graph class is usable on its own, algorithms may require graph data to be shaped or represented in order to fit in to the algorithm's needs. Various graph representations solve different problems in the same way that different algorithms solve different problems.

Graph representation does not change the graph's data. Rather, graph representation reorganizes and (pre-)processes graph data in order to make them more readily consumable by an algorithm. A graph representation needs a graph to exist. The graph representation can then initialize its own data model and fill it accordingly with the graph's data. This line of thought is the basis of GraphRepresentationBase, the base class of graph representations in Mendz.Graphs.Representations.

GraphRepresentationBase.cs
using System.Collections;

namespace Mendz.Graphs.Representations
{
    public abstract class GraphRepresentationBase<T>
        where T : IEnumerable
    {
        public Graph Graph { get; private set; }

        protected GraphRepresentationBase(Graph graph)
        {
            Graph = graph;
        }

        public abstract void Initialize();

        public abstract T Fill();
    }
}

This code defines an abstract class named GraphRepresentationBase. Its constructor requires that a graph instance is passed, which is then stored and exposed via property named Graph. When inherited by a class, the abstract Initialize() and Fill() methods must be implemented. T is the IEnumerable type that will be used to store the representation.

There are two primary ways to represent graphs: as a list and as a matrix. I used GraphRepresentationBase to define mnemonic versions for list and matrix.

GraphListBase.cs
using System.Collections;

namespace Mendz.Graphs.Representations
{
    public interface IGraphList<T>
    {
        T List { get; }
    }

    public abstract class GraphListBase<L> 
        : GraphRepresentationBase<L>, IGraphList<L>
        where L : IEnumerable
    {
        public L List { get; protected set;  }

        L IGraphList<L>.List
        {
            get
            {
                return List;
            }
        }

        protected GraphListBase(Graph graph)
            : base(graph)
        {

        }
    }
}

For GraphListBase, it exposes a List property, an implementation of the IGraphList interface. Note that List is also explicitly implemented.

GraphMatrixBase.cs
using System.Collections;

namespace Mendz.Graphs.Representations
{
    public interface IGraphMatrix<T>
    {
        T Matrix { get; }

        (int rows, int columns) Size { get; }
    }

    public abstract class GraphMatrixBase<M> 
        : GraphRepresentationBase<M>, IGraphMatrix<M>
        where M : IEnumerable
    {
        public M Matrix { get; protected set; }

        M IGraphMatrix<M>.Matrix {
            get
            {
                return Matrix;
            }
        }

        public (int rows, int columns) Size { get; protected set; }

        (int rows, int columns) IGraphMatrix<M>.Size
        {
            get
            {
                return Size;
            }
        }

        protected GraphMatrixBase(Graph graph, (int rows, int columns) size)
            : base(graph)
        {
            Size = size;
        }
    }
}

For the GraphMatrixBase, it exposes the Matrix and Size properties, implementations of the IGraphMatrix interface. Note that Matrix and Size are also explicity implemented.

In effect, the GraphListBase and GraphMatrixBase are just mnemonic implementations of the GraphRepresentationBase. I did this to allow for expressiveness. Essentially, they are the same. However, the interface they implement communicates the difference.