1
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

Pass parameters by const &

In print_list and your Graph constructor, you pass in the parameters by value. This will make unnecessary copies of the vectors. Passing in the values by const reference will avoid making these copies.

Make use of the auto keyword or range-based for loops

You have several places with a long type name to get the type to use for an iterator. These would be great spots to make use of the auto keyword. For example, auto it = l.cbegin().

However, in these cases, you can do better. You can use the range-based for statement instead.

Combining these for the print_list function gives us

template<typename T>
void print_list(const std::list<T> &l)
{
    for (auto v: l)
        std::cout << v << '\t';
    std::cout << std::endl;
}

Similar changes can be made to your Graph constructor and print_adj_list.

You can also pass the pair to add_edge by const reference, although with the small types you're using that won't really gain much.

add_edge assumes that all your edges are bidirectional. Some adjacency lists have edges that only go in one direction.

Do you need that cout in size? All it is really doing is telling you that the function has been called.

You should be able to call print_list without having to specify the type. The compiler should be able to deduce the template type to use.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the response. I will make the changes corresponding to const & and auto. I made an assumption that it was a bidirectional graph. I felt that the output statement in size makes the results more presentable. I was using eclipse and it showed an error when I didn’t specify type for print_list. This was before compiling, when eclipse inspects the code automatically. So, that’s probably an eclipse issue. However, is the overall logic of implementation correct? \$\endgroup\$ – skr_robo Aug 18 '18 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.