Non-directed graph representing clusters of different genes

graph.cpp

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>
#include <cassert>

template <typename T>
void print_vector(const std::vector<T>& vec)
{
    std::cout << "{";
    for (size_t idx = 0; idx < vec.size(); ++idx)
    {
        std::cout << vec[idx];
        if (idx != vec.size()-1)
        {
            std::cout << ",";
        }
    }
    std::cout << "}\n";
}

class Graph
{
public:
    Graph(){}
    void add_edge(char v1, char v2);
    void add_node(char v);
    void print_adj_list();
    void get_similarity_clusters();
    
private:
    std::map<char, std::vector<char>> adj_list;
    void add_edge_helper(char v1, char v2);
};

void Graph::add_edge(char v1, char v2)
{
    add_edge_helper(v1, v2);
    add_edge_helper(v2, v1);
}

void Graph::add_edge_helper(char v1, char v2)
{
    auto it = adj_list.find(v1);
    if (it != adj_list.end())
    {
        if (std::find(it->second.begin(), it->second.end(), v2) == it->second.end())
        {
            it->second.push_back(v2);
        }
    }
    else
    {
        adj_list.insert(std::pair<char, std::vector<char>>(v1, std::vector<char>(1, v2)));
    }
}

void Graph::add_node(char v)
{
    auto it = adj_list.find(v);
    if (it == adj_list.end())
    {
        adj_list.insert(std::pair<char, std::vector<char>>(v, std::vector<char>(0)));
    }
}

void Graph::print_adj_list()
{
    for (auto elem : adj_list)
    {
        std::cout << elem.first << ": ";  // first, print index of node for easier visualisation in standard output
        for (char v : elem.second)
        {
            std::cout << v << " ";
        }
        std::cout << "\n";
    }
}

void Graph::get_similarity_clusters()  // depth-first-search
{
    std::vector<char> visited_nodes;
    for (auto elem : adj_list)
    {
        if (std::find(visited_nodes.begin(), visited_nodes.end(), elem.first) == visited_nodes.end())
        {
            std::vector<char> similarity_cluster;
            std::stack<char> s;
            
            visited_nodes.push_back(elem.first);
            s.push(elem.first);
            
            while (!s.empty())
            {
                char discovered_node = s.top();
                similarity_cluster.push_back(discovered_node);
                s.pop();
                
                for (char v : adj_list[discovered_node])
                {
                    if (std::find(visited_nodes.begin(), visited_nodes.end(), v) == visited_nodes.end())
                    {
                        visited_nodes.push_back(v);
                        s.push(v);
                    }
                }
            }
            
            print_vector(similarity_cluster);
        }
    }
    assert(visited_nodes.size() == adj_list.size());
}

int main(){
    Graph graph;
    graph.add_edge('a', 'b');
    graph.add_edge('a', 'c');
    graph.add_edge('a', 'e');
    graph.add_edge('b', 'c');
    graph.add_edge('b', 'd');
    graph.add_edge('c', 'd');
    graph.add_edge('c', 'e');
    graph.add_edge('e', 'f');
    graph.add_edge('e', 'g');
    graph.add_node('h');
    graph.add_edge('i', 'j');
    graph.add_edge('j', 'k');
    graph.add_edge('j', 'l');
    graph.add_edge('k', 'l');
    graph.add_edge('l', 'm');
    graph.add_edge('l', 'n');
    graph.add_edge('l', 'p');
    graph.add_edge('m', 'n');
    graph.add_edge('n', 'o');
    graph.add_edge('o', 'p');
    graph.get_similarity_clusters();
    
    return 0;
}