abstract_graph.h

Go to the documentation of this file.

#ifndef GRAPHLIB_INTERNAL_ABSTRACT_GRAPH_H
#define GRAPHLIB_INTERNAL_ABSTRACT_GRAPH_H
 
#include <cstddef>
#include <iostream>
#include <limits>
#include <ostream>
#include <queue>
#include <set>
#include <stdexcept>
#include <unordered_map>
#include <vector>
 
#include "GraphLib/internal/adjacency_list.h"
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib::Internal {
 
template <valid_data_type D, valid_id_type I, valid_edge_type<I> E>
std::ostream& operator<<(std::ostream& os, const Graph<D, I, E>& graph);

template <valid_data_type D, valid_id_type I, valid_edge_type<I> E>
class Graph {
public:
    using data_type = D; 
    using id_type = I;   
    using edge_type = E; 
 
    virtual ~Graph() = default; 

    [[nodiscard]] virtual bool is_directed() const = 0;

    [[nodiscard]] virtual bool is_weighted() const = 0;
 
    //
    // State Inspection
    //

    constexpr bool operator==(const Graph& other) const
    {
        return this->data_map_ == other.data_map_ && this->adj_list_ == other.adj_list_;
    }

    bool is_full()
    {
        return data_map_.size() == std::numeric_limits<id_type>::max();
    }

    bool node_exists(const id_type id) const
    {
        return adj_list_.has_node_id(id);
    }

    id_type node_count() const
    {
        return adj_list_.node_id_count();
    }

    size_t edge_count() const
    {
        if (is_directed())
            return adj_list_.edge_count();
        else
            return (adj_list_.edge_count() / 2);
    }

    std::unordered_set<id_type> get_nodes() const
    {
        return adj_list_.get_node_ids();
    }

    const data_type& get_node_data(const id_type id) const
    {
        if (!node_exists(id)) {
            throw std::invalid_argument("Node does not exist");
        }
        return data_map_.at(id);
    }

    const std::set<id_type> get_neighbors(const id_type id) const
    {
        return adj_list_.get_neighboring_node_ids(id);
    }

    bool has_edge(const id_type from_id, const id_type to_id) const
    {
        return adj_list_.has_edge(from_id, to_id);
    }

    edge_type get_edge(const id_type from_id, const id_type to_id) const
    {
        if (!has_edge(from_id, to_id)) {
            throw std::invalid_argument("Edge does not exist");
        }
        return adj_list_.get_edge(from_id, to_id);
    }

    std::set<edge_type> get_edges(const id_type from_id) const
    {
        return adj_list_.get_edges(from_id);
    }

    void print_data_map() const
    {
        std::cout << "data_map_: \n";
        for (auto i : data_map_) {
            std::cout << i.first << " : " << i.second << "\n";
        }
        std::cout << "---\n";
    };

    void print_adjacency_list() const
    {
        std::cout << *this << "\n";
    }

    void print_with_data(std::ostream& os) const
    {
        if constexpr (!GraphLib::Internal::is_printable<D>) {
            throw std::invalid_argument("The Data is not printable");
        }
        adj_list_.print_with_data_map(os, data_map_);
    }

    void print_adjacency_matrix() const
    {
        const size_t dim = data_map_.size();
        std::vector<id_type> nodes;
        for (auto& pair : data_map_) {
            nodes.push_back(pair.first);
        }
 
#ifndef NDEBUG
        std::cout << "Dimension: " << dim << "\n";
        std::cout << "Nodes: ";
        for (auto& node : nodes) {
            std::cout << node << " ";
        }
        std::cout << "\n";
#endif
 
        // Header
        std::cout << "Adjacency Matrix: \n  | ";
        for (auto& node : nodes) {
            std::cout << node << "   ";
        }
        std::cout << "\n";
        for (size_t idx {}; idx < dim; idx++) {
            std::cout << "----";
        }
        std::cout << "--\n";
 
        // Content
        for (auto& base_node : nodes) {
            std::cout << base_node << " | ";
            for (auto& node : nodes) {
                if (adj_list_.has_edge(base_node, node)) {
                    if constexpr (valid_weighted_edge_type<edge_type, id_type>)
                        std::cout << adj_list_.get_edge(base_node, node).weight;
                    else
                        std::cout << "X";
                } else
                    std::cout << ".";
                std::cout << "   ";
            }
            std::cout << "\n  |\n";
        }
    }
 
    //
    // State Mutation
    //

    id_type add_node(const data_type data)
    {
        id_type id;
        if (is_full()) {
            throw std::overflow_error("The Graph is full, no new nodes can be added");
        }
        // One of those should always work, don't need to
        // check for numeric_limits in else clause again.
        if (!reusable_ids_.empty()) {
            id = reusable_ids_.front();
            reusable_ids_.pop();
        } else {
            // We lose the ID 0 here, that is intended to avoid a
            // mismatch between max ID and ID count.
            auto insertion_id = highest_id_ + 1;
            while (data_map_.count(insertion_id))
                ++insertion_id;
            id = insertion_id;
            highest_id_ = insertion_id;
        }
        const auto [it, inserted] = data_map_.insert({id, data});
        if (!inserted) {
            throw std::runtime_error("Insertion failed: key might already exist");
        }
        adj_list_.add_node_id(id);
#ifndef NDEBUG
        if (is_full()) {
            std::cout << "Graph is FULL now. We can't add a new node\n";
        }
#endif
        return id;
    }

    id_type add_node()
    {
        add_node(data_type {});
    }

    void add_node_with_id(const id_type id, const data_type data)
    {
        if (is_full())
            throw std::overflow_error("The Graph is full, no new nodes can be added");
        else if (node_exists(id))
            throw std::runtime_error("Cannot insert: the given ID already exists");
 
        const auto [it, inserted] = data_map_.insert({id, data});
        if (!inserted) {
            throw std::runtime_error("Insertion failed");
        }
        adj_list_.add_node_id(id);
    }

    void add_node_with_id(const id_type id)
    {
        add_node_with_id(id, data_type {});
    }

    void remove_node(const id_type id)
    {
        if (!node_exists(id)) {
            throw std::invalid_argument("Node with this ID does not exist");
        }
        adj_list_.remove_node_id(id);
        reusable_ids_.push(id);
        data_map_.erase(id);
    }

    void set_node_data(const id_type id, const data_type data)
    {
        if (!node_exists(id)) {
            throw std::invalid_argument("Node does not exist");
        }
        data_map_.at(id) = data;
    }

    virtual void add_edge(const id_type from_id, const id_type to_id) = 0;

    virtual void remove_edge(const id_type from_id, const id_type to_id) = 0;
 
protected:
    AdjacencyList<id_type, edge_type> adj_list_ {};      
    std::unordered_map<id_type, data_type> data_map_ {}; 
    id_type highest_id_ {};                              
    friend std::ostream& operator<< <data_type, id_type, edge_type>(
        std::ostream& os,
        const Graph<data_type, id_type, edge_type>& graph); 

    virtual void add_edge_impl(const id_type from_id, const edge_type edge)
    {
        if (!node_exists(from_id)) {
            throw std::invalid_argument("Node with origin ID does not exist");
        }
        if (!node_exists(edge.node_id)) {
            throw std::invalid_argument("Node with target ID to_id does not exist");
        }
        if (adj_list_.has_edge(from_id, edge.node_id)) {
            throw std::invalid_argument("An edge from origin ID to target ID already exists");
        }
 
        adj_list_.add_edge(from_id, edge);
 
        if (!is_directed() && from_id != edge.node_id) {
            auto reverse_edge = edge;
            reverse_edge.node_id = from_id;
            adj_list_.add_edge(edge.node_id, reverse_edge);
        }
    }
 
private:
    std::queue<id_type> reusable_ids_ {}; 
};

template <valid_data_type D, valid_id_type I, valid_edge_type<I> E>
std::ostream& operator<<(std::ostream& os, const Graph<D, I, E>& graph)
{
    os << graph.adj_list_;
    return os;
}
 
} // namespace GraphLib::Internal
 
#endif