Adjacency Matrix

Download:	http://solutionzip.com/downloads/adjacency-matrix/
Ex 1: Adjacency Matrix
Although adjacency lists are simple, an adjacency matrix representation is easier for representing graphs with weighted edges.
We will implement an adjacency matrix representation for weighted graphs, and then use this representation for running some weighted graph algorithms.
1
Make a new project in Eclipse, called WeightedGraph.
2
To save time, we won’t implement a Node ADT. Instead, add a class Node and give it the following structure:
import java.util.List;
public class Node {
// The value in the node itself
public Object value;
// The distance from this node to every other node
public List edges;
public Node(Object value);
}
Fill in the constructor for the Node class to just set value to the one passed in, and initialise edges to an empty ArrayList.
3
Add the following WeightedGraph ADT to your project:
import java.util.List;
public interface WeightedGraph {
public int size();
public boolean isEmpty();
public List getNodes();
public void addNode(Node n);
public void removeNode(Node n);
public void addEdge(Node source, Node destination, int weight);
}
4
Create a class WeightedDirectedGraph that implements WeightedGraph.
Now let’s go through and implement each of the methods:
a
Member variables
In an adjacency matrix representation, each nodes stores its neighbours as a list of integers (with each integer representing the weight of the edge between those two nodes).
For example, in a graph containing 3 nodes A, B and C, the matrix of neighbours might look like:
(
0 3 0
0 0 1
0 0 0
)
These weights correspond to the following edges:
(
A?A A?B A?C
B?A B?B B?C
C?A C?B C?C
)
This means that this graph only has two edges:
A?B, with a weight of 3
B?C, with a weight of 1
To represent this in Java, we can store each row in this matrix in a Node object, but we still need a list somewhere (of all the nodes) to use as a reference. This list (which is (A,B,C) in the example above) will be used to determine which index of the matrix each node corresponds to (which, in the example above, is 0 for A, 1 for B and 2 for C).
So we just need a list of nodes in our WeightedDirectedGraph object:
private List nodes;
The order of nodes in this list is important, so we have to be careful to update the neighbours for each node whenever we make changes to this list.
b
Constructor
Make the constructor take no arguments, and just set the nodes list to a new ArrayList.
c
size() and isEmpty()
Just call the corresponding size() and isEmpty() on the list of nodes.
d
getNodes()
Just return the list of nodes.
e
addNode()
For the addNode method, we need to do 3 things:
Add an edge with weight 0 (i.e. no edge) from the node we’re about to add to every other node (including itself)
Add an edge with weight 0 from every other node to this new node
Add this node to the list of nodes
Let’s go through each of these methods one-at-a-time.
Firstly, we can add an edge from this node to every other node with weight 0:
for (Node m : nodes) {
n.edges.add(0);
}
We then also need to add an edge from this node to itself:
n.edges.add(0);
Now we need to do the reverse – add an edge from every other node back to this node:
for (Node m : nodes) {
m.edges.add(0);
}
Finally, with all the edges added, we can add this new node to our list of nodes:
nodes.add(n);
Note
Sometimes, when Eclipse warns you that the value of a local variable is not used, its a hint that your method could use some refactoring. In this case, you can improve it to only use a single for-loop (instead of two for-loops).
See if you can refactor your addNode() method to use only a single for-loop.
f
removeNode()
Removing a node is similar to adding one, except slightly simpler.
To remove a node, we need to:
Remove the index entry corresponding to that node from every other node’s list of edges
Remove the node itself from our list of nodes
First, we should find the index of the node we want to remove:
int index = this.nodes.indexOf(n);
Now we can remove that index from every other node (which corresponds to removing the edge that links those two nodes together):
for (Node node : nodes) {
node.edges.remove(index);
}
Lastly, we can remove the node itself:
this.nodes.remove(index);
Now the node has been removed from the graph, and all other nodes contain correct lists of edge weights to all other nodes.
g
addEdge()
Similarly to removeNode(), we need to first find the index of the node we want to the edge to point towards (the destination of the edge).
Then, once we have this index, set the value in source.edges at that index to weight.
Hint
You can use List.set() to set the value of an item at a particular index in a list.
For example, in this case, you could use:
source.edges.set(i, 2);
to set the value at index i to 2.
Great! You should now have a working graph with an adjacency matrix representation.
5
To test our WeightedDirectedGraph, we can use very similar tests to those we used when we wrote our Graph class using an adjacency-list representation. However, we will need to slightly modify them to use weights as well (since our new WeightedGraph implementation supports edges of differing weights).
a
testConstruction()
Add a test that ensures that, for a newly constructed WeightedDirectedGraph:
The size() method returns 0
The isEmpty() method returns true
The getNodes() method returns an empty list
b
testSize()
Create a graph of 3 nodes, ensuring size() returns the correct value at each step, and then slowly remove nodes and ensure size() remains correct at every stage.
c
testIsEmpty()
The same as testSize(), but ensure the results of isEmpty() are correct.
d
testAddNode()
Create a graph of 3 nodes, and ensure that getNodes() returns the correct values (in the correct order – the order that they were added).
e
testRemoveNode()
Create a graph of 3 nodes, remove the second one, and ensure that getNodes() returns the correct nodes.
Then try and remove the other 2 nodes, and check that getNodes() returns an empty list.
f
testSmallGraph()
Create the example weighted graph from the Weighted Graphs section by constructing each node and adding edges between them like so:
WeightedGraph g = new WeightedDirectedGraph();
Node A = new Node(“A”);
Node B = new Node(“B”);
Node C = new Node(“C”);
Node D = new Node(“D”);
Node E = new Node(“E”);
g.addNode(A);
g.addNode(B);
g.addNode(C);
g.addNode(D);
g.addNode(E);
g.addEdge(A, B, 2);
g.addEdge(A, C, 5);
g.addEdge(B, D, 3);
g.addEdge(C, D, 6);
g.addEdge(D, E, 9);
Then look at the edges member variable on each node and ensure they are correct.
For example, to test the edges member variable for node A, you could use:
assertEquals(Arrays.asList(0, 2, 5, 0, 0), A.edges);
Note
You may find it helpful to work out the adjacency matrix on pen-and-paper before writing the test for each node.
Great job! You should now have a fully working directed graph implementation using an adjacency matrix.
You can now use WeightedDirectedGraph objects to represent weighted graphs, which will help you complete the following exercises.

Download:	http://solutionzip.com/downloads/adjacency-matrix/