adjacency_list.h

Go to the documentation of this file.

#ifndef GRAPHLIB_INTERNAL_ADJACENCY_LIST_H
#define GRAPHLIB_INTERNAL_ADJACENCY_LIST_H
 
#include <algorithm>
#include <cassert>
#include <iterator>
#include <ostream>
#include <set>
#include <unordered_map>
#include <unordered_set>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib::Internal {
 
template <valid_id_type I, valid_edge_type<I> E>
class AdjacencyList;
 
template <typename I, typename E>
std::ostream& operator<<(std::ostream& os, const AdjacencyList<I, E>& adj_list);

template <valid_id_type I, valid_edge_type<I> E>
class AdjacencyList {
public:
    using id_type = I;   
    using edge_type = E; 

    bool has_node_id(const id_type node_id) const
    {
        return adj_map_.contains(node_id);
    }

    std::unordered_set<id_type> get_node_ids() const
    {
        auto keys = std::unordered_set<id_type> {};
        std::transform(adj_map_.begin(), adj_map_.end(), std::inserter(keys, keys.end()),
                       [](const auto& pair) { return pair.first; });
        return keys;
    }

    std::set<id_type> get_neighboring_node_ids(const id_type node_id) const
    {
        assert(has_node_id(node_id));
 
        auto edges = adj_map_.at(node_id);
        auto neighbor_ids = std::set<id_type> {};
        std::transform(edges.begin(), edges.end(), std::inserter(neighbor_ids, neighbor_ids.end()),
                       [](const edge_type edge) { return edge.node_id; });
        return neighbor_ids;
    }

    void add_node_id(const id_type node_id)
    {
        assert(!has_node_id(node_id));
 
        adj_map_.insert({node_id, std::set<edge_type> {}});
    }

    void remove_node_id(const id_type node_id)
    {
        assert(has_node_id(node_id));
 
        for (auto& [_, edge_set] : adj_map_) {
            for (auto it = edge_set.begin(); it != edge_set.end();) {
                if (it->node_id == node_id)
                    it = edge_set.erase(it);
                else
                    ++it;
            }
        }
 
        adj_map_.erase(node_id);
    }

    bool has_edge(const id_type from_id, const id_type to_id) const
    {
        assert(has_node_id(from_id) && has_node_id(to_id));
 
        auto it = std::find_if(adj_map_.at(from_id).begin(), adj_map_.at(from_id).end(),
                               [to_id](const edge_type& edge) { return edge.node_id == to_id; });
        return it != adj_map_.at(from_id).end();
    }

    edge_type get_edge(const id_type from_id, const id_type to_id) const
    {
        assert(has_edge(from_id, to_id));
 
        auto it = std::find_if(adj_map_.at(from_id).begin(), adj_map_.at(from_id).end(),
                               [to_id](const edge_type& edge) { return edge.node_id == to_id; });
        return *it;
    }

    std::set<edge_type> get_edges(const id_type from_id) const
    {
        assert(has_node_id(from_id));
 
        return adj_map_.at(from_id);
    }

    void add_edge(const id_type from_id, edge_type edge)
    {
        assert(has_node_id(from_id) && has_node_id(edge.node_id) && !has_edge(from_id, edge.node_id));
 
        adj_map_.at(from_id).insert(edge);
    }

    void remove_edge(const id_type from_id, const id_type to_id)
    {
        assert(has_edge(from_id, to_id));
 
        adj_map_.at(from_id).erase(get_edge(from_id, to_id));
    }

    std::size_t node_id_count() const
    {
        return get_node_ids().size();
    }

    std::size_t edge_count() const
    {
        std::size_t count {0};
        for (const auto& [_, edge_set] : adj_map_)
            count += edge_set.size();
        return count;
    }

    constexpr bool operator==(const AdjacencyList& other) const
    {
        return adj_map_ == other.adj_map_;
    }

    template <typename D>
        requires GraphLib::Internal::is_printable<D> && GraphLib::Internal::valid_data_type<D>
    void print_with_data_map(std::ostream& os, const std::unordered_map<I, D> data_map) const
    {
        for (const auto& [node, edges] : adj_map_) {
            D node_value = data_map.at(node);
            os << node_value << ": [";
            bool first = true;
            for (const auto& edge : edges) {
                if (!first)
                    os << ", ";
                edge.print_with_data(os, data_map.at(edge.node_id));
                first = false;
            }
            os << "]\n";
        }
    }
 
private:
    std::unordered_map<id_type, std::set<edge_type>> adj_map_ {}; 
    friend std::ostream& operator<< <id_type, edge_type>(
        std::ostream& os,
        const AdjacencyList<id_type, edge_type>& adj_list); 
};

template <typename I, typename E>
std::ostream& operator<<(std::ostream& os, const AdjacencyList<I, E>& adj_list)
{
    for (const auto& [node, edges] : adj_list.adj_map_) {
        os << node << ": [";
        bool first = true;
        for (const auto& edge : edges) {
            if (!first)
                os << ", ";
            os << edge;
            first = false;
        }
        os << "]\n";
    }
    return os;
}
 
} // namespace GraphLib::Internal
 
#endif