Graph Class Implementation In C++

Filed Under: C++
Graph Class Implementation In C

In today’s article, we will learn about graph class implementation in C++. Graphs are one of the most important data structures used to represent data. We will also look at some of the countless applications of graphs.

What Is A Graph?

First things first, what is a graph? Graphs are non-linear data structures that consist of various nodes and the edges related to these nodes. Graphs are not a predefined data type. Graphs are commonly represented in two ways – either we use an adjacency list representation or we use matrix type representation.

Both types have their own benefits.

Matrix type has the benefit of O(1) time complexity for access, but we need O(N2) space complexity even if we want to represent only a couple of nodes.

In this article, we will develop a template graph class using adjacency type representation.

Real-Life Applications Of Graphs

There are quite literally countless applications of graphs in our lives, a few of which are,

  • Shortest path in maps
  • Social networking
  • Circuit design
  • Routing algorithms
  • Delivery route for vans
  • Resolving dependencies
  • Graphs in deep learning
  • Web development(Document Obect Model Tree)
  • Image processing
  • Paint bucket tool/ connected components

Graph Class Structure in C++

Let’s quickly jump to the structure of a graph class. In this discussion, we will discuss the data members and the member functions of our template graph class.

Example Graph
Example Graph

Data Members

  • map <T, list <pair <T, int>> l;

And that’s it. The data member defined above is sufficient enough to fulfill our current needs. Let’s see what it represents.

  • An map represents a key, pair format
  • In this key-pair tuple
  • The key is a generic data type T
  • The pair associated with a key is a pair that represents the neighbour as generic data type T and the distance of the key from the neighbour with an integer.

Member Functions for Graph Class

Moving on to the member functions of the class.

  • void add_edge(T node, T neighbour, int distance, bool is_directed = true): This function will add an edge between two nodes
  • void print_graph(T source): This function will traverse over the graph and print its contents

void add_edge(T node, T neighbour, int distance, bool is_directed = true)

void add_edge(T node, T neighbour, int distance, bool is_directed = false)
	{
		// is_directed variable is marked as false by default but
		// if the graph is a directed graph, we will not add the edge
		// between the neighbour and the node
		l[node].push_back(make_pair(neighbour, distance));

		if(!is_directed)
			l[neighbour].push_back(make_pair(node, distance));
	}

void print_graph(T source)

void print_graph()
	{
		// now we will iterate over all the keys in the map
		// then we will print the linked list of neighbours
		// associated with these nodes

		for(auto p : l)
		{
			// iterate over all the neighbours of this particular node
			T node = p.first;
			list <pair <T, int>> neighbour = p.second;

			cout << "Neighbours of: " << node << " are:\n";

			for(auto nbr : neighbour)
			{
				T dest = nbr.first;
				int distance = nbr.second;

				cout << "Neighbour: " << dest << " " << " Distance: "<< distance << endl;
			}
			cout << endl;
		}
	}
Graph Class Code
Graph Class Code

C++ Program To Demonstrate Graph Class

#include <iostream>
#include <map>
#include <list>

using namespace std;

template <typename T>
class Graph
{
	map<T, list <pair <T, int>>> l; // adjacency list
public:
	void add_edge(T node, T neighbour, int distance, bool is_directed = false)
	{
		// is_directed variable is marked as false by default but
		// if the graph is a directed graph, we will not add the edge
		// between the neighbour and the node
		l[node].push_back(make_pair(neighbour, distance));

		if(!is_directed)
			l[neighbour].push_back(make_pair(node, distance));
	}

	void print_graph()
	{
		// now we will iterate over all the keys in the map
		// then we will print the linked list of neighbours
		// associated with these nodes

		for(auto p : l)
		{
			// iterate over all the neighbours of this particular node
			T node = p.first;
			list <pair <T, int>> neighbour = p.second;

			cout << "Neighbours of: " << node << " are:\n";

			for(auto nbr : neighbour)
			{
				T dest = nbr.first;
				int distance = nbr.second;

				cout << "Neighbour: " << dest << " " << " Distance: "<< distance << endl;
			}
			cout << endl;
		}
	}

};

int main()
{
	Graph <string> g;
	
	g.add_edge("Delhi", "Jaipur", 250, false);
	g.add_edge("Delhi", "Shamli", 147, false);
	g.add_edge("Delhi", "Mumbai", 1100, false);
	g.add_edge("Shamli", "Lucknow", 377, false);
	g.add_edge("Shamli", "Baghpat", 50, false);
	g.add_edge("Jaipur", "Bikaner", 300, false);
	g.add_edge("Udaipur", "Jaipur", 600, false);
	g.add_edge("Uttarlai", "Jaipur", 500, false);
	g.add_edge("Jaipur", "Jodhpur", 150, false);
	g.add_edge("Mumbai", "Jaipur", 1000, false);

	g.print_graph();

	return 0;
}
Main Function 1
Main Function 1

Output

Graph Class Program Output
Graph Class Program Output

Conclusion

This article was primarily about Graph Class Implementation In C++. Let’s recall what we learned from today’s article. We started by discussing a graph, its uses in real-life, and the basic structure of a template graph class. Later we learned to implement the add_edge() and the print_graph() functions in C++. In the end, we looked at a C++ program that featured adding edges to a graph and printing it.

References

To learn more about graphs, and linked lists, you can refer to the following websites.

close
Generic selectors
Exact matches only
Search in title
Search in content