graph.h

Go to the documentation of this file.

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025  Medusa Slockbower
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <https://www.gnu.org/licenses/>.
// =====================================================================================================================
 
 
#ifndef FENNEC_CONTAINERS_GRAPH_H
#define FENNEC_CONTAINERS_GRAPH_H
 
#include <fennec/containers/dynarray.h>
#include <fennec/containers/list.h>
#include <fennec/containers/map.h>
#include <fennec/containers/object_pool.h>
#include <fennec/containers/set.h>
 
/*
 * With the directed tree we were able to cheat a little, the structure has more rules to it which allows
 * tighter constraints. A graph is basically no rules whatsoever. Some variants, such as weighted graphs, assign
 * properties or rules to edges which can simply be an extension to this graph.
 *
 * The most effective way to do this is to have a dynarray of lists, however this results in double the
 * memory being used. This can also result in two edge objects being created.
 *
 * There is no nice way to avoid the problem of mapping vertices to edges
 */
 
namespace fennec
{
 
template<typename VertexT, typename EdgeT = empty_t>
struct graph {
public:
// Definitions =========================================================================================================
 
    using edge_t        = EdgeT;                         
    using vertex_t      = VertexT;                       
    using vertex_pool_t = object_pool<vertex_t>;         
    using edge_map_t    = dynarray<map<size_t, size_t>>; 
    using edge_pool_t   = object_pool<edge_t>;           
 
    static constexpr size_t npos = -1; 
 
 
// Constructors ========================================================================================================
 
 
    constexpr graph() = default;
 
    constexpr ~graph() = default;
 
 
 
 
    constexpr graph& operator=(const graph& g) = default;
 
    constexpr graph& operator=(graph&& g) = default;
 
 
 
// Properties ==========================================================================================================
 
 
    constexpr size_t num_vertices() const {
        return _vertex_pool.size();
    }
 
    constexpr size_t num_edges() const {
        return _edge_pool.size();
    }
 
    constexpr size_t capacity() const {
        return _vertex_pool.capacity();
    }
 
    constexpr bool empty() const {
        return num_vertices() == 0;
    }
 
    constexpr bool exists(size_t a, size_t b) const {
        return _edge_map[a][b] != nullptr;
    }
 
    constexpr bool is_symmetric(size_t a, size_t b) const {
        return exists(a, b) and exists(b, a);
    }
 
    constexpr bool is_undirected(size_t a, size_t b) const {
        const auto* e0 = _edge_map[a][b];
        const auto* e1 = _edge_map[b][a];
        if (not (e0 != nullptr && e1 != nullptr)) {
            return false;
        }
        return *e0 == *e1;
    }
 
    // TODO: connected, disjoint, unilateral, get_component
 
 
 
// Access ==============================================================================================================
 
 
    constexpr vertex_t& operator[](size_t vertex) {
        return _vertex_pool[vertex];
    }
 
    constexpr const vertex_t& operator[](size_t vertex) const {
        return _vertex_pool[vertex];
    }
 
    constexpr edge_t* operator[](size_t a, size_t b) {
        if (empty()) {
            return nullptr;
        }
        edge_t* it = _edge_map[a][b];
        if (it) {
            return _edge_pool[*it];
        }
        return nullptr;
    }
 
    constexpr const edge_t* operator[](size_t a, size_t b) const {
        if (empty()) {
            return nullptr;
        }
        const edge_t* it = _edge_map[a][b];
        if (it) {
            return _edge_pool[*it];
        }
        return nullptr;
    }
 
    list<size_t> outgoing(size_t vertex) {
        list<size_t> res;
        if (empty() || vertex >= _edge_map.size()) {
            return res;
        }
        for (const auto& it : _edge_map[vertex]) {
            res.push_back(it.first);
        }
        return res;
    }
 
    list<size_t> incoming(size_t vertex) {
        list<size_t> res;
        if (empty() || vertex >= _edge_map.size()) {
            return res;
        }
        for (size_t n = 0; n < _edge_map.size(); ++n) {
            if (_edge_map[n][vertex]) {
                res.push_back(n);
            }
        }
        return res;
    }
 
