Dense - Using Mendz.Graphs..AdjacencyMatrix

Mendz.Graph.AdjacencyMatrix implements an adjacency matrix. So, how do you use it?

In Visual Studio, create a console application that references Mendz.Graphs. In the console application's Program.cs Main(), initialize the graph.

Graph graph = new Graph();
int order = 2500;
for (int i = 1; i <= order; i++)
{
    graph.AddVertex(i, i);
}
Random random = new Random(1)
bool directed = false; // true
int size = 1250;
for (int i = 1; i <= size; i++)
{
    graph.AddEdge(random.Next(1, order), random.Next(1, order), directed);
}
Console.WriteLine(graph.ToString());

This code creates a graph with an order of 2500 vertices and a size of 1250 randomized edges.

The main problem that the adjacency matrix solves is to show if a vertex u is adjacent to another vertex v or not -- by "adjacent" it means that vertex u and vertex v are the endpoints in an edge.

AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix(graph);
adjacencyMatrix.Fill();

This code initializes and fills an adjacency matrix. When the adjacency matrix was filled, it already performed all the iterations through the graph's indexed vertices and indexed edges, while applying the directed/undirected rule on each edge. The element indexes of the indexed vertices are used to address elements/entries in the matrix.

Vertex[] indexedVertices = graph.IndexVertices();
for (i = 0; i < order; i++)
{
    for (j = 0; j < order; j++)
    {
        if (adjacencyMatrix.Matrix[i, j] == 1)
        {
            Console.WriteLine(indexedVertices[i].Value.ToString() + 
                " is adjacent to " + indexedVertices[j].Value.ToString());
        }
    }
}

This code loops through the entire matrix to find the vertices adjacent to each other. If the graph's order is 2500, the total iteration is 2500 * 2500 = 6,250,000. Crazy, right? Using the adjacency matrix this way actually doesn't make sense. The most basic and practical usage really is when you already have two vertices and you want to quickly determine if they are adjacent or not.

Vertex vertex1 = graph.Vertices[250]; // pick any vertex ID between 1 - 2500
Vertex vertex2 = graph.Vertices[230]; // pick any vertex ID between 1 - 2500
int i = Array.BinarySearch(indexedVertices, vertex1);
int j = Array.BinarySearch(indexedVertices, vertex2);
Console.WriteLine(indexedVertices[i].Value.ToString() + 
    " is " + 
    ((adjacencyMatrix.Matrix[i, j] == 1) ? "" : "not") + 
    " adjacent to " + 
    indexedVertices[j].Value.ToString());

Remember, graph theory is a field in discrete mathematics that is concerned in the study of graphs (Wolfram MathWorld; Wikipedia). The keyword is "mathematics". Thus, a graph matrix is really no different than a matrix in mathematics, which is the primary subject in linear algebra's Matrix Theory. Very likely, choosing to use the dense AdjacencyMatrix to represent the graph intends it so for mathematical operations.

Understand 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.