Generate an Adjacency Matrix for a Weighted Graph

Question

I am trying to implement Floyd-Warshall Algorithm. To do this it requires me to set up an adjacency matrix of a weighted graph. How would I go about doing this? I know the values and have attached a picture of the weighted graph. I have tried to look for some online examples of this, but I cannot seem to find anything. I understand Floyd-Warshall algorithm I just need help getting it set up so I am able to implement it. Here is one that I have built before, but I didn't have to use specific values.

Code:

public static void buildAdjMatrix()
{

    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            if (directionAllowed(i, j) == true)
            {
                adjMatrix[i, j] = 1;
            }
            else
            {
                adjMatrix[i, j] = 50;
            }
        }
    }

}

Here is the specific Graph at hand:

Here is a picture of the matrix I need to create.. Sorry for the horrible quality...

Solution

So, you seem not to be familiarized with Graphs, take a look at Wikipedia. Also browse for some images, it gets easier to understand.

Bit of concept

Your picture can be represented as a Graph. Generally graphs are implemented using 2 basic kinds of elements, Nodes and Links (sometimes called Arcs).

A Node represent the letters in your picture, they would be A, B, C, etc. An Arc or Link, is the line that connect two nodes, if you look the connection between H to L, the have a link between the two, in a weighted graph, different links have different weights.

Solving your problem - Part 1

What we have to do is represent your picture as a graph in the code, so let's start creating the basic elements Node and Arc:

Node

A node has a Name, so we can identify the node. And a node can be connected to other nodes, we could use a collection of Nodes, but yours is a weighted graph, so, each of the connections has to be represented by the linked node and it's weight. Therefore, we use a collection of Arcs.

public class Node
{
    public string Name;
    public List<Arc> Arcs = new List<Arc>();

    public Node(string name)
    {
        Name = name;
    }

    /// <summary>
    /// Create a new arc, connecting this Node to the Nod passed in the parameter
    /// Also, it creates the inversed node in the passed node
    /// </summary>
    public Node AddArc(Node child, int w)
    {
        Arcs.Add(new Arc
        {
            Parent = this,
            Child = child,
            Weigth = w
        });

        if (!child.Arcs.Exists(a => a.Parent == child && a.Child == this))
        {
            child.AddArc(this, w);
        }

        return this;
    }
}

Arc

Really simple class, it contains the linked nodes, and the weight of the connection:

public class Arc
{
    public int Weigth;
    public Node Parent;
    public Node Child;
}

Graph

Graph is a kind of wrapper class, for organization purposes. I also have declared a Root for the graph, we're not using it, but is useful in several cases:

public class Graph
{
    public Node Root;
    public List<Node> AllNodes = new List<Node>();

    public Node CreateRoot(string name)
    {
        Root = CreateNode(name);
        return Root;
    }

    public Node CreateNode(string name)
    {
        var n = new Node(name);
        AllNodes.Add(n);
        return n;
    }

    public int?[,] CreateAdjMatrix()
    {
        // Matrix will be created here...
    }
}

Solving your problem - Part 2

Now we have all the data structure for holding the graph, let's fill it with some data. Here's some code that initializes a graph similar to your cube picture. It's boring and dull, but in real life cases, the graph will be created dynamically:

static void Main(string[] args)
{
    var graph = new Graph();

    var a = graph.CreateRoot("A");
    var b = graph.CreateNode("B");
    var c = graph.CreateNode("C");
    var d = graph.CreateNode("D");
    var e = graph.CreateNode("E");
    var f = graph.CreateNode("F");
    var g = graph.CreateNode("G");
    var h = graph.CreateNode("H");
    var i = graph.CreateNode("I");
    var j = graph.CreateNode("J");
    var k = graph.CreateNode("K");
    var l = graph.CreateNode("L");
    var m = graph.CreateNode("M");
    var n = graph.CreateNode("N");
    var o = graph.CreateNode("O");
    var p = graph.CreateNode("P");

    a.AddArc(b, 1)
     .AddArc(c, 1);

    b.AddArc(e, 1)
     .AddArc(d, 3);

    c.AddArc(f, 1)
     .AddArc(d, 3);

    c.AddArc(f, 1)
     .AddArc(d, 3);

    d.AddArc(h, 8);

    e.AddArc(g, 1)
     .AddArc(h, 3);

    f.AddArc(h, 3)
     .AddArc(i, 1);

    g.AddArc(j, 3)
     .AddArc(l, 1);

    h.AddArc(j, 8)
     .AddArc(k, 8)
     .AddArc(m, 3);

    i.AddArc(k, 3)
     .AddArc(n, 1);

    j.AddArc(o, 3);

    k.AddArc(p, 3);

    l.AddArc(o, 1);

    m.AddArc(o, 1)
     .AddArc(p, 1);

    n.AddArc(p, 1);

    // o - Already added

    // p - Already added

    int?[,] adj = graph.CreateAdjMatrix(); // We're going to implement that down below

    PrintMatrix(ref adj, graph.AllNodes.Count); // We're going to implement that down below
}