    list<size_t> symmetric(size_t vertex) {
        list<size_t> res;
        if (empty() || vertex >= _edge_map.size()) {
            return res;
        }
        for (const auto& it : _edge_map[vertex]) {
            if (_edge_map[it.first][vertex]) {
                res.push_back(it.first);
            }
        }
        return res;
    }
 
    list<size_t> undirected(size_t vertex) {
        list<size_t> res;
        if (empty() || vertex >= _edge_map.size()) {
            return res;
        }
        for (const auto& it : _edge_map[vertex]) {
            const auto* at = _edge_map[it.first][vertex];
            if (at != nullptr && *at == it.second) {
                res.push_back(it.first);
            }
        }
        return res;
    }
 
    const auto* edges(size_t vertex) {
        if (empty() || vertex >= _edge_map.size()) {
            return nullptr;
        }
        return &_edge_map[vertex];
    }
 
 
 
// Modifiers ===========================================================================================================
 
 
    constexpr size_t insert(vertex_t&& vertex) {
        return this->_insert(fennec::forward<vertex_t>(vertex));
    }
 
    constexpr size_t insert(const vertex_t& vertex) {
        return this->_insert(vertex);
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace(ArgsT&&...args) {
        return this->_insert(fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void erase(size_t vertex) {
        cut(vertex);
        _vertex_pool.erase(vertex);
    }
 
    template<typename...ArgsT>
    constexpr void make_edge(size_t a, size_t b, ArgsT&&...args) {
        if (a == b) {
            return;
        }
 
        if (_edge_map.size() < _vertex_pool.capacity()) {
            _edge_map.resize(_vertex_pool.capacity());
        }
 
        auto it = _edge_map[a][b];
        size_t conn;
        if (it != nullptr) {
            conn = *it;
            _edge_pool[conn] = vertex_t(fennec::forward<ArgsT>(args)...);
        } else {
            conn = _edge_pool.emplace(fennec::forward<ArgsT>(args)...);
        }
        _edge_map[a].emplace(b, conn);
    }
 
    template<typename...ArgsT>
    constexpr void make_edge2(size_t a, size_t b, ArgsT&&...args) {
        if (a == b) {
            return;
        }
 
        if (_edge_map.size() < _vertex_pool.capacity()) {
            _edge_map.resize(_vertex_pool.capacity());
        }
 
        auto it = _edge_map[a][b];
        size_t conn;
        if (it != nullptr) {
            conn = *it;
            _edge_pool[conn] = vertex_t(fennec::forward<ArgsT>(args)...);
        } else {
            conn = _edge_pool.emplace(fennec::forward<ArgsT>(args)...);
        }
 
        _edge_map[a].emplace(b, conn);
        _edge_map[b].emplace(a, conn);
    }
 
    constexpr void cut_edge(size_t a, size_t b) {
 
        // Find the edge object
        const auto* it = _edge_map[a][b];
        if (not it) {
            return;
        }
        size_t    c = *it;
 
        // Check if undirected
        const auto* at = _edge_map[b][a];
        if (not at || *at != c) {
            _edge_pool.erase(c);
        }
 
        // Erase the edge mapping
        _edge_map[a].erase(b);
    }
 
    constexpr void cut_edge2(size_t a, size_t b) {
        const auto* ita = _edge_map[a][b];
        const auto* itb = _edge_map[a][b];
        if (not (ita || itb)) {
            return;
        }
        if (ita) _edge_pool.erase(*ita);
        if (itb) _edge_pool.erase(*itb);
        _edge_map[a].erase(b);
        _edge_map[b].erase(a);
    }
 
    void cut(size_t n) {
        for (const auto it : outgoing(n)) {
            cut_edge(n, it);
        }
        for (const auto it : incoming(n)) {
            cut_edge(it, n);
        }
    }
 
    void clear() {
        _vertex_pool.clear();
        _edge_pool.clear();
        _edge_map.clear();
    }
 
 
 
// edges =========================================================================================================
 
 
private:
    vertex_pool_t _vertex_pool;
    edge_pool_t   _edge_pool;
    edge_map_t    _edge_map;
 
    template<typename...ArgsT>
    size_t _insert(ArgsT&&...args) {
        return _vertex_pool.emplace(fennec::forward<ArgsT>(args)...);
    }
 
};
 
}
 
#endif // FENNEC_CONTAINERS_GRAPH_H