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...
Adjacency matrix representationTo store weighted graph using adjacency matrix form, we call the matrix as cost matrix. Here each cell at position M[i, j] is holding the weight from edge i to j. If the edge is not present, then it will be infinity. For same node, it will be 0.
An adjacency matrix is easily implemented as an array. Both directed and undirected graphs may be weighted. A weight is attached to each edge.
To fill the adjacency matrix, we look at the name of the vertex in row and column. If those vertices are connected by an edge or more, we count number of edges and put this number as matrix element. The matrix to represent a graph in this way is called Adjacency matrix .
Due to this, each node (i,j) is represented by the position (i-1,j-1) in the adjacency matrix. To create an adjacency matrix for a weighted graph, we will first create an n x n 2-dimensional list having 0s. After that, we will assign the weight of edge eij at the position (i,j) in the matrix.
So, you seem not to be familiarized with Graphs, take a look at Wikipedia. Also browse for some images, it gets easier to understand.
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.
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...
}
}
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
}
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 1
s, 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;
}
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, ., &, ]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With