by Graph is a data structure which consists a set of vertices which is called as Node, together with a set of collection of pair of vertices which is called as an Edge.
A graph data structure can be represented as a pair (V, E) where V is a set of nodes called vertices and E is a collection of pairs of vertices called edges. Graphs are used to solve many real life problems such as fastest ways to go from A to B etc.
Before going ahead have a look into Graph Basics.
Graph implementation
Here we are going to talk about a simple implementation of Graph data structures in C++ along with some basic graph operations implementation such as adding edges etc.
Let’s have a look on basic class definition for Graphs.
class Graph
{
private:
int m_nodes;
int m_edges;
int **edges;
/* This parameter will be used to check whether
graph is undirected or not */
bool isUndirected;
public:
Graph (int nodes, bool isUndirected);
int getNumberOfNodes ();
int getNumberOfEdges ();
void getEdges ();
bool addEdge (int srcNode, int dstNode);
~Graph ();
};
Now let’s have a look at each of these function implementation, Starting with constructors and destructors.
Note: Here in this implementation, we are not considering adding node functionality as that would require its own article to be fair.
Graph::Graph (int nodes, bool isUndirected): m_nodes (nodes),
m_edges (0),
edges (NULL),
isUndirected (isUndirected),
isConnected (-1)
{
edges = new int* [m_nodes];
if (!edges)
{
cout << "Graph initialization failed " << endl;
}
for (int i = 0; i < m_nodes; i++)
{
edges[i] = new int[m_nodes];
}
for (int i = 0; i < m_edges; i++)
{
for (int j = 0; j < m_edges; j++)
{
edges[i][j] = 0;
}
}
}
Graph::~Graph ()
{
if (!edges)
{
cout << "Graph was never initializaed, nothing to free " << endl;
return;
}
for (int i = 0; i < m_nodes; i++)
{
delete [] edges[i];
}
delete [] edges;
}
As you can see in constructor we are allocating Graph nodes and adjacency matrix memory and in destructor we are freeing the same.
Let’s look into some helper functions which will provide basic information of the Graph.
/* This function will return number of Nodes present in Graph */
int Graph::getNumberOfNodes ()
{
return m_nodes;
}
/* This function will return number of Edges present in Graph */
int Graph::getNumberOfEdges ()
{
return m_edges;
}
/* This function will print information related to edge(i, j) in the Graph */
void Graph::getEdges ()
{
if (!edges)
{
cout << "Graph is not initialized properly " << endl;
}
for (int i = 0; i < m_nodes; i++)
{
for (int j = 0; j < m_nodes; j++)
{
cout << "Node " << i << " and Node " << j << " edge status: " << edges[i][j] << endl;
}
}
}
Now, let’s look into the function which will allow to add an edge details between node i and j.
As you can see in the below function, we have handled the undirected/ directed behaviour of graph also.
bool Graph::addEdge (int srcNode, int dstNode)
{
if (srcNode >= m_nodes || dstNode >= m_nodes)
{
cout << "srcNode " << srcNode << " or dstNode " << dstNode << " is out of known max node: " << m_nodes << endl;
return false;
}
if (edges[srcNode][dstNode])
{
cout << "srcNode " << srcNode << " or dstNode " << dstNode << " is already existed." << endl;
return false;
}
edges[srcNode][dstNode] = 1;
++m_edges;
if (isUndirected)
{
edges[dstNode][srcNode] = 1;
++m_edges;
}
return true;
}
As you can see, this Graph implementation is self sufficient to satisfy both undirected and directed Graphs need.
Let’s look into usage of these functions.
int main ()
{
Graph g(5, true);
g.addEdge (1,2);
g.addEdge (0,2);
g.addEdge (3,2);
g.addEdge (4,2);
g.addEdge (1,3);
g.addEdge (1,4);
g.addEdge (1,5);
g.addEdge (1,7);
g.addEdge (1,0);
g.addEdge (2,2);
g.addEdge (3,2);
g.addEdge (4,2);
g.addEdge (5,2);
cout << "Graph has nodes: " << g.getNumberOfNodes () << endl;
cout << "Graph has edges: " << g.getNumberOfEdges () << endl;
g.getEdges ();
}
Let’s analyse the output of this main function.
srcNode 1 or dstNode 5 is out of known max node: 5
srcNode 1 or dstNode 7 is out of known max node: 5
srcNode 3 or dstNode 2 is already existed.
srcNode 4 or dstNode 2 is already existed.
srcNode 5 or dstNode 2 is out of known max node: 5
Graph has nodes: 5
Graph has edges: 16
Node 0 and Node 0 edge status: 0
Node 0 and Node 1 edge status: 1
Node 0 and Node 2 edge status: 1
Node 0 and Node 3 edge status: 0
Node 0 and Node 4 edge status: 0
Node 1 and Node 0 edge status: 1
Node 1 and Node 1 edge status: 0
Node 1 and Node 2 edge status: 1
Node 1 and Node 3 edge status: 1
Node 1 and Node 4 edge status: 1
Node 2 and Node 0 edge status: 1
Node 2 and Node 1 edge status: 1
Node 2 and Node 2 edge status: 1
Node 2 and Node 3 edge status: 1
Node 2 and Node 4 edge status: 1
Node 3 and Node 0 edge status: 0
Node 3 and Node 1 edge status: 1
Node 3 and Node 2 edge status: 1
Node 3 and Node 3 edge status: 0
Node 3 and Node 4 edge status: 0
Node 4 and Node 0 edge status: 0
Node 4 and Node 1 edge status: 1
Node 4 and Node 2 edge status: 1
Node 4 and Node 3 edge status: 0
Node 4 and Node 4 edge status: 0