Solving your problem - Part 3

So, we have a completelly initialized graph, let's create the matrix. The next method creates a matrix of two dimensions, n by n, where n is the number of node we get from the graph class. Foreach of the nodes, we search if they have a link, if they have a link, a filled the matrix in the appropriate position. Look that in your adjacency matrix example, you only have 1s, here I put the weight of the link, I've put this way, so there's no sense in having a weighted graph!

public int?[,] CreateAdjMatrix()
{
    int?[,] adj = new int?[AllNodes.Count, AllNodes.Count];

    for (int i = 0; i < AllNodes.Count; i++)
    {
        Node n1 = AllNodes[i];

        for (int j = 0; j < AllNodes.Count; j++)
        {
            Node n2 = AllNodes[j];

            var arc = n1.Arcs.FirstOrDefault(a => a.Child == n2);

            if (arc != null)
            {
                adj[i, j] = arc.Weigth;
            }
        }
    }
    return adj;
}

Done

That's done, you have your weighted adjacency matrix, some way to print it:

private static void PrintMatrix(ref int?[,] matrix, int Count)
{
    Console.Write("       ");
    for (int i = 0; i < Count; i++)
    {
        Console.Write("{0}  ", (char)('A' + i));
    }

    Console.WriteLine();

    for (int i = 0; i < Count; i++)
    {
        Console.Write("{0} | [ ", (char)('A' + i));

        for (int j = 0; j < Count; j++)
        {
            if (i == j)
            {
                Console.Write(" &,");
            }
            else if (matrix[i, j] == null)
            {
                Console.Write(" .,");
            }
            else
            {
                Console.Write(" {0},", matrix[i, j]);
            }

        }
        Console.Write(" ]\r\n");
    }
    Console.Write("\r\n");
}

What give us the following output:

       A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
A | [  &, 1, 1, ., ., ., ., ., ., ., ., ., ., ., ., ., ]
B | [  1, &, ., 3, 1, ., ., ., ., ., ., ., ., ., ., ., ]
C | [  1, ., &, 3, ., 1, ., ., ., ., ., ., ., ., ., ., ]
D | [  ., 3, 3, &, ., ., ., 8, ., ., ., ., ., ., ., ., ]
E | [  ., 1, ., ., &, ., 1, 3, ., ., ., ., ., ., ., ., ]
F | [  ., ., 1, ., ., &, ., 3, 1, ., ., ., ., ., ., ., ]
G | [  ., ., ., ., 1, ., &, ., ., 3, ., 1, ., ., ., ., ]
H | [  ., ., ., 8, 3, 3, ., &, ., 8, 8, ., 3, ., ., ., ]
I | [  ., ., ., ., ., 1, ., ., &, ., 3, ., ., 1, ., ., ]
J | [  ., ., ., ., ., ., 3, 8, ., &, ., ., ., ., 3, ., ]
K | [  ., ., ., ., ., ., ., 8, 3, ., &, ., ., ., ., 3, ]
L | [  ., ., ., ., ., ., 1, ., ., ., ., &, ., ., 1, ., ]
M | [  ., ., ., ., ., ., ., 3, ., ., ., ., &, ., 1, 1, ]
N | [  ., ., ., ., ., ., ., ., 1, ., ., ., ., &, ., 1, ]
O | [  ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ., ]
P | [  ., ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ]

Comments

[JLott]

Wow! This explanation is incredible! Thank you so much for you help. This really helped me understand what to do and I am sure others will find it helpful as well.

[JLott]

I did have one problem.. On your CreateAdjMatrix, it says that there is unreachable code in the for loop with the counter 'i'

[RMalke]

Mmmm, in the for line specifically? Mine is working here. PS: The CreateAdjMatrix method should be inside the Graph class

[JLott]

Yeah that is where I have it... odd... Where are you putting the structure of the graph? Like where you are adding the new graph.

[JLott]

Awesome. I just had my parenthesis out of order... of course lol. Thanks again!

[user1312242]

Wow!! RMalke, you are so strong in Data Structure!! +1 for your detailed explanation.

[Celsiuss]

I thought that the idea of an adjacency matrix whas that the graph is also represented in that way in memory. This code does not store the graph as an adjacency matrix

[RMalke]

@Celsiuss it does. It's implemented on Part 3, on the method CreateAdjMatrix