C++ : Adjacency list implementation for storing graph
Below is a simple example of a graph where each node has a number that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to. An adjacency list can be implemented as a list of lists in C++.
Example : In the below adjacency list we can see a) Node 0 has a list storing adjacent nodes 1 and 2. b) Node 1 has a list storing adjacent nodes 0, 3 and 4.
C++: Storing graph in an adjacency list using list of lists.
#include<iostream>
#include<list>
using namespace std;
class Graph {
private:
int nodes;
list<int> *adjlist;
public:
Graph() {
}
Graph (int nodes) { // Allocate resources
adjlist = new list<int> [nodes];
this->nodes = nodes;
}
~Graph () { // Free allocated resources
delete [] adjlist;
}
void AddEdge (int src, int dst) {
adjlist[src].push_back(dst);
adjlist[dst].push_back(src);
}
void Iterate (int src) {
cout << src << " : ";
for (auto& adj_node : adjlist[src]) {
cout << adj_node << " ";
} cout << endl;
}
};
int main()
{
Graph g(7);
g.AddEdge(0,1);
g.AddEdge(0,2);
g.AddEdge(1,3);
g.AddEdge(1,4);
g.AddEdge(2,3);
g.AddEdge(3,5);
g.AddEdge(4,6);
g.AddEdge(5,6);
cout << "Adjacency list implementation for graph" << endl;
g.Iterate(0);
g.Iterate(1);
g.Iterate(4);
return 0;
}
Output
Adjacency list implementation for graph
0 : 1 2
1 : 0 3 4
4 : 1 6
Storing graph as an adjacency list using a map of node and list of nodes
Below is an example of a graph where each node has a name (string) and an id (number) that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to. An adjacency list for such a graph can be implemented as a map of node and list of nodes in C++.
Example : In the below adjacency list we can see a) Node ( Alfa, 1 ) has a list storing adjacent nodes ( Cod, 2 ), ( Pi, 3 ) and ( Ram , 4)
Note : Node is defined as a custom class hence we need to overload < (less than) operator so that it works with map other option is to use a compare class that overloads () operator.
C++: Storing graph in an adjacency list using map of Node and a list of Node(s). Operator < (less than) is overloaded.
#include<list>
#include<map>
using namespace std;
class Node {
private:
string name;
int id;
public:
Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
}
bool operator < (const Node& n) const {
if (n.name < this->name) {
return true;
}
return false;
}
void Display () const {
cout << "(" << name << " , " << id << ") ";
}
};
class Graph {
private:
map<Node, list<Node>> adjlist;
public:
Graph() {
}
void Add_Adjacent_Nodes (Node& src, list<Node>& adj_nodes) {
adjlist.insert( { src, adj_nodes } );
}
void Iterate (Node src) {
src.Display(); cout << " : ";
for (const auto& node : adjlist[src]) {
node.Display();
} cout << endl;
}
};
int main()
{
Node n1("Alfa", 1);
Node n2("Cod", 2);
Node n3("Pi", 3);
Node n4("Ram", 4);
Node n5("Yo", 5);
list<Node> n1_list = { n2, n3, n4 };
list<Node> n2_list = { n1, n4 };
list<Node> n3_list = { n1, n4, n5 };
list<Node> n4_list = { n1, n2, n3, n5 };
list<Node> n5_list = { n3, n4 };
cout << "Adjacency list implementation for graph" << endl;
Graph g;
g.Add_Adjacent_Nodes (n1, n1_list);
g.Add_Adjacent_Nodes (n2, n2_list);
g.Add_Adjacent_Nodes (n3, n3_list);
g.Add_Adjacent_Nodes (n4, n4_list);
g.Add_Adjacent_Nodes (n5, n5_list);
g.Iterate(n1);
g.Iterate(n2);
g.Iterate(n3);
g.Iterate(n4);
return 0;
}
Output
Adjacency list implementation for graph
(Alfa , 1) : (Cod , 2) (Pi , 3) (Ram , 4)
(Cod , 2) : (Alfa , 1) (Ram , 4)
(Pi , 3) : (Alfa , 1) (Ram , 4) (Yo , 5)
(Ram , 4) : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5)
C++: Storing graph in an adjacency list using map of Node and a list of Node(s). Creating a map using a Compare Class with operator () overloaded.
#include<iostream>
#include<list>
#include<map>
using namespace std;
class Node {
private:
string name;
int id;
public:
Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
}
void Display () const {
cout << "(" << name << " , " << id << ") ";
}
int GetId() const {
return id;
}
};
class Compare {
public:
bool operator () (const Node& a, const Node& b) const {
return (a.GetId() < b.GetId());
}
};
class Graph {
private:
map<Node, list<Node>, Compare> adjlist;
public:
Graph() {
}
void Add_Adjacent_Nodes (Node& src, list<Node>& adj_nodes) {
adjlist.insert( { src, adj_nodes } );
}
void Iterate (Node src) {
src.Display(); cout << " : ";
for (auto& node : adjlist[src]) {
node.Display();
} cout << endl;
}
};
int main()
{
Node n1("Alfa", 1);
Node n2("Cod", 2);
Node n3("Pi", 3);
Node n4("Ram", 4);
Node n5("Yo", 5);
list<Node> n1_list = { n2, n3, n4 };
list<Node> n2_list = { n1, n4 };
list<Node> n3_list = { n1, n4, n5 };
list<Node> n4_list = { n1, n2, n3, n5 };
list<Node> n5_list = { n3, n4 };
cout << "Adjacency list implementation for graph" << endl;
Graph g;
g.Add_Adjacent_Nodes (n1, n1_list);
g.Add_Adjacent_Nodes (n2, n2_list);
g.Add_Adjacent_Nodes (n3, n3_list);
g.Add_Adjacent_Nodes (n4, n4_list);
g.Add_Adjacent_Nodes (n5, n5_list);
g.Iterate(n1);
g.Iterate(n2);
g.Iterate(n3);
g.Iterate(n4);
return 0;
}
Output
Adjacency list implementation for graph
(Alfa , 1) : (Cod , 2) (Pi , 3) (Ram , 4)
(Cod , 2) : (Alfa , 1) (Ram , 4)
(Pi , 3) : (Alfa , 1) (Ram , 4) (Yo , 5)
(Ram , 4) : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5)