An edge list for this graph could be:
TASK: Read a list of edges describing a graph, create a corresponding adjacency matrix.
COMMENT: We have seen how a graph can be represented as a picture (dots and lines) or as an adjacency matrix. Another way to represent a graph is to provide a list of edges, that is, pairs of nodes that are connected. In this exercise, you will write a program that reads a list of edges and creates an adjacency matrix "A".
For example, consider the following graph:
An edge list for this graph could be:
(1,2), (1,3), (2,3), (2,4), (2,5), (2,6), (3,4), (5,6)
but we could list the edges in any order we want:
(2,5), (2,6), (3,4), (5,6), (1,2), (1,3), (2,3), (2,4)
or
(4,3), (6,5), (1,2), (2,5), (2,6), (1,3), (3,2), (4,2)
and we could list both versions of each edge:
(1,2), (1,3), (2,3), (2,4), (2,5), (2,6), (3,4), (5,6),
(2,1), (3,1), (3,2), (4,2), (5,2), (6,2), (4,3), (6,5)
However, all of these edge lists should result in the same adjacency matrix A, which is 6x6, symmetric, contains only 0's and 1's, and has 0's on the diagonal:
A = [ ...
0, 1, 1, 0, 0, 0;
1, 0, 1, 1, 1, 1;
1, 1, 0, 1, 0, 0;
0, 1, 1, 0, 0, 0;
0, 1, 0, 0, 0, 1;
0, 1, 0, 0, 1, 0];
In MATLAB, the edge list will be an array E of 2 rows and M columns, where M is the number of items of information. For our example matrix, E might be the following 2x8 array:
E1 = [ 1, 1, 2, 2, 2, 2, 3, 5;
2, 3, 3, 4, 5, 6, 4, 6];
or the following 2x16 array:
E2 = [ 1, 2, 1, 3, 2, 3, 2, 4, 2, 5, 2, 6, 3, 4, 5, 6;
2, 1, 3, 1, 3, 2, 4, 2, 5, 2, 6, 2, 4, 3, 6, 5];
Your job is to write a function hw056() which takes an edge list E as
input and returns an adjacency matrix A as output. If (I,J) is a pair
of nodes in the edge list, then A(I,J) and A(J,I) should both be set to 1.
But also, if (I,J) and (J,I) are both in the edge list, then A(I,J) and
A(J,I) should still both be set to 1 (not 2!).
INSTRUCTIONS:
function A = hw056 ( E )
[ two, edge_num ] = size ( E ).
We expect "two" to be set to two; we really only need the value of
"edge_num".
n = ?
Compute n, the number of nodes, by finding the maximum value in E.
n = max(E) is ALMOST the right command, but not quite,
because E is an array!
A = ?
Initialize A to be an nxn matrix of zeros.
There are edge_num edges in E. Each edge is a pair of values I and J.
for edge = 1 : edge_num
i = ?
j = ?
update the appropriate entries of A
return
end
CHECK: For either edge list E1 or E2 listed above, you should get the adjacency matrix A listed above.
SUBMIT: Your file should be named "hw056.m", and begin with:
% hw056.m
% YOUR NAME
% This script (describe what it does)