What is a graph ? The name may suggest something that has to do with graphics, which in a way is true but graphs are generally more than that. Their main use is at describing relationships between various entities in the real world. For example consider four persons – call them Mary, John, April and George. Now let us try to examine the relationships between them. For this we will use arrows with the following convention – we have an arrow going from X to Y if X likes Y, otherwise no arrow at all. Consider the following – John likes April, April likes John, Mary likes George, George likes April, Mary likes John – and draw the diagram below.
With this overall view we may more easily arrive at certain conclusions. It is now obvious that April and John are the most “liked” persons, while there is nobody who likes Mary. Also we see that the relationship between John and April is reciprocal. In the following we will define some basic graph terminology based on the previous example.
A vertex (or node) is the representation of an entity in the real world as part of a network of such entities, where each may be connected to another on the basis of a particular relation. This connection is indicated with an edge (or arc) drawn between the corresponding vertices. In the above diagram, the vertices are the circles – (John), (Mary), (George), (April) – while edges are denoted by arrows. Because replacing names (or any other kind of information describing the entity) with consecutive numbers does not affect the initial graph and the conclusions we may get based upon it, we might as well use the following diagram :
Now we can give a more rigorous definition of the graph – an ordered pair of sets G = ( X, U ) where
X = vertex set = { 1, 2, …, n } , n = number of vertices
U = edge set = { ( x, y ) | x, y are from X and there is an edge between x and y }
For example, the previous graph has X = { 1, 2, 3, 4 } and U = { ( 1, 2 ), ( 2, 1 ), ( 3, 1 ), ( 4, 2 ), ( 4, 3 ) } or as in the initial formulation :
X = { April, John, George, Mary } and U = { ( April, John ), ( John, April ), ( George, April ), ( Mary, John ), ( Mary, George ) }
So far the edges we have drawn were arrows with a specific direction (George likes April, but April does not like George). From now on we will only consider reciprocal relationships as between John and April. Also we will use line segments instead of arrows. These are in fact bidirectional arrows and whenever we have a line from x to y we should bear in mind that it is actually formed of two edges ( x, y ) and ( y, x ).
We may now give the definition of an undirected graph – an ordered pair of sets G = ( X, U ) where
X = vertex set = { 1, 2, …, n }, n = number of vertices
U = edge set = { ( x, y ) | x, y are from X and there is a bidirectional arrow between x and y }
For example, the undirected graph above has X = { 1, 2, 3, 4, 5 } and U = { ( 1, 2 ), ( 1, 4 ), ( 2, 3 ), ( 4, 5 ) }.
Now it would be nice if we found a method of storing such data structures in the memory of a computer. But before we do that let us try and optimize things a little bit – look at the vertex set X, is it really necessary to keep all elements 1, 2, …, n ? Or is it possible to replace the set X by a single value n, the number of vertices of the graph ? Of course it is possible. This means that an arbitrary undirected graph is only identified by an ordered pair G = ( n, U ) where U is defined as above.
The adjacency matrix is a square binary matrix (its elements are either 0 or 1) of order n (this is the number of graph vertices) with the following property :
A( i, j ) = 1 if the ( i, j ) pair is found in the edge set U, otherwise A( i, j ) = 0, for all values 1 <= i, j <= n
It is easy to see that this matrix is symmetric since whenever we have a ( i, j ) pair we also have its corresponding ( j, i ) pair – remember the graph is undirected. We have therefore found a method of storing a graph into a square binary matrix which is easy to store in memory. Next we will implement a C++ class Graph that uses stream operators to initialize and display the contents of a graph stored as an adjacency matrix. Also, the isConnected function tests for the connectivity of two vertices in the graph.
#include <iostream.h>
class Graph {
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
friend istream& operator>>(istream&, Graph&);
friend ostream& operator<<(ostream&, Graph&);
private :
int n;
int **A;
};
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
istream& operator >> (istream &in, Graph &G) {
int p, x, y;
cout << "Input number of edges : ";
in >> p;
cout << endl << "Input edges :" << endl;
for (int i = 0; i < p; ++i) {
cout << "Edge " << i+1 << endl;
cout << " x = ";
in >> x;
cout << " y = ";
in >> y;
--x; --y;
G.A[x][y] = G.A[y][x] = 1;
}
return in;
}
ostream& operator << (ostream &out, Graph &G) {
int i, j;
out << endl;
out << "Adjacency matrix : " << endl << endl;
for (i = 0; i < G.n; ++i) {
for (j = 0; j < G.n; ++j)
out << G.A[i][j] << " ";
out << endl;
}
return out;
}
|
It is time to test our class :
void main() {
int a, x, y;
cout << "Input number of vertices : ";
cin >> a;
Graph g(a);
cin >> g;
cout << g;
cout << endl << "Test for connectivity" << endl << endl;
cout << " Input first node : ";
cin >> x;
cout << "Input second node : ";
cin >> y;
cout << endl << x << " and " << y;
if (g.isConnected(x, y)) cout << " are connected." << endl;
else cout << " are not connected." << endl;
}
|
To conclude, we have found a way of storing a graph in memory and test for the connectivity of two vertices. This may not seem such a great achievement but there are actually lots of applications that require this simple test. Remember that graphs are about relationships and relationships arise everywhere around us.