I am learning graphs and most of the implementations that I see are meant for int. So, I decided to code an example that can take other data types such as char or float. I did see this prior to posting my example (but not prior to coding my example). The example in the link is similar to creating a Tree where a separate Node class is used to keep track of node value, left and right child. In the link, instead of left and right child, the GraphNode class keeps track of neighbors.
My code does not use that approach and instead keeps the Adjacency List completely to Graph class, similar to usual implementations meant for int type. The idea is that if anyone needs to define a custom data type, it can be coded later (So, my code does not have a counterpart for GraphNode yet). The Graph is initialized by a vector of edges. The edges are represented by std::pair of nodes/ vertices involved. I have posted my code below. I am interested in knowing if there is a way to represent adjacency list, better than a map of lists, using stl containers, and can still handle different data types. However, any reviews or improvements or suggestions are welcome:
#include <iostream>
#include <vector>
#include <list>
#include <map>
template<typename T>
void print_list(std::list<T> l)
{
typename std::list<T>::const_iterator it;
for(it = l.cbegin(); it != l.cend(); it++)
{
std::cout << *it << "\t";
}
std::cout << std::endl;
}
template<typename T>
class Graph
{
//Undirected Graph
std::map<T, std::list<T>> adj_list;
public:
Graph(std::vector<std::pair<T, T>>);
void add_edge(std::pair<T, T>);
size_t size();
void print_adj_list();
};
template<typename T>
Graph<T>::Graph(std::vector<std::pair<T, T>> edges)
{
for(size_t i = 0; i < edges.size(); i++)
{
this -> add_edge(edges[i]);
}
}
//Undirected Graph
template<typename T>
void Graph<T>::add_edge(std::pair<T, T> edge)
{
adj_list[edge.first].push_back(edge.second);
adj_list[edge.second].push_back(edge.first);
}
template<typename T>
size_t Graph<T>::size()
{
std::cout << "Size of Graph(no. of vertices): " << std::endl;
return adj_list.size();
}
template<typename T>
void Graph<T>::print_adj_list()
{
std::cout << "The Adjacency List: " << std::endl;
typename std::map<T, std::list<T>>::const_iterator it;
for(it = adj_list.cbegin(); it != adj_list.cend(); it++)
{
std::cout << it -> first << "\t";
print_list<T>(it -> second);
}
}
int main()
{
/*std::vector<std::pair<int, int>> v;
v.push_back({1, 2});
v.push_back({2, 8});
v.push_back({2, 5});
v.push_back({2, 4});
v.push_back({3, 4});
v.push_back({5, 9});
v.push_back({5, 7});
v.push_back({5, 6});
Graph<int> g{v};*/
std::vector<std::pair<char, char>> v;
v.push_back({'a', 'b'});
v.push_back({'b', 'h'});
v.push_back({'b', 'e'});
v.push_back({'b', 'd'});
v.push_back({'c', 'd'});
v.push_back({'e', 'i'});
v.push_back({'e', 'g'});
v.push_back({'e', 'f'});
Graph<char> g{v};
g.print_adj_list();
std::cout << g.size() << std::endl;
g.add_edge({'i', 'k'});
g.add_edge({'f', 'k'});
g.print_adj_list();
std::cout << g.size() << std::endl;
return 0;
}
