/*
 *    ╔═╗╦═╗╔═╗╔═╗╦ ╦  C++ Graph library
 *    ║ ╦╠╦╝╠═╣╠═╝╠═╣  Version 1.2.0
 *    ╚═╝╩╚═╩ ╩╩  ╩ ╩  https://github.com/Terae/Graph
 *
 *
 * Single header-file generated by lumen on 2025-09-05
 *
 *
 * Licensed under the MIT License <https://opensource.org/licenses/MIT>.
 * Copyright (c) 2017 Benjamin BIGEY
 *
 * Permission is hereby  granted, free of charge, to any  person obtaining a copy
 * of this software and associated  documentation files (the "Software"), to deal
 * in the Software  without restriction, including without  limitation the rights
 * to  use, copy,  modify, merge,  publish, distribute,  sublicense, and/or  sell
 * copies  of the Software,  and  to  permit persons  to  wholm  the Software  is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE  IS PROVIDED "AS  IS", WITHOUT WARRANTY  OF ANY KIND,  EXPRESS OR
 * IMPLIED,  INCLUDING BUT  NOT  LIMITED TO  THE  WARRANTIES OF  MERCHANTABILITY,
 * FITNESS FOR  A PARTICULAR PURPOSE AND  NONINFRINGEMENT. IN NO EVENT  SHALL THE
 * AUTHORS  OR COPYRIGHT  HOLDERS  BE  LIABLE FOR  ANY  CLAIM,  DAMAGES OR  OTHER
 * LIABILITY, WHETHER IN AN ACTION OF  CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE  OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#ifndef ROOT_GRAPH_FINAL_H
#define ROOT_GRAPH_FINAL_H

#include <fstream>
#include <iomanip>
#include <map>
#include <queue>
#include <vector>

#ifdef INCLUDE_JSON_FILE
    #include "../third-party/json/single_include/nlohmann/json.hpp"
#else
    #include <nlohmann/json.hpp>
#endif

// C++ language standard detection
#if (defined(__cplusplus) && __cplusplus >= 202302L) || \
    (defined(_MSVC_LANG) && _MSVC_LANG >= 202302L)
    #define GRAPH_HAS_CPP_23
    #define GRAPH_HAS_CPP_20
    #define GRAPH_HAS_CPP_17
    #define GRAPH_HAS_CPP_14
#elif (defined(__cplusplus) && __cplusplus >= 202002L) || \
    (defined(_MSVC_LANG) && _MSVC_LANG >= 202002L)
    #define GRAPH_HAS_CPP_20
    #define GRAPH_HAS_CPP_17
    #define GRAPH_HAS_CPP_14
#elif (defined(__cplusplus) && __cplusplus >= 201703L) || \
    (defined(_MSC_VER) && _MSC_VER > 1900 && defined(_HAS_CXX17) && _HAS_CXX17 == 1)
    #define GRAPH_HAS_CPP_17
    #define GRAPH_HAS_CPP_14
#elif (defined(__cplusplus) && __cplusplus >= 201402L) || \
    (defined(_HAS_CXX14) && _HAS_CXX14 == 1)
    #define GRAPH_HAS_CPP_14
#endif

// Include optional for C++17 and later
#if defined(GRAPH_HAS_CPP_17)
    #include <optional>
#endif

// Include concepts for C++20 and later
#if defined(GRAPH_HAS_CPP_20)
#include <concepts>

template<typename T>
concept GraphKey = std::copyable<T> && std::equality_comparable<T> && std::totally_ordered<T>;

template<typename T>
concept GraphData = std::copyable<T>;

template<typename T>
concept GraphCost = std::copyable<T> && std::equality_comparable<T> && std::totally_ordered<T> && requires(T t) {
    t + t;
    t - t;
    t * t;
    t / t;
};
#endif

#if defined(__clang__)
    #if (__clang_major__ * 10000 + __clang_minor__ * 100 + __clang_patchlevel__) < 30500
        #error "unsupported Clang version - see https://github.com/terae/structure#supported-compilers"
    #endif
#elif defined(__GNUC__) && !(defined(__ICC) || defined(__INTEL_COMPILER))
    #if (__GNUC__        * 10000 + __GNUC_MINOR__  * 100 + __GNUC_PATCHLEVEL__)  < 50000
        #error "unsupported GCC version - see https://github.com/terae/structure#supported-compilers"
    #endif
#endif

#include <iostream>
#include <list>
#include <memory>
#include <tuple>
#include <utility>

#include <memory>
#include <string>
#include <istream>

/// allow to disable exceptions
#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)) && not defined(GRAPH_NOEXCEPTION)
    #define GRAPH_THROW(exception_name) throw detail::exception_name::create(__FUNCTION__);
    #if defined(__clang__)
        #define GRAPH_THROW_WITH(exception_name, ...) throw detail::exception_name::create(__FUNCTION__, __VA_ARGS__);
    #elif defined(__GNUC__)
        #define GRAPH_THROW_WITH(exception_name, ...) throw detail::exception_name::create(__FUNCTION__, ##__VA_ARGS__);
    #endif
    #define GRAPH_TRY try
    #define GRAPH_CATCH(exception) catch(exception)
#else
    #define GRAPH_THROW(exception) std::abort()
    #define GRAPH_TRY if (true)
    #define GRAPH_CATCH(exception) if (false)
#endif

#include <functional>
#include <limits>
#include <sstream>

/**
 * @brief Enumeration representing the nature of a graph
 *
 * Defines whether a graph is directed or undirected, which affects
 * how edges are handled and how certain algorithms behave.
 */
enum Nature {
    DIRECTED   = 'd',
    UNDIRECTED = 'u'
};

namespace detail {

    struct exception : std::exception {
        /// returns the explanatory string
        [[nodiscard]] const char* what() const noexcept override {
            return m.what();
        }

      protected:
        explicit exception(const char* what_arg) : m(what_arg) {}

        static std::string name(const std::string &exception_type) {
            return "[graph.exception." + exception_type + "] ";
        }

      private:
        std::logic_error m;
    };

    struct invalid_argument final : exception {

        static invalid_argument create(const std::string &function_name,
                                       const std::string &what_arg = "Invalid argument") {
            const std::string w{exception::name("invalid_argument") + what_arg + " when calling '" + function_name + "'."};
            return invalid_argument(w.c_str());
        }

      private:
        explicit invalid_argument(const char* what_arg) : exception(what_arg) {}
    };

    struct unexpected_nullptr final : exception {

        static unexpected_nullptr create(const std::string &function_name,
                                         const std::string &what_arg = "Unexpected nullptr") {
            const std::string w{exception::name("unexpected_nullptr") + what_arg + " when calling '" + function_name + "'."};
            return unexpected_nullptr(w.c_str());
        }

      private:
        explicit unexpected_nullptr(const char* what_arg) : exception(what_arg) {}
    };

    struct parse_error final : exception {

        static parse_error create(const std::string &function_name,
                                  const std::size_t byte,
                                  const std::string &what_arg = "Bad format") {
            const std::string w{exception::name("parse_error") + "parse error"
                                + (byte != 0 ? " at " + std::to_string(byte) : "")
                                + ": " + what_arg + " when calling '" + function_name + "'."};
            return parse_error(w.c_str(), byte);
        }

        const std::size_t byte;

      private:
        explicit parse_error(const char* what_arg, std::size_t b) : exception(what_arg), byte(b) {}
    };

    struct bad_graph : exception {
      protected:
        explicit bad_graph(const char* what_arg) : exception(what_arg) {}

        static std::string name(const std::string &exception_type) {
            return "[graph.exception.bad_graph." + exception_type + "] ";
        }
    };

    struct negative_edge final : bad_graph {

        static negative_edge create(const std::string &function_name,
                                    const std::string &what_arg = "Edge with negative weight") {
            const std::string w{bad_graph::name("negative_edge") + what_arg + " when calling '" + function_name + "'."};
            return negative_edge(w.c_str());
        }

      private:
        explicit negative_edge(const char* what_arg) : bad_graph(what_arg) {}
    };

    struct negative_weight_cycle final : bad_graph {

        static negative_weight_cycle create(const std::string &function_name,
                                            const std::string &what_arg = "Negative-weight cycle") {
            const std::string w{bad_graph::name("negative_weight_cycle") + what_arg + " when calling '" + function_name + "'."};
            return negative_weight_cycle(w.c_str());
        }

      private:
        explicit negative_weight_cycle(const char* what_arg) : bad_graph(what_arg) {}
    };

    struct not_complete final : bad_graph {

        static not_complete create(const std::string &function_name,
                                   const std::string &what_arg = "Not complete graph") {
            const std::string w{bad_graph::name("not_complete") + what_arg + " when calling '" + function_name + "'."};
            return not_complete(w.c_str());
        }

      private:
        explicit not_complete(const char* what_arg) : bad_graph(what_arg) {}
    };

    struct has_cycle final : bad_graph {

        static has_cycle create(const std::string &function_name,
                                const std::string &what_arg = "Graph with a cycle") {
            const std::string w{bad_graph::name("has_cycle") + what_arg + " when calling '" + function_name + "'."};
            return has_cycle(w.c_str());
        }

      private:
        explicit has_cycle(const char* what_arg) : bad_graph(what_arg) {}
    };

    /// SECTION degree

    template <Nature> class basic_degree;

    template <> class basic_degree<DIRECTED> {
      public:
        using value_type = std::pair<std::size_t, std::size_t>;
        using type = basic_degree<DIRECTED>;

        explicit basic_degree(value_type degree) : _deg(std::move(degree)) {};
        basic_degree(std::size_t in, std::size_t out) : basic_degree(std::make_pair(in, out)) {};

        [[nodiscard]] value_type get_degree() const {
            return _deg;
        }

        friend bool operator==(const type &t1, const type &t2) {
            return t1._deg == t2._deg;
        }
        friend bool operator==(const value_type &v, const type &t) {
            return t._deg == v;
        }
        friend bool operator==(const type &t, const value_type &v) {
            return t._deg == v;
        }

        friend bool operator< (const type &t1, const type &t2) {
            return t1._deg < t2._deg;
        }

        static basic_degree max() {
            return {std::numeric_limits<std::size_t>::max(), std::numeric_limits<std::size_t>::max()};
        }
        static basic_degree min() {
            return {std::numeric_limits<std::size_t>::min(), std::numeric_limits<std::size_t>::min()};
        }

      private:
        value_type _deg;
    };

    template <> class basic_degree<UNDIRECTED> {
      public:
        using value_type = std::size_t;
        using type = basic_degree<UNDIRECTED>;

        explicit basic_degree(const value_type &d) : _deg(d) {}
        basic_degree(const std::size_t in, const std::size_t out) : basic_degree(std::max(in, out)) {}

        [[nodiscard]] value_type get_degree() const {
            return _deg;
        }

        friend bool operator==(const type &t1, const type &t2) {
            return t1._deg == t2._deg;
        }
        friend bool operator==(const value_type &v, const type &t) {
            return t._deg == v;
        }
        friend bool operator==(const type &t, const value_type &v) {
            return t._deg == v;
        }

        friend bool operator< (const type &t1, const type &t2) {
            return t1._deg < t2._deg;
        }

        static basic_degree max() {
            return basic_degree(std::numeric_limits<std::size_t>::max());
        }
        static basic_degree min() {
            return basic_degree(std::numeric_limits<std::size_t>::min());
        }

      private:
        value_type _deg;
    };

    /// SECTION helpers

    template <Nature> struct is_directed           : std::false_type { };
    template <>       struct is_directed<DIRECTED> : std::true_type  { };

    template <Nature> struct is_undirected             : std::false_type { };
    template <>       struct is_undirected<UNDIRECTED> : std::true_type  { };

#include <utility>

    /// distinguish value type between map::iterator and shared_ptr: @see https://stackoverflow.com/a/31409532
    template <typename... >
    using void_t = void;

    template <typename T, typename = void>
    struct is_map_iterator : std::false_type { };

    template <typename T>
    struct is_map_iterator<T,
            void_t<decltype(++std::declval<T&>()),
                   decltype(*std::declval<T&>()),
                   decltype(std::declval<T&>() == std::declval<T&>()),
                   decltype((*std::declval<T&>()).second)> >
            : std::true_type { };

    template <class V, class = typename std::enable_if<is_map_iterator<V>::value>::type>
    typename std::iterator_traits<V>::value_type::second_type get_value(const V &v, const V &end) {
        if (v == end) {
            return static_cast<typename std::iterator_traits<V>::value_type::second_type>(nullptr);
        }
        return (*v).second;
    }

#include <cxxabi.h>

    /// @return the human-readable name of @tparam T

    template <class T>
    std::string type_name() {
        int status;
        std::string type_name{typeid(T).name()};
        char* demangled_name{abi::__cxa_demangle(type_name.c_str(), nullptr, nullptr, &status)};

        if (status == 0) {
            type_name = demangled_name;
        }
        std::free(demangled_name);

        const std::function<void(std::string &, std::string, std::string)> replace_all =
        [](std::string & base, const std::string & to_replace, const std::string & replacement) {
            for (std::string::size_type i{0}; (i = base.find(to_replace, i)) != std::string::npos; ) {
                base.replace(i, to_replace.length(), replacement);
                i += replacement.length();
            }
        };

        replace_all(type_name, "std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >", "std::string>");
        replace_all(type_name, "std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >",   "std::string");
        return type_name;
    }

    template <class T>
    std::istream &read_T(std::istream &is, T &t) {
        is.ignore(std::numeric_limits<std::streamsize>::max(), '"');

        std::string str;
        std::getline(is, str, '"');
        std::stringstream ss;
        ss << str;
        if (!(ss >> t)) {
            GRAPH_THROW_WITH(parse_error, 5, "Bad type");
        }

        return is;
    }
    template<> inline
    std::istream &read_T<std::string>(std::istream &is, std::string &str) {
        is.ignore(std::numeric_limits<std::streamsize>::max(), '"');
        std::getline(is, str, '"');
        return is;
    }

    template <class C>
    std::istream &read_cost(std::istream &is, C &c) {
        const auto str = std::string(std::istreambuf_iterator<char>(is),
                                     std::istreambuf_iterator<char>());
        if (str.find_first_of('"') == std::string::npos &&
                str.find_first_of("infinity") != std::string::npos)
            c = std::numeric_limits<C>::has_infinity ? std::numeric_limits<C>::infinity() :
                std::numeric_limits<C>::max();
        else {
            std::stringstream ss;
            ss << str;
            read_T(ss, c);
        }
        return is;
    }
}

// C++11 compatibility for make_unique
#if !defined(GRAPH_HAS_CPP_14)
namespace std {
    template<typename T, typename... Args>
    std::unique_ptr<T> make_unique(Args&&... args) {
        return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
    }
}
#endif

/**
 * @brief Base class for nodes in a graph
 *
 * This class represents a node in a graph, containing data and connections
 * to other nodes (edges). It is designed to work with the graph class
 * to provide a complete graph data structure.
 *
 * @tparam Data Type of data stored in the node
 * @tparam Cost Type of cost associated with edges
 * @tparam Container Type of container for iterators
 * @tparam constContainer Type of container for const iterators
 */
template <class Data, class Cost, class Container, class constContainer>
class basic_node {
  public:
    /**
     * @brief Represents an edge in the graph
     *
     * An edge connects two nodes and has an associated cost.
     */
    class edge {
        template <class T, class C, class c1, class c2> friend class basic_node;
        template <class K, class T, class C, Nature N> friend class graph;

        std::weak_ptr<basic_node<Data, Cost, Container, constContainer >> _target;
        std::shared_ptr<Cost> _cost;

        /**
         * @brief Create a tuple representation of the edge for comparison
         * @return Tuple containing cost and target node
         */
        std::tuple<Cost, basic_node<Data, Cost, Container, constContainer >> tie() const;

      public:
        /**
         * @brief Construct a new edge object
         * @param ptr Shared pointer to the target node
         * @param cost Cost of the edge
         */
        explicit edge(const std::weak_ptr<basic_node<Data, Cost, Container, constContainer >> &ptr, Cost cost);

        /**
         * @brief Copy constructor
         * @param other Edge to copy
         */
        edge(const edge& other);

        /**
         * @brief Compare edges by cost
         * @param other Edge to compare with
         * @return true if this edge has lower cost than other
         */
        bool operator<(const edge& other) const;

        /**
         * @brief Check equality of edges
         * @param other Edge to compare with
         * @return true if edges are equal
         */
        bool operator==(const edge& other) const;

        /**
         * @brief Get the target node of this edge
         * @return constContainer pointing to the target node
         */
        constContainer target() const;

        /**
         * @brief Get the cost of this edge
         * @return Reference to the cost value
         */
        Cost& cost() const;
    };

    using ListEdges = std::list<edge>;
    using EdgesIterator = typename ListEdges::iterator;
    using ConstEdgesIterator = typename ListEdges::const_iterator;

  private:
    template <class K, class T, class C, Nature N> friend class graph;

    ListEdges _out_edges;

    const Cost infinity = std::numeric_limits<Cost>::has_infinity ? std::numeric_limits<Cost>::infinity() :
                          std::numeric_limits<Cost>::max();

    std::size_t _in_degree{0};

    void increment_in_degree(int n = 1);
    void decrement_in_degree(int n = 1);

    /// used for UNDIRECTED graphs: same Cost in memory for both directions
    bool set_edge(constContainer other, std::shared_ptr<Cost> cost);

    std::tuple<Data, std::size_t, ListEdges> tie() const;

    ListEdges get_edges() const;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator==(const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator!=(const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator< (const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator<=(const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator> (const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    template <class T, class C, class X, class Y>
    friend constexpr bool operator>=(const basic_node<T, C, X, Y> &n1, const basic_node<T, C, X, Y> &n2) noexcept;

    basic_node(const basic_node &n);

    basic_node &operator=(const basic_node &n);

  protected:
    Data _data;

    Container      container_from_this;
    Container      end_container;
    constContainer cend_container;

  public:

    /// @section exceptions

    using exception          = detail::exception;
    using invalid_argument   = detail::invalid_argument;
    using unexpected_nullptr = detail::unexpected_nullptr;

    /**
     * @brief Default constructor
     */
    explicit basic_node();

    /**
     * @brief Construct with data
     * @param data Data to store in the node
     */
    explicit basic_node(const Data& data);

    /**
     * @brief Move assignment operator (deleted)
     */
    basic_node &operator=(basic_node&& n) = delete;

    /**
     * @brief Destructor
     */
    ~basic_node();

    /**
     * @brief Get reference to node data
     * @return Reference to stored data
     */
    Data &get();

    /**
     * @brief Get copy of node data (const version)
     * @return Copy of stored data
     */
    Data get() const;

    /**
     * @brief Get reference to edge cost
     * @param other Iterator to target node
     * @return Reference to edge cost
     */
    Cost &get_cost(Container other);

    /**
     * @brief Get copy of edge cost (const version)
     * @param other Const iterator to target node
     * @return Copy of edge cost
     */
    Cost get_cost(constContainer other) const;

    /**
     * @brief Access edge cost with operator[]
     * @param other Iterator to target node
     * @return Reference to edge cost
     */
    Cost &operator[](Container other);

    /**
     * @brief Access edge cost with operator[] (const version)
     * @param other Const iterator to target node
     * @return Copy of edge cost
     */
    Cost operator[](constContainer other) const;

    /**
     * @brief Set node data
     * @tparam T_data Type of data to set
     * @param data Data to set
     */
    template<class T_data>
    void set(const T_data& data);

    /**
     * @brief Set edge cost
     * @tparam T_cost Type of cost to set
     * @param other Iterator to target node
     * @param cost Cost to set
     */
    template<class T_cost>
    void set_cost(Container other, const T_cost& cost);

    /**
     * @brief Add an edge to another node
     * @param other Const iterator to target node
     * @param cost Cost of the edge (default: 1)
     * @return Pair containing iterator to edge and boolean indicating if new edge was created
     */
    std::pair<EdgesIterator, bool> add_edge(constContainer other, Cost cost = Cost(1)) {
        std::shared_ptr<basic_node<Data, Cost, Container, constContainer >> ptr{
            detail::get_value(other, cend_container)
        };

        if (ptr == nullptr) {
            GRAPH_THROW(unexpected_nullptr)
        }

        for (EdgesIterator it{_out_edges.begin()}; it != _out_edges.end(); ++it) {
            if (it->_target.lock() == ptr) {
                it->cost() = cost;
                return std::make_pair(it, false);
            }
        }

        // Link doesn't exist
        ptr->increment_in_degree();
        _out_edges.emplace_back(
            std::weak_ptr<basic_node<Data, Cost, Container, constContainer >> (ptr),
            cost
        );
        std::pair<EdgesIterator, bool> result{std::make_pair(--_out_edges.end(), true)};
        return result;
    }

    /**
     * @brief Delete an edge to another node
     * @param other Const iterator to target node
     * @return true if edge was deleted, false otherwise
     */
    bool del_edge(constContainer other);

    /**
     * @brief Delete an edge based on a predicate
     * @param other Const iterator to target node
     * @param predicate Function to determine if edge should be deleted
     * @return true if edge was deleted, false otherwise
     */
    bool del_edge_if(constContainer other, std::function<bool(const edge &)> predicate);

    /**
     * @brief Clear all edges from this node
     * @return Number of edges cleared
     */
    std::size_t clear_edges();

    /**
     * @brief Get the degree of this node
     * @return Pair containing in-degree and out-degree
     */
    [[nodiscard]] std::pair<std::size_t, std::size_t> degree() const;

    /**
     * @brief Check if an adjacent node exists
     * @param other Iterator to potential adjacent node
     * @return true if adjacent node exists, false otherwise
     */
    [[nodiscard]] bool existing_adjacent_node(constContainer other) const;

};

/**
 * @brief A generalized class of Graph
 *
 * This class implements a graph data structure that can be either directed
 * or undirected. It supports various operations including node and edge
 * manipulation, graph traversal algorithms, and serialization.
 *
 * The graph is implemented as an adjacency list where each node contains
 * a list of its adjacent nodes and the cost of the connecting edges.
 *
 * @tparam Key Type of the keys. Each element in a Graph is uniquely identified
 *             by its key value. Aliased as member type Graph::key_type
 * @tparam T Type of graphed value stored into a node.
 *           Aliased as member type Graph::graphed_type
 * @tparam Cost Type of the cost between nodes. Default is std::size_t
 * @tparam Nat Nature of the graph (DIRECTED or UNDIRECTED). Default is UNDIRECTED
 *
 * @since version 1.0.0
 */
template <class Key, class T, class Cost = std::size_t, Nature Nat = UNDIRECTED>
class graph {
  public:
    class node;
    using Degree = detail::basic_degree<Nat>;
    class search_path;
    class shortest_paths;

  private:
    using PtrNode  = std::shared_ptr<node>;
    using MapNodes = std::map<Key, PtrNode>;

    MapNodes _nodes;
    std::size_t _num_edges = 0;

    const Cost infinity = std::numeric_limits<cost_type>::has_infinity ? std::numeric_limits<Cost>::infinity() :
                          std::numeric_limits<Cost>::max();
    class path_comparator;
    struct iterator_comparator;

  public:

    /// @section exceptions

    using bad_graph          = detail::bad_graph;
    using exception          = detail::exception;
    using invalid_argument   = detail::invalid_argument;
    using negative_edge      = detail::negative_edge;
    using not_complete       = detail::not_complete;
    using parse_error        = detail::parse_error;
    using unexpected_nullptr = detail::unexpected_nullptr;

    /// @section container types

    // Concept validation for better error messages in C++20+
#if defined(GRAPH_HAS_CPP_20)
    static_assert(GraphKey<Key>, "Key type must satisfy GraphKey concept (copyable, equality_comparable, and totally_ordered)");
    static_assert(GraphData<T>, "T type must satisfy GraphData concept (copyable)");
    static_assert(GraphCost<Cost>, "Cost type must satisfy GraphCost concept (copyable, equality_comparable, totally_ordered, and supports arithmetic operations)");
#endif

    using value_type   = std::pair<const Key, PtrNode>;

    using reference    = value_type &;

    using key_type     = Key;

    using graphed_type = T;

    using cost_type    = Cost;

    using size_type    = std::size_t;

    using iterator               = typename MapNodes::iterator;

    using const_iterator         = typename MapNodes::const_iterator;

    using reverse_iterator       = typename MapNodes::reverse_iterator;

    using const_reverse_iterator = typename MapNodes::const_reverse_iterator;

    /**
     * @brief Returns an iterator to the first element of the graph
     * @return Iterator to the first element
     */
    iterator begin() noexcept;

    /**
     * @brief Returns an iterator to the element following the last element of the graph
     * @return Iterator to the element following the last element
     */
    iterator end() noexcept;

    /**
     * @brief Returns a const iterator to the first element of the graph
     * @return Const iterator to the first element
     */
    const_iterator begin() const noexcept;

    /**
     * @brief Returns a const iterator to the first element of the graph
     * @return Const iterator to the first element
     */
    const_iterator cbegin() const noexcept;

    /**
     * @brief Returns a const iterator to the element following the last element of the graph
     * @return Const iterator to the element following the last element
     */
    const_iterator end() const noexcept;

    /**
     * @brief Returns a const iterator to the element following the last element of the graph
     * @return Const iterator to the element following the last element
     */
    const_iterator cend() const noexcept;

    /**
     * @brief Returns a reverse iterator to the first element of the reversed graph
     * @return Reverse iterator to the first element
     */
    reverse_iterator rbegin() noexcept;

    /**
     * @brief Returns a reverse iterator to the element following the last element of the reversed graph
     * @return Reverse iterator to the element following the last element
     */
    reverse_iterator rend() noexcept;

    /**
     * @brief Returns a const reverse iterator to the first element of the reversed graph
     * @return Const reverse iterator to the first element
     */
    const_reverse_iterator rbegin() const noexcept;

    /**
     * @brief Returns a const reverse iterator to the first element of the reversed graph
     * @return Const reverse iterator to the first element
     */
    const_reverse_iterator crbegin() const noexcept;

    /**
     * @brief Returns a const reverse iterator to the element following the last element of the reversed graph
     * @return Const reverse iterator to the element following the last element
     */
    const_reverse_iterator rend() const noexcept;

    /**
     * @brief Returns a const reverse iterator to the element following the last element of the reversed graph
     * @return Const reverse iterator to the element following the last element
     */
    const_reverse_iterator crend() const noexcept;

    /**
     * @brief Default constructor
     *
     * Creates an empty graph with no nodes or edges.
     */
    explicit graph();

    /**
     * @brief Construct a graph from an input stream
     *
     * Creates a graph by parsing data from the provided input stream.
     *
     * @param is Input stream containing graph data
     */
    explicit graph(std::istream& is);

    /**
     * @brief Copy constructor
     *
     * Creates a new graph as a copy of an existing graph.
     *
     * @param other Graph to copy
     */
    graph(const graph& other);

    /**
     * @brief Move constructor
     *
     * Creates a new graph by moving the contents of an existing graph.
     * The moved-from graph is left in a valid but unspecified state.
     *
     * @param other Graph to move from
     */
    graph(graph&& other) noexcept;

    /**
     * @brief Copy assignment operator
     *
     * Assigns the contents of one graph to another by copying.
     *
     * @param other Graph to copy from
     * @return Reference to this graph
     */
    graph &operator=(const graph& other);

    /**
     * @brief Move assignment operator
     *
     * Assigns the contents of one graph to another by moving.
     * The moved-from graph is left in a valid but unspecified state.
     *
     * @param other Graph to move from
     * @return Reference to this graph
     */
    graph &operator=(graph&& other) noexcept;

    /**
     * @brief Virtual destructor
     *
     * Destroys the graph and frees all associated resources.
     */
    virtual ~graph();

    /**
     * @brief Checks whether the graph is empty
     *
     * @return true if the graph contains no nodes, false otherwise
     */
    [[nodiscard]] bool empty() const noexcept;

    /**
     * @brief Returns the number of nodes in the graph
     *
     * @return The number of nodes in the graph
     */
    [[nodiscard]] size_type size() const noexcept;

    /**
     * @brief Returns the maximum possible number of nodes in the graph
     *
     * @return Maximum possible number of nodes
     */
    [[nodiscard]] size_type max_size() const noexcept;

    /**
     * @brief Access or insert a node with the specified key
     *
     * If a node with the given key exists, returns a reference to its data.
     * Otherwise, creates a new node with default-constructed data.
     *
     * @param key Key of the node to access
     * @return Reference to the node's data
     */
    graphed_type &operator[](const key_type& key);

    /**
     * @brief Access or insert a node with the specified key (move version)
     *
     * If a node with the given key exists, returns a reference to its data.
     * Otherwise, creates a new node with default-constructed data.
     *
     * @param key Key of the node to access (may be moved from)
     * @return Reference to the node's data
     */
    graphed_type &operator[](key_type&& key);

#if defined(GRAPH_HAS_CPP_17)
    /**
     * @brief Access a node with the specified key (const version)
     *
     * If a node with the given key exists, returns an optional containing its data.
     * Otherwise, returns an empty optional.
     *
     * @param key Key of the node to access
     * @return Optional containing the node's data or empty if not found
     */
    std::optional<graphed_type> operator[](key_type&& key) const;
#else
    /**
     * @brief Access a node with the specified key (const version)
     *
     * If a node with the given key exists, returns its data.
     * Otherwise, throws an invalid_argument exception.
     *
     * @param key Key of the node to access
     * @return Copy of the node's data
     * @throws invalid_argument if node with key does not exist
     */
    graphed_type operator[](key_type&& key) const;
#endif

    /**
     * @brief Access the cost of an edge between two nodes (iterator version)
     *
     * If an edge between the nodes exists, returns a reference to its cost.
     * Otherwise, creates a new edge with infinite cost.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return Reference to the edge cost
     */
    cost_type &operator()(iterator from, iterator to);

    /**
     * @brief Access the cost of an edge between two nodes (key version)
     *
     * If an edge between the nodes exists, returns a reference to its cost.
     * Otherwise, creates a new edge with infinite cost.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return Reference to the edge cost
     */
    cost_type &operator()(const key_type& from_key, const key_type& to_key);

#if defined(GRAPH_HAS_CPP_17)
    /**
     * @brief Access the cost of an edge between two nodes (const iterator version)
     *
     * If an edge between the nodes exists, returns an optional containing its cost.
     * Otherwise, returns an empty optional.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return Optional containing the edge cost or empty if edge doesn't exist
     */
    std::optional<cost_type> operator()(const_iterator from, const_iterator to) const;

    /**
     * @brief Access the cost of an edge between two nodes (const key version)
     *
     * If an edge between the nodes exists, returns an optional containing its cost.
     * Otherwise, returns an empty optional.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return Optional containing the edge cost or empty if edge doesn't exist
     */
    std::optional<cost_type> operator()(const key_type& from_key, const key_type& to_key) const;
#else
    /**
     * @brief Access the cost of an edge between two nodes (const iterator version)
     *
     * If an edge between the nodes exists, returns its cost.
     * Otherwise, throws an invalid_argument exception.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return Copy of the edge cost
     * @throws invalid_argument if edge doesn't exist
     */
    cost_type operator()(const_iterator from, const_iterator to) const;

    /**
     * @brief Access the cost of an edge between two nodes (const key version)
     *
     * If an edge between the nodes exists, returns its cost.
     * Otherwise, throws an invalid_argument exception.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return Copy of the edge cost
     * @throws invalid_argument if edge doesn't exist
     */
    cost_type operator()(const key_type& from_key, const key_type& to_key) const;
#endif

    /**
     * @brief Insert a node (deprecated)
     * @deprecated Use add_node instead
     */
    [[deprecated]] std::pair<iterator, bool> insert(const value_type &);

    /**
     * @brief Insert a node at a specific position
     *
     * @param position Hint for where to insert the node
     * @param value Node to insert
     * @return Iterator to the inserted node
     */
    iterator insert(const_iterator position, const value_type &);

    /**
     * @brief Insert a node with specified key and data
     *
     * @param position Hint for where to insert the node
     * @param key Key for the new node
     * @param data Data for the new node
     * @return Iterator to the inserted node
     */
    iterator insert(const_iterator position, const key_type &, graphed_type &);

    /**
     * @brief Insert a node with specified key and node
     *
     * @param position Hint for where to insert the node
     * @param key Key for the new node
     * @param node Node to insert
     * @return Iterator to the inserted node
     */
    iterator insert(const_iterator position, const key_type &, const node &);

    /**
     * @brief Emplace a node with the specified key
     *
     * Constructs a new node in-place with the given key.
     *
     * @param key Key for the new node
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> emplace(const key_type &);

    /**
     * @brief Emplace a node with the specified key and data
     *
     * Constructs a new node in-place with the given key and data.
     *
     * @param key Key for the new node
     * @param data Data for the new node
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> emplace(const key_type &, const graphed_type &);

    /**
     * @brief Emplace a node with the specified key and node
     *
     * Constructs a new node in-place with the given key and node.
     *
     * @param key Key for the new node
     * @param node Node to emplace
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> emplace(const key_type &, const node &);

    /**
     * @brief Add a node with the specified key
     *
     * If a node with the given key doesn't exist, creates a new node with default data.
     *
     * @param key Key for the node
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> add_node(const key_type &);

    /**
     * @brief Add a node with the specified key and data
     *
     * If a node with the given key doesn't exist, creates a new node with the given data.
     *
     * @param key Key for the node
     * @param data Data for the node
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> add_node(const key_type &, const graphed_type &);

    /**
     * @brief Add a node with the specified key and node
     *
     * If a node with the given key doesn't exist, creates a new node with the given node's data.
     *
     * @param key Key for the node
     * @param node Node to copy data from
     * @return Pair containing iterator to the node and boolean indicating if insertion occurred
     */
    std::pair<iterator, bool> add_node(const key_type &, const node &);

    /**
     * @brief Add an edge between two nodes (iterator version)
     *
     * Creates an edge between the nodes pointed to by the iterators.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @param cost Cost of the edge (default: epsilon)
     * @return true if edge was added, false if it already existed
     */
    bool add_edge(const_iterator from, const_iterator to, cost_type cost = std::numeric_limits<cost_type>::epsilon());

    /**
     * @brief Add an edge between two nodes (key version)
     *
     * Creates an edge between the nodes with the given keys.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @param cost Cost of the edge (default: epsilon)
     * @return true if edge was added, false if it already existed
     */
    bool add_edge(const key_type& from_key, const key_type& to_key, cost_type cost = std::numeric_limits<cost_type>::epsilon());

    /**
     * @brief Make the graph complete with specified edge cost
     *
     * Adds edges between all pairs of nodes with the given cost.
     *
     * @param cost Cost for all edges
     */
    void make_complete(cost_type cost);

    /**
     * @brief Erase a node
     *
     * Removes the node pointed to by the iterator.
     *
     * @param position Iterator to the node to erase
     * @return Iterator following the erased node
     */
    iterator erase(const_iterator position);

    /**
     * @brief Erase a range of nodes
     *
     * Removes the nodes in the range [first, last).
     *
     * @param first Iterator to the first node to erase
     * @param last Iterator to one past the last node to erase
     * @return Iterator following the last erased node
     */
    iterator erase(const_iterator first, const_iterator last);

    /**
     * @brief Erase a node by key
     *
     * Removes the node with the given key.
     *
     * @param key Key of the node to erase
     * @return Number of nodes removed (0 or 1)
     */
    size_type erase(const key_type& key);

    /**
     * @brief Delete a node
     *
     * Removes the node pointed to by the iterator.
     *
     * @param position Iterator to the node to delete
     * @return Iterator following the deleted node
     */
    iterator del_node(const_iterator position);

    /**
     * @brief Delete a range of nodes
     *
     * Removes the nodes in the range [first, last).
     *
     * @param first Iterator to the first node to delete
     * @param last Iterator to one past the last node to delete
     * @return Iterator following the last deleted node
     */
    iterator del_nodes(const_iterator first, const_iterator last);

    /**
     * @brief Delete a node by key
     *
     * Removes the node with the given key.
     *
     * @param key Key of the node to delete
     * @return Number of nodes removed (0 or 1)
     */
    size_type del_node(const key_type& key);

    /**
     * @brief Clear all nodes and edges from the graph
     */
    void clear() noexcept;

    /**
     * @brief Delete an edge between two nodes (iterator version)
     *
     * Removes the edge between the nodes pointed to by the iterators.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return Number of edges removed (0 or 1)
     */
    size_type del_edge(const_iterator from, const_iterator to);

    /**
     * @brief Delete an edge between two nodes (key version)
     *
     * Removes the edge between the nodes with the given keys.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return Number of edges removed (0 or 1)
     */
    size_type del_edge(const key_type& from_key, const key_type& to_key);

    /**
     * @brief Clear all edges from the graph
     */
    void clear_edges();

    /**
     * @brief Clear edges from a specific node (iterator version)
     *
     * Removes all edges from the node pointed to by the iterator.
     *
     * @param position Iterator to the node
     * @return Number of edges removed
     */
    size_type clear_edges(const_iterator position);

    /**
     * @brief Clear edges from a specific node (key version)
     *
     * Removes all edges from the node with the given key.
     *
     * @param key Key of the node
     * @return Number of edges removed
     */
    size_type clear_edges(const key_type& key);

    /**
     * @brief Swap the contents of two graphs
     *
     * Exchanges the contents of this graph with another graph.
     *
     * @param other Graph to swap with
     */
    void swap(graph& other) noexcept;

    /**
     * @brief Count the number of nodes with a specific key
     *
     * @param key Key to count
     * @return Number of nodes with the given key (0 or 1)
     */
    size_type count(const key_type &) const;

    /**
     * @brief Find a node with a specific key
     *
     * @param key Key to search for
     * @return Iterator to the node if found, end() otherwise
     */
    iterator find(const key_type &);

    /**
     * @brief Find a node with a specific key (const version)
     *
     * @param key Key to search for
     * @return Const iterator to the node if found, cend() otherwise
     */
    const_iterator find(const key_type &) const;

    /**
     * @brief Check if a node exists (iterator version)
     *
     * @param position Iterator to the node to check
     * @return true if the node exists, false otherwise
     */
    bool existing_node(const_iterator position) const;

    /**
     * @brief Check if a node exists (key version)
     *
     * @param key Key of the node to check
     * @return true if the node exists, false otherwise
     */
    bool existing_node(const key_type& key) const;

    /**
     * @brief Check if an edge exists between two nodes (iterator version)
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return true if the edge exists, false otherwise
     */
    bool existing_edge(const_iterator from, const_iterator to) const;

    /**
     * @brief Check if an edge exists between two nodes (key version)
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return true if the edge exists, false otherwise
     */
    bool existing_edge(const key_type& from_key, const key_type& to_key) const;

    /**
     * @brief Check if there exists a path connecting two nodes (iterator version)
     *
     * If from and to are equal, this function returns true.
     *
     * @param from Iterator to the source node
     * @param to Iterator to the target node
     * @return true if a path exists, false otherwise
     */
    bool has_path_connecting(const_iterator from, const_iterator to) const;

    /**
     * @brief Check if there exists a path connecting two nodes (key version)
     *
     * If from_key and to_key are equal, this function returns true.
     *
     * @param from_key Key of the source node
     * @param to_key Key of the target node
     * @return true if a path exists, false otherwise
     */
    bool has_path_connecting(const key_type& from_key, const key_type& to_key) const;

    /**
     * @brief Get the number of nodes in the graph
     *
     * @return Number of nodes
     */
    [[nodiscard]] size_type get_nbr_nodes() const noexcept;

    /**
     * @brief Get the number of edges in the graph
     *
     * @return Number of edges
     */
    [[nodiscard]] size_type get_nbr_edges() const noexcept;

    /**
     * @brief Get the nature of the graph
     *
     * @return Nature of the graph (DIRECTED or UNDIRECTED)
     */
    [[nodiscard]] Nature get_nature() const;

    /**
     * @brief Get the degree of a node (iterator version)
     *
     * @param position Iterator to the node
     * @return Degree of the node
     */
    Degree degree(const_iterator position) const;

    /**
     * @brief Get the degree of a node (key version)
     *
     * @param key Key of the node
     * @return Degree of the node
     */
    Degree degree(const key_type& key) const;

    /**
     * @brief Get the node with maximum degree
     *
     * @return Pair containing iterator to the node and its degree
     */
    std::pair<const_iterator, Degree> degree_max() const;

    /**
     * @brief Get the node with minimum degree
     *
     * @return Pair containing iterator to the node and its degree
     */
    std::pair<const_iterator, Degree> degree_min() const;

    /**
     * @brief Get degrees of all nodes
     *
     * @return Map of node keys to their degrees
     */
    std::map<key_type, Degree> degrees() const;

    /**
     * @brief Get incoming edges of a node (directed graphs only)
     *
     * @tparam enable_if<detail::is_directed<Nat>::value> SFINAE constraint for directed graphs
     * @param position Iterator to the node
     * @return Vector of incoming edges
     */
    template <class = std::enable_if<detail::is_directed<Nat>::value >>
    std::vector<typename node::edge> get_in_edges(const_iterator position) const;

    /**
     * @brief Get incoming edges of a node (directed graphs only, key version)
     *
     * @tparam enable_if<detail::is_directed<Nat>::value> SFINAE constraint for directed graphs
     * @param key Key of the node
     * @return Vector of incoming edges
     */
    template <class = std::enable_if<detail::is_directed<Nat>::value >>
    std::vector<typename node::edge> get_in_edges(const key_type& key) const;

    /**
     * @brief Get outgoing edges of a node (directed graphs only)
     *
     * @tparam enable_if<detail::is_directed<Nat>::value> SFINAE constraint for directed graphs
     * @param position Iterator to the node
     * @return Vector of outgoing edges
     */
    template <class = std::enable_if<detail::is_directed<Nat>::value >>
    std::vector<typename node::edge> get_out_edges(const_iterator position) const;

    /**
     * @brief Get outgoing edges of a node (directed graphs only, key version)
     *
     * @tparam enable_if<detail::is_directed<Nat>::value> SFINAE constraint for directed graphs
     * @param key Key of the node
     * @return Vector of outgoing edges
     */
    template <class = std::enable_if<detail::is_directed<Nat>::value >>
    std::vector<typename node::edge> get_out_edges(const key_type& key) const;

    /**
     * @brief Get edges of a node (undirected graphs only)
     *
     * @tparam enable_if<detail::is_undirected<Nat>::value> SFINAE constraint for undirected graphs
     * @param position Iterator to the node
     * @return Vector of edges
     */
    template <class = std::enable_if<detail::is_undirected<Nat>::value >>
    std::vector<typename node::edge> get_edges(const_iterator position) const;

    /**
     * @brief Get edges of a node (undirected graphs only, key version)
     *
     * @tparam enable_if<detail::is_undirected<Nat>::value> SFINAE constraint for undirected graphs
     * @param key Key of the node
     * @return Vector of edges
     */
    template <class = std::enable_if<detail::is_undirected<Nat>::value >>
    std::vector<typename node::edge> get_edges(const key_type& key) const;

    /**
     * @brief Check if the graph contains cycles (directed graphs only)
     *
     * @tparam enable_if<detail::is_directed<Nat>::value> SFINAE constraint for directed graphs
     * @return true if the graph contains cycles, false otherwise
     */
    template <class = std::enable_if<detail::is_directed<Nat>::value >>
    [[nodiscard]] bool is_cyclic() const;

    /*
    // TODO
    bool is_isomorphic() const;

    // TODO
    std::vector<const_iterator> toposort() const;

    // TODO
    std::set<std::vector<const_iterator>, iterator_comparator> kosaraju_scc() const;

    // TODO
    std::set<std::vector<const_iterator>, iterator_comparator> tarjan_scc() const;

    // TODO
    size_type connected_components() const;

    // TODO
    graph &condensate(bool make_acyclic = true);

    // TODO
    std::vector<const_iterator> maximum_clique() const;
    */

    /**
     * @brief Output stream operator
     *
     * Displays a JSON representation of the graph.
     *
     * @tparam K Key type
     * @tparam D Data type
     * @tparam C Cost type
     * @tparam N Nature type
     * @param os Output stream
     * @param g Graph to output
     * @return Reference to the output stream
     */
    template<class K, class D, class C, Nature N>
    friend std::ostream & operator<<(std::ostream& os, const graph<K, D, C, N> &g);

    /**
     * @brief Input stream operator
     *
     * Tries to load from JSON and then from FILE.
     *
     * @tparam K Key type
     * @tparam D Data type
     * @tparam C Cost type
     * @tparam N Nature type
     * @param is Input stream
     * @param g Graph to load into
     * @return Reference to the input stream
     */
    template<class K, class D, class C, Nature N>
    friend std::istream & operator>>(std::istream& is, graph<K, D, C, N> &g);

    /**
     * @brief Load a graph from a file
     *
     * @param filename Path to the file to load
     * @note .DOT format is not supported
     */
    void load(const char* filename);

    /**
     * @brief Generate a DOT representation of the graph
     *
     * @param graph_name Optional name for the graph (accepted characters: [a-zA-Z0-9_-])
     * @return Unique pointer to the DOT string representation
     */
    [[nodiscard]] std::unique_ptr<std::string> generate_dot(const std::string& graph_name = "") const;

    /**
     * @brief Save the graph to a DOT file
     *
     * @param filename Path to the file to save to
     * @param graph_name Optional name for the graph (accepted characters: [a-zA-Z0-9_-])
     */
    void save_to_dot(const char* filename, const std::string& graph_name = "") const;

    /**
     * @brief Generate a JSON representation of the graph
     *
     * @return Unique pointer to the JSON representation
     */
    [[nodiscard]] std::unique_ptr<nlohmann::json> generate_json() const;

    /**
     * @brief Save the graph to a JSON file
     *
     * @param filename Path to the file to save to
     */
    void save_to_json(const char* filename) const;

    /**
     * @brief Parse a graph from a JSON input stream
     *
     * @param is Input stream containing JSON data
     */
    void parse_from_json(std::istream& is);

    /**
     * @brief Debug function to load from JSON Rust format (deprecated)
     * @deprecated Use parse_from_json instead
     */
    [[deprecated]] void DEBUG_load_from_json_rust(const char*);

    /**
     * @brief Generate a GRP representation of the graph
     *
     * @return Unique pointer to the GRP string representation
     */
    [[nodiscard]] std::unique_ptr<std::string> generate_grp() const;

    /**
     * @brief Save the graph to a GRP file
     *
     * @param filename Path to the file to save to
     */
    void save_to_grp(const char* filename) const;

    /**
     * @brief Parse a graph from a GRP input stream
     *
     * @param is Input stream containing GRP data
     */
    void parse_from_grp(std::istream& is);

    /**
     * @brief Equality operator
     *
     * Compares two graphs for equality.
     *
     * @tparam K Key type of other graph
     * @tparam D Data type of other graph
     * @tparam C Cost type of other graph
     * @tparam N Nature type of other graph
     * @param other Graph to compare with
     * @return true if graphs are equal, false otherwise
     */
    template<class K, class D, class C, Nature N>
    bool operator==(const graph<K, D, C, N> &other) const noexcept;

    /**
     * @brief Inequality operator
     *
     * Compares two graphs for inequality.
     *
     * @tparam K Key type of other graph
     * @tparam D Data type of other graph
     * @tparam C Cost type of other graph
     * @tparam N Nature type of other graph
     * @param other Graph to compare with
     * @return true if graphs are not equal, false otherwise
     */
    template<class K, class D, class C, Nature N>
    bool operator!=(const graph<K, D, C, N> &other) const noexcept;

    class node : public basic_node<graphed_type, cost_type, iterator, const_iterator> {
      public:
        explicit node();

        explicit node(const graphed_type &);

        node &operator=(const graphed_type &);

      private:
        friend class graph;

        void set_iterator_values(iterator this_, iterator end, const_iterator cend);
    };

    /// @section Search algorithms

    search_path bfs(key_type       start, key_type                            target)      const;
    search_path bfs(key_type       start, std::list<key_type>                 target_list) const;
    search_path bfs(key_type       start, std::function<bool(key_type)>       is_goal)     const;

    search_path bfs(const_iterator start, const_iterator                      target)      const;
    search_path bfs(const_iterator start, std::list<const_iterator>           target_list) const;
    search_path bfs(const_iterator start, std::function<bool(const_iterator)> is_goal)     const;

    search_path dfs(key_type       start, key_type                            target)      const;
    search_path dfs(key_type       start, std::list<key_type>                 target_list) const;
    search_path dfs(key_type       start, std::function<bool(key_type)>       is_goal)     const;

    search_path dfs(const_iterator start, const_iterator                      target)      const;
    search_path dfs(const_iterator start, std::list<const_iterator>           target_list) const;
    search_path dfs(const_iterator start, std::function<bool(const_iterator)> is_goal)     const;

    search_path dls(key_type       start, key_type                            target,      size_type depth) const;
    search_path dls(key_type       start, std::list<key_type>                 target_list, size_type depth) const;
    search_path dls(key_type       start, std::function<bool(key_type)>       is_goal,     size_type depth) const;

    search_path dls(const_iterator start, const_iterator                      target,      size_type depth) const;
    search_path dls(const_iterator start, std::list<const_iterator>           target_list, size_type depth) const;
    search_path dls(const_iterator start, std::function<bool(const_iterator)> is_goal,     size_type depth) const;

    search_path iddfs(key_type       start, key_type                            target)      const;
    search_path iddfs(key_type       start, std::list<key_type>                 target_list) const;
    search_path iddfs(key_type       start, std::function<bool(key_type)>       is_goal)     const;

    search_path iddfs(const_iterator start, const_iterator                      target)      const;
    search_path iddfs(const_iterator start, std::list<const_iterator>           target_list) const;
    search_path iddfs(const_iterator start, std::function<bool(const_iterator)> is_goal)     const;

    search_path ucs(key_type       start, key_type                            target)      const;
    search_path ucs(key_type       start, std::list<key_type>                 target_list) const;
    search_path ucs(key_type       start, std::function<bool(key_type)>       is_goal)     const;

    search_path ucs(const_iterator start, const_iterator                      target)      const;
    search_path ucs(const_iterator start, std::list<const_iterator>           target_list) const;
    search_path ucs(const_iterator start, std::function<bool(const_iterator)> is_goal)     const;

    search_path astar(key_type       start, key_type                            target,      std::function<cost_type(const_iterator)> heuristic) const;
    search_path astar(key_type       start, std::list<key_type>                 target_list, std::function<cost_type(const_iterator)> heuristic) const;
    search_path astar(key_type       start, std::function<bool(key_type)>       is_goal,     std::function<cost_type(const_iterator)> heuristic) const;

    search_path astar(const_iterator start, const_iterator                      target,      std::function<cost_type(const_iterator)> heuristic) const;
    search_path astar(const_iterator start, std::list<const_iterator>           target_list, std::function<cost_type(const_iterator)> heuristic) const;
    search_path astar(const_iterator start, std::function<bool(const_iterator)> is_goal,     std::function<cost_type(const_iterator)> heuristic) const;

    shortest_paths dijkstra(key_type       start)                                                  const;
    shortest_paths dijkstra(key_type       start, key_type                            target)      const;
    shortest_paths dijkstra(key_type       start, std::list<key_type>                 target_list) const;
    shortest_paths dijkstra(key_type       start, std::function<bool(key_type)>       is_goal)     const;

    shortest_paths dijkstra(const_iterator start)                                                  const;
    shortest_paths dijkstra(const_iterator start, const_iterator                      target)      const;
    shortest_paths dijkstra(const_iterator start, std::list<const_iterator>           target_list) const;
    shortest_paths dijkstra(const_iterator start, std::function<bool(const_iterator)> is_goal)     const;

    shortest_paths bellman_ford(key_type       start) const;
    shortest_paths bellman_ford(const_iterator start) const;

    class search_path final : std::deque<std::pair<graph::const_iterator, cost_type >> {
        template <bool> friend search_path graph::abstract_first_search(graph::const_iterator, std::function<bool(const_iterator)>) const;

        friend search_path graph::dls   (graph::const_iterator, std::function<bool(const_iterator)>, size_type)                                const;
        friend search_path graph::iddfs (graph::const_iterator, std::function<bool(const_iterator)>)                                           const;
        friend search_path graph::ucs   (graph::const_iterator, std::function<bool(const_iterator)>)                                           const;
        friend search_path graph::astar (graph::const_iterator, std::function<bool(const_iterator)>, std::function<cost_type(const_iterator)>) const;

        friend class shortest_paths;

        friend bool path_comparator::operator()(const search_path &, const search_path &) const;

        using Container = std::deque<std::pair<graph::const_iterator, cost_type >>;

      public:
        using value_type             = typename Container::value_type;
        using reference              = typename Container::reference;
        using const_reference        = typename Container::const_reference;
        using iterator               = typename Container::iterator;
        using const_iterator         = typename Container::const_iterator;
        using reverse_iterator       = typename Container::reverse_iterator;
        using const_reverse_iterator = typename Container::const_reverse_iterator;

        using Container::begin;
        using Container::cbegin;
        using Container::rbegin;
        using Container::crbegin;
        using Container::end;
        using Container::cend;
        using Container::rend;
        using Container::crend;

        search_path() = default;
        search_path(const search_path &);
        ~search_path() = default;

        using Container::empty;
        using Container::size;
        using Container::clear;
        using Container::front;
        using Container::pop_front;
        using Container::swap;

        using Container::push_back;
        using Container::emplace_back;

        cost_type total_cost() const;

        bool contain(const graph::const_iterator &) const;

        friend std::ostream &operator << (std::ostream &os, const graph::search_path &sp) {
            cost_type count{};
            for (const std::pair<graph::const_iterator, cost_type> &p : sp) {
                os << "-> " << p.first->first << " (" << (count += p.second) << ") ";
            }
            return os;
        }
    };

    class shortest_paths final : std::map<graph::const_iterator, std::pair<graph::const_iterator, cost_type>, iterator_comparator> {
        graph::const_iterator _start;

        friend shortest_paths graph::dijkstra    (graph::const_iterator, std::function<bool(const_iterator)>) const;
        friend shortest_paths graph::bellman_ford(graph::const_iterator)                                      const;

        using Container = std::map<graph::const_iterator, std::pair<graph::const_iterator, cost_type>, iterator_comparator>;

        explicit shortest_paths(graph::const_iterator start);

      public:
        using value_type             = typename Container::value_type;
        using mapped_type            = typename Container::mapped_type;
        using reference              = typename Container::reference;
        using const_reference        = typename Container::const_reference;
        using iterator               = typename Container::iterator;
        using const_iterator         = typename Container::const_iterator;
        using reverse_iterator       = typename Container::reverse_iterator;
        using const_reverse_iterator = typename Container::const_reverse_iterator;

        using Container::begin;
        using Container::cbegin;
        using Container::rbegin;
        using Container::crbegin;
        using Container::end;
        using Container::cend;
        using Container::rend;
        using Container::crend;

        shortest_paths(const shortest_paths &);
        ~shortest_paths() = default;

        using Container::empty;
        using Container::size;

        /// @return the father of current in the optimal path from _start to current
        graph::const_iterator get_previous(graph::const_iterator current) const;

        /// @return the re-build path from the start node to the target
        search_path get_path(graph::key_type target) const;
        search_path get_path(graph::const_iterator target) const;

        friend std::ostream & operator<<(std::ostream & os, const shortest_paths & sp) {
            for (auto p : sp) {
                os << sp.get_path(p.first) << std::endl;
            }
            return os;
        }
    };

  private:
    /// Helper functions and classes
    class path_comparator : public std::function<bool(search_path, search_path)> {
        std::function<cost_type(const_iterator)> _heuristic;

      public:
        explicit path_comparator(std::function<cost_type(const_iterator)> heuristic);

        bool operator() (const search_path &, const search_path &) const;
    };

    struct iterator_comparator : std::function<bool(const_iterator, const_iterator)> {
        bool operator()(const const_iterator &, const const_iterator &) const;
    };

    bool is_cyclic_rec(const_iterator current, std::list<const_iterator> path) const;

    template <bool insertFront> search_path abstract_first_search(const_iterator start, std::function<bool(const_iterator)> is_goal) const;
};

template <class Key, class T, class Cost = std::size_t>
using graph_directed   = graph<Key, T, Cost, DIRECTED>;

template <class Key, class T, class Cost = std::size_t>
using graph_undirected = graph<Key, T, Cost, UNDIRECTED>;

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::edge::edge(const std::weak_ptr<basic_node<Data, Cost, Container, constContainer >> &ptr, Cost c) : _target(ptr),
    _cost(std::make_shared<Cost>(c)) {}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::edge::edge(const edge &e) : _target(e._target), _cost(e._cost) {}

template <class Data, class Cost, class Container, class constContainer>
std::tuple<Cost, basic_node<Data, Cost, Container, constContainer >> basic_node<Data, Cost, Container, constContainer>::edge::tie() const {
    return std::tie(*_cost, *_target.lock().get());
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::edge::operator<(const edge &other) const {
    return tie() < other.tie();
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::edge::operator==(const edge &other) const {
    return tie() == other.tie();
}

template <class Data, class Cost, class Container, class constContainer>
constContainer basic_node<Data, Cost, Container, constContainer>::edge::target() const {
    return _target.lock()->container_from_this;
}

template <class Data, class Cost, class Container, class constContainer>
Cost & basic_node<Data, Cost, Container, constContainer>::edge::cost() const {
    return *_cost;
}

template <class Data, class Cost, class Container, class constContainer>
std::tuple<Data, std::size_t, std::list<typename basic_node<Data, Cost, Container, constContainer>::edge >> basic_node<Data, Cost, Container, constContainer>::tie() const {
    return std::tie(_data, _in_degree, _out_edges);
}

template <class Data, class Cost, class Container, class constContainer>
std::list<typename basic_node<Data, Cost, Container, constContainer>::edge> basic_node<Data, Cost, Container, constContainer>::get_edges() const {
    return _out_edges;
}

template <class Data, class Cost, class Container, class constContainer>
void basic_node<Data, Cost, Container, constContainer>::increment_in_degree(int n) {
    _in_degree += n;
}

template <class Data, class Cost, class Container, class constContainer>
void basic_node<Data, Cost, Container, constContainer>::decrement_in_degree(int n) {
    _in_degree -= n;
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::set_edge(constContainer other, std::shared_ptr<Cost> cost) {
    std::pair<basic_node<Data, Cost, Container, constContainer>::EdgesIterator, bool> new_edge{add_edge(other, *cost)};

    new_edge.first->_cost = cost;

    return new_edge.second;
}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::basic_node() : basic_node(Data()) {}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::basic_node(const Data &d) : _data(d) {}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::basic_node(const basic_node &n) {
    *this = n;
}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer> &basic_node<Data, Cost, Container, constContainer>::operator=(const basic_node &n) {
    _data               = n._data;
    _out_edges          = n._out_edges;
    _in_degree          = n._in_degree;
    container_from_this = n.container_from_this;

    return *this;
}

template <class Data, class Cost, class Container, class constContainer>
basic_node<Data, Cost, Container, constContainer>::~basic_node() = default;

template <class Data, class Cost, class Container, class constContainer>
Data & basic_node<Data, Cost, Container, constContainer>::get() {
    return _data;
}

template <class Data, class Cost, class Container, class constContainer>
Data basic_node<Data, Cost, Container, constContainer>::get() const {
    return _data;
}

template <class Data, class Cost, class Container, class constContainer>
Cost & basic_node<Data, Cost, Container, constContainer>::get_cost(Container other) {
    std::shared_ptr<basic_node<Data, Cost, Container, constContainer >> ptr(detail::get_value(other, end_container));

    if (ptr == nullptr) {
        GRAPH_THROW(unexpected_nullptr)
    }

    for (EdgesIterator it{_out_edges.begin()}; it != _out_edges.end(); ++it)
        if (it->_target.lock() == ptr) {
            return it->cost();
        }

    /// Link doesn't exist
    _out_edges.emplace_back(std::weak_ptr<basic_node<Data, Cost, Container, constContainer >> (detail::get_value(other, end_container)), infinity);
    ptr->increment_in_degree();
    return (--_out_edges.end())->cost();
}

template <class Data, class Cost, class Container, class constContainer>
Cost basic_node<Data, Cost, Container, constContainer>::get_cost(constContainer other) const {
    std::shared_ptr<basic_node<Data, Cost, Container, constContainer >> ptr(detail::get_value(other, cend_container));

    if (ptr == nullptr) {
        GRAPH_THROW(unexpected_nullptr)
    }

    for (auto it = _out_edges.begin(); it != _out_edges.end(); ++it)
        if (it->_target.lock() == ptr) {
            return it->cost();
        }

    /// Link doesn't exist
    return infinity;
}

template <class Data, class Cost, class Container, class constContainer>
Cost & basic_node<Data, Cost, Container, constContainer>::operator[](Container other) {
    return get_cost(other);
}

template <class Data, class Cost, class Container, class constContainer>
Cost basic_node<Data, Cost, Container, constContainer>::operator[](constContainer other) const {
    return get_cost(other);
}

template <class Data, class Cost, class Container, class constContainer>
template <class T_data>
void basic_node<Data, Cost, Container, constContainer>::set(const T_data &d) {
    _data = static_cast<Data>(d);
}

template <class Data, class Cost, class Container, class constContainer>
template <class T_cost>
void basic_node<Data, Cost, Container, constContainer>::set_cost(Container other, const T_cost &c) {
    std::shared_ptr<basic_node<Data, Cost, Container, constContainer >> ptr(detail::get_value(other, end_container));

    if (ptr == nullptr) {
        GRAPH_THROW(unexpected_nullptr)
    }

    Cost new_cost{static_cast<Cost>(c)};
    bool existing_edge{false};

    for (EdgesIterator it{_out_edges.begin()}; it != _out_edges.end(); ++it) {
        if (it->_target.lock() == ptr) {
            it->cost() = new_cost;
            existing_edge = true;
        }
    }

    if (!existing_edge) {
        this->add_edge(other, new_cost);
    }
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::del_edge(constContainer other) {
    return del_edge_if(other, [](const edge &) {
        return true;
    } );
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::del_edge_if(constContainer other, std::function<bool(const edge &)> predicate) {
    for (EdgesIterator it{_out_edges.begin()}; it != _out_edges.end(); ) {
        if (it->_target.lock() == detail::get_value(other, cend_container)) {
            if (predicate(*it)) {
                it = _out_edges.erase(it);
                other->second->decrement_in_degree();
                return true;
            }
            break;
        }
        ++it;
    }

    return false;
}

template <class Data, class Cost, class Container, class constContainer>
std::size_t basic_node<Data, Cost, Container, constContainer>::clear_edges() {
    const std::size_t NUM{_out_edges.size()};

    for (EdgesIterator it{_out_edges.begin()}; it != _out_edges.end(); ) {
        it->_target.lock()->decrement_in_degree();
        it = _out_edges.erase(it);
    }

    return NUM;
}

template <class Data, class Cost, class Container, class constContainer>
std::pair<std::size_t, std::size_t> basic_node<Data, Cost, Container, constContainer>::degree() const {
    return std::make_pair(_in_degree, _out_edges.size());
}

template <class Data, class Cost, class Container, class constContainer>
bool basic_node<Data, Cost, Container, constContainer>::existing_adjacent_node(constContainer other) const {
    std::shared_ptr<basic_node<Data, Cost, Container, constContainer >> ptr(detail::get_value(other, cend_container));

    if (ptr == nullptr) {
        return false;
    }

    for (auto it = _out_edges.begin(); it != _out_edges.end(); ++it) {
        if (it->_target.lock() == ptr) {
            return true;
        }
    }

    /// Link doesn't exist
    return false;
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator==(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return n1.tie() == n2.tie();
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator!=(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return !(n1 == n2);
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator<(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return n1.tie() < n2.tie();
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator>(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return n2 < n1;
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator<=(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return !(n2 < n1);
}

template <class Data, class Cost, class Container, class constContainer>
constexpr bool operator>=(const basic_node<Data, Cost, Container, constContainer> &n1, const basic_node<Data, Cost, Container, constContainer> &n2) noexcept {
    return !(n1 < n2);
}

#include <memory>
#include <set>

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::begin() noexcept {
    return _nodes.begin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::end() noexcept {
    return _nodes.end();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::begin() const noexcept {
    return _nodes.begin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::cbegin() const noexcept {
    return _nodes.cbegin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::end() const noexcept {
    return _nodes.end();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::cend() const noexcept {
    return _nodes.cend();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::reverse_iterator graph<Key, T, Cost, Nat>::rbegin() noexcept {
    return _nodes.rbegin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::reverse_iterator graph<Key, T, Cost, Nat>::rend() noexcept {
    return _nodes.rend();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_reverse_iterator graph<Key, T, Cost, Nat>::rbegin() const noexcept {
    return _nodes.rbegin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_reverse_iterator graph<Key, T, Cost, Nat>::crbegin() const noexcept {
    return _nodes.crbegin();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_reverse_iterator graph<Key, T, Cost, Nat>::rend() const noexcept {
    return _nodes.rend();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_reverse_iterator graph<Key, T, Cost, Nat>::crend() const noexcept {
    return _nodes.crend();
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::graph() {
    _nodes.clear();
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::graph(std::istream &is) {
    is >> *this;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::graph(const graph &other) {
    *this = other;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::graph(graph &&other) noexcept
    : _nodes(std::move(other._nodes))
    , _num_edges(other._num_edges) {
    other._num_edges = 0;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat> &graph<Key, T, Cost, Nat>::operator=(const graph &other) {
    clear();

    for (const_iterator it{other.cbegin()}; it != other.cend(); ++it) {
        add_node(it->first, it->second->get());
    }

    for (const_iterator it{other.cbegin()}; it != other.cend(); ++it) {
        std::list<typename node::edge> list = it->second->get_edges();
        for (typename node::edge e : list) {
            graph::const_iterator i{e.target()};
            add_edge(it->first, i->first, e.cost());
        }
    }

    return *this;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat> &graph<Key, T, Cost, Nat>::operator=(graph&& other) noexcept {
    // Handle self-assignment
    if (this != &other) {
        //swap(other);
        // Move the resources directly for better performance
        _nodes = std::move(other._nodes);
        _num_edges = other._num_edges;

        // Reset the moved-from object to a valid state
        other._num_edges = 0;
    }
    return *this;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::~graph() = default;

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::empty() const noexcept {
    return _nodes.empty();
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::size() const noexcept {
    return _nodes.size();
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::max_size() const noexcept {
    return _nodes.max_size();
}

template <class Key, class T, class Cost, Nature Nat>
T &graph<Key, T, Cost, Nat>::operator[](const key_type &k) {
    return add_node(k).first->second->get();
}

template <class Key, class T, class Cost, Nature Nat>
T &graph<Key, T, Cost, Nat>::operator[](key_type &&k) {
    return add_node(k).first->second->get();
}

#if defined(GRAPH_HAS_CPP_17)
template <class Key, class T, class Cost, Nature Nat>
std::optional<T> graph<Key, T, Cost, Nat>::operator[](key_type &&k) const {
    const_iterator it{this->find(k)};
    return it == cend() ? std::nullopt : std::optional<T>(it->second->get());
}
#else
template <class Key, class T, class Cost, Nature Nat>
T graph<Key, T, Cost, Nat>::operator[](key_type &&k) const {
    const_iterator it{this->find(k)};
    if (it == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Unexistant node")
    }

    return it->second->get();
}
#endif

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::cost_type &graph<Key, T, Cost, Nat>::operator()(iterator it1, iterator it2) {
    if (!existing_edge(it1, it2)) {
        add_edge(it1, it2, infinity);
    }

    return it1->second->get_cost(it2);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::cost_type &graph<Key, T, Cost, Nat>::operator()(const key_type &k1, const key_type &k2) {
    iterator it1{add_node(k1).first};
    iterator it2{add_node(k2).first};

    return operator()(it1, it2);
}

#if defined(GRAPH_HAS_CPP_17)
template <class Key, class T, class Cost, Nature Nat>
std::optional<typename graph<Key, T, Cost, Nat>::cost_type> graph<Key, T, Cost, Nat>::operator()(const_iterator it1, const_iterator it2) const {
    return existing_edge(it1, it2) ? std::optional<cost_type>(it1->second->get_cost(it2)) : std::nullopt;
}

template <class Key, class T, class Cost, Nature Nat>
std::optional<typename graph<Key, T, Cost, Nat>::cost_type> graph<Key, T, Cost, Nat>::operator()(const key_type &k1, const key_type &k2) const {
    return operator()(this->find(k1), this->find(k2));
}
#else
template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::cost_type graph<Key, T, Cost, Nat>::operator()(const_iterator it1, const_iterator it2) const {
    if (!existing_edge(it1, it2)) {
        GRAPH_THROW_WITH(invalid_argument, "Unexistant edge")
    }

    return it1->second->get_cost(it2);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::cost_type graph<Key, T, Cost, Nat>::operator()(const key_type &k1, const key_type &k2) const {
    return operator()(this->find(k1), this->find(k2));
}
#endif

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::insert(const graph<Key, T, cost_type, Nat>::value_type &val) {
    std::pair<iterator, bool> p{_nodes.insert(val)};
    p.first->second->set_iterator_values(p.first, end(), cend());
    return p;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::insert(const_iterator position, const value_type &val) {
    iterator it{_nodes.insert(position, val)};
    it->second->set_iterator_values(it, end(), cend());
    return it;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::insert(const_iterator position, const key_type &k, graphed_type &x) {
    return insert(position, std::make_pair(k, std::make_shared<node>(x)));
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::insert(const_iterator position, const key_type &k, const node &n) {
    return insert(position, std::make_pair(k, std::make_shared<node>(n)));
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::emplace(const key_type &k) {
    return emplace(k, node());
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::emplace(const key_type &k, const graphed_type &x) {
    return emplace(k, node(x));
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::emplace(const key_type &k, const node &n) {
    std::pair<iterator, bool> p{_nodes.emplace(k, std::make_shared<node>(n))};
    p.first->second->set_iterator_values(p.first, end(), cend());
    return p;
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::add_node(const key_type &k) {
    return emplace(k);
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::add_node(const key_type &k, const graphed_type &x) {
    return emplace(k, x);
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::iterator, bool> graph<Key, T, Cost, Nat>::add_node(const key_type &k, const node &n) {
    return emplace(k, n);
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::add_edge(const_iterator it1, const_iterator it2, cost_type cost) {
    std::pair<typename std::list<typename node::edge>::const_iterator, bool> new_edge{it1->second->add_edge(it2, cost)};

    if (get_nature() == UNDIRECTED) {
        it2->second->set_edge(it1, new_edge.first->_cost);
    }

    if (new_edge.second) {
        _num_edges++;
    }

    return true;
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::add_edge(const key_type &k1, const key_type &k2, cost_type cost) {
    return add_edge(emplace(k1).first, emplace(k2).first, cost);
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::make_complete(cost_type cost) {
    clear_edges();

    if (cost != infinity) {
        for (iterator it1{begin()}; it1 != end(); ++it1) {
            for (iterator it2{begin()}; it2 != end(); ++it2) {
                if (it1 != it2) {
                    add_edge(it1, it2, cost);
                }
            }
        }
    }
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::erase(const_iterator position) {
    clear_edges(position);

    return _nodes.erase(position);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::erase(const_iterator first, const_iterator last) {
    for (const_iterator it{first}; it != last && it != cend(); ++it) {
        clear_edges(it);
    }

    return _nodes.erase(first, last);
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::erase(const key_type &k) {
    const_iterator it{this->find(k)};
    if (it == cend()) {
        return 0;
    }

    clear_edges(it);
    return _nodes.erase(k);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::del_node(const_iterator position) {
    return erase(position);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::del_nodes(const_iterator first, const_iterator last) {
    return erase(first, last);
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::del_node(const key_type &k) {
    return erase(k);
}
template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::clear() noexcept {
    _nodes.clear();
    _num_edges = 0;
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::del_edge(const_iterator it1, const_iterator it2) {
    size_type result{0};
    if (it1 != end() && it2 != end()) {
        result = static_cast<size_type>(it1->second->del_edge(it2));

        if (get_nature() == UNDIRECTED) {
            it2->second->del_edge(it1);
        }

        _num_edges -= result;
    }
    return result;
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::del_edge(const key_type &k1, const key_type &k2) {
    return del_edge(this->find(k1), this->find(k2));
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::clear_edges() {
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        clear_edges(it);
    }
    _num_edges = 0;
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::clear_edges(const_iterator it) {
    size_type result{0};
    if (it != cend()) {
        for (const_iterator it1{cbegin()}; it1 != cend(); ++it1) {
            del_edge(it1, it);
        }

        if (get_nature() == DIRECTED) {
            result += it->second->clear_edges();
        }

        _num_edges -= result;
    }
    return result;
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::clear_edges(const key_type &k) {
    return clear_edges(find(k));
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::swap(graph &other) noexcept {
    std::swap(_nodes,     other._nodes);
    std::swap(_num_edges, other._num_edges);
}

namespace std {
    template <class Key, class T, class Cost, Nature Nat>
    void swap(graph<Key, T, Cost, Nat> &g1, graph<Key, T, Cost, Nat> &g2) noexcept {
        g1.swap(g2);
    }
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::count(const key_type &k) const {
    return _nodes.count(k);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::iterator graph<Key, T, Cost, Nat>::find(const key_type &k) {
    return _nodes.find(k);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::find(const key_type &k) const {
    return _nodes.find(k);
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::existing_node(const_iterator it) const {
    return it != cend();
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::existing_node(const key_type &k) const {
    return existing_node(find(k));
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::existing_edge(const_iterator it1, const_iterator it2) const {
    if (it1 != cend() && it2 != cend()) {
        if (get_nature() == DIRECTED) {
            return it1->second->existing_adjacent_node(it2);
        }
        return it1->second->existing_adjacent_node(it2) && it2->second->existing_adjacent_node(it1);
    }

    return false;
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::existing_edge(const key_type &k1, const key_type &k2) const {
    return existing_edge(this->find(k1), this->find(k2));
}
template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::has_path_connecting(const_iterator from, const_iterator to) const {
    if (from == cend() || to == cend()) {
        GRAPH_THROW(unexpected_nullptr)
    }
    if (from == to) {
        return true;
    }
    return !dfs(from, to).empty();
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::has_path_connecting(const key_type &from, const key_type &to) const {
    return has_path_connecting(this->find(from), this->find(to));
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::get_nbr_nodes() const noexcept {
    return _nodes.size();
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::get_nbr_edges() const noexcept {
    return _num_edges;
}

template <class Key, class T, class Cost, Nature Nat>
Nature graph<Key, T, Cost, Nat>::get_nature() const {
    return Nat;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::Degree graph<Key, T, Cost, Nat>::degree(const_iterator position) const {
    if (get_nature() == DIRECTED) {
        return position == cend() ? Degree::min() : Degree(position->second->degree().first, position->second->degree().second);
    }
    return position == cend() ? Degree::min() : Degree(position->second->degree().first, 0);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::Degree graph<Key, T, Cost, Nat>::degree(const key_type &k) const {
    return degree(find(k));
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::const_iterator, typename graph<Key, T, Cost, Nat>::Degree> graph<Key, T, Cost, Nat>::degree_max() const {
    if (empty()) {
        return std::make_pair(cend(), Degree::min());
    }

    Degree max{Degree::min()};
    const_iterator cit;

    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        Degree tmp{degree(it)};
        if (max < tmp) {
            max = tmp;
            cit = it;
        }
    }

    return std::make_pair(cit, max);
}

template <class Key, class T, class Cost, Nature Nat>
std::pair<typename graph<Key, T, Cost, Nat>::const_iterator, typename graph<Key, T, Cost, Nat>::Degree> graph<Key, T, Cost, Nat>::degree_min() const {
    if (empty()) {
        return std::make_pair(cend(), Degree::min());
    }

    Degree min{Degree::max()};
    const_iterator cit;

    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        Degree tmp{degree(it)};
        if (tmp < min) {
            min = tmp;
            cit = it;
        }
    }

    return std::make_pair(cit, min);
}

template <class Key, class T, class Cost, Nature Nat>
std::map<Key, typename graph<Key, T, Cost, Nat>::Degree> graph<Key, T, Cost, Nat>::degrees() const {
    std::map<key_type, Degree> result;

    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        result.insert(std::make_pair(it->first, degree(it)));
    }

    return result;
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_in_edges(const_iterator to) const {
    std::vector<typename node::edge> result;

    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        if (it != to) {
            for (typename node::edge e : it->second->_out_edges) {
                if (e.target() == to) {
                    result.push_back(e);
                }
            }
        }
    }

    return result;
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_in_edges(const key_type &to) const {
    return get_in_edges(find(to));
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_out_edges(const_iterator from) const {
    return std::vector<typename node::edge>(from->second->_out_edges.begin(), from->second->_out_edges.end());
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_out_edges(const key_type &from) const {
    return get_out_edges(find(from));
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_edges(const_iterator i) const {
    return std::vector<typename node::edge>(i->second->_out_edges.begin(), i->second->_out_edges.end());
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
std::vector<typename graph<Key, T, Cost, Nat>::node::edge> graph<Key, T, Cost, Nat>::get_edges(const key_type &i) const {
    return get_edges(find(i));
}

template <class Key, class T, class Cost, Nature Nat>
template <class>
bool graph<Key, T, Cost, Nat>::is_cyclic() const {
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        std::list<const_iterator> initPath;
        if (is_cyclic_rec(it, initPath)) {
            return true;
        }
    }
    return false;
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::is_cyclic_rec(const_iterator current, std::list<const_iterator> path) const {
    for (const_iterator it : path) {
        if (it == current && (get_nature() == DIRECTED || path.back() != current)) {
            return true;
        }
    }
    /*if (std::find(path.cbegin(), path.cend(), current) != path.cend()) {
        return true;
    }*/

    path.push_back(current);
    std::vector<typename node::edge> adjacent;
    if (get_nature() == DIRECTED) {
        adjacent = get_out_edges(current);
    } else {
        adjacent = get_edges(current);
    }

    for (typename std::vector<typename node::edge>::const_iterator it{adjacent.cbegin()}; it != adjacent.cend(); ++it) {
        if (is_cyclic_rec(it->target(), path)) {
            return true;
        }
        path.remove(it->target());
    }

    return false;
}

/*
template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::is_isomorphic() const {
    // TODO
}

template <class Key, class T, class Cost, Nature Nat>
std::vector<typename graph<Key, T, Cost, Nat>::const_iterator> graph<Key, T, Cost, Nat>::toposort() const {
    // TODO
}

template <class Key, class T, class Cost, Nature Nat>
std::set<std::vector<typename graph<Key, T, Cost, Nat>::const_iterator>, typename graph<Key, T, Cost, Nat>::iterator_comparator> graph<Key, T, Cost, Nat>::kosaraju_scc() const {
    // TODO
}

template <class Key, class T, class Cost, Nature Nat>
std::set<std::vector<typename graph<Key, T, Cost, Nat>::const_iterator>, typename graph<Key, T, Cost, Nat>::iterator_comparator> graph<Key, T, Cost, Nat>::tarjan_scc() const {
    // TODO
}

template <class Key, class T, class Cost, Nature Nat>
std::size_t graph<Key, T, Cost, Nat>::connected_components() const {
    // TODO
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat> &graph<Key, T, Cost, Nat>::condensate(bool make_acyclic) {
    // TODO
}
*/

//template <class Key, class T, class Cost, Nature Nat>
//std::vector<typename graph<Key, T, Cost, Nat>::const_iterator> graph<Key, T, Cost, Nat>::maximum_clique() const {
// TODO: fix the bug

/*
std::function<size_type(const_iterator)> heuristic = [](const_iterator it) -> size_type { return it->second->degree().first; };
std::function<size_type(const_iterator, const_iterator)> comparator = [&heuristic](const_iterator it1, const_iterator it2) -> size_type { return heuristic(it1) > heuristic(it2); };
std::list<const_iterator> Q;
for (const_iterator it{cbegin()}; it != cend(); ++it) {
    Q.emplace_back(it);
}
//std::copy(cbegin(), cend(), std::back_inserter(Q));
Q.sort(comparator);

std::vector<const_iterator> result;
std::function<size_type()> calculate_max_size = [&Q, &heuristic]() -> size_type {
    for (size_type degree{heuristic(*Q.cbegin())}; degree > 0; --degree) {
        if (std::count_if(Q.cbegin(), Q.cend(), [degree, &heuristic](const_iterator it) -> bool {
        return heuristic(it) >= degree;
        }) >= degree) {
            return degree + 1;
        }
    }
    return 0;
};
size_type max_size{calculate_max_size()};

while (!Q.empty() && result.size() <= max_size) {
    // DEBUG
    std::cout << "Values inside Q: ";
    for (const_iterator I : Q) {
        std::cout << I->first << " ";
    }
    std::cout << std::endl;

    const_iterator N{*Q.cbegin()};
    // DEBUG
    std::cout << "N: " << N->first << std::endl;
    std::vector<const_iterator> current_clique({N});

    // TODO: loop until neighbors of N { for each neighbor of N inside of Q { . . . }; };
    std::vector<typename node::edge> adj{get_out_edges(N)};
    for (typename std::vector<typename node::edge>::const_iterator edge{adj.cbegin()}; edge != adj.cend(); ++edge) {
        // DEBUG
        std::cout << "Values inside current_clique: ";
        for (const_iterator I : current_clique) {
            std::cout << I->first << " ";
        }
        std::cout << std::endl;

        const_iterator X{edge->target()};
        if (std::find(Q.cbegin(), Q.cend(), X) == Q.cend()) {
            continue;
        }

        bool part_of_clique{true};
        for (const_iterator it : current_clique) {
            if (!existing_edge(it, X)) {
                part_of_clique = false;
                break;
            }
        }
        if (part_of_clique) {
            current_clique.push_back(X);
        } else {
            if (result.size() < current_clique.size()) {
                result = current_clique;
                // DEBUG
                std::cout << "new clique discovered: size of " << result.size() << std::endl;
            }
            Q.remove(N);

            std::function<bool(const_iterator)> PAF = [&result, &heuristic](const_iterator it) -> bool {
                return heuristic(it) < result.size();
            };
            Q.erase(std::remove_if(Q.begin(), Q.end(), PAF), Q.cend());
            max_size = calculate_max_size();
        }
    }
    // DEBUG
    std::cout << std::endl;
}
return result;

// candidates <- sort each node in function of its degree
// max clique size <= degree_max() + 1

// current_clique_size = 0
// result = null
// for each node N in candidates
//      current_clique = {N}
//      for each neighbor X of N ordered by its degree
//              if (X linked with all nodes of current_clique) then
//                      current_clique += {X}
//              else
//                      if (result.size < current_clique.size)
//                              result = current_clique
//                      candidates -= {N}
//                      for each node M in candidates
//                              if (M.degree <= result.size)
//                                      candidates -= {M}

// clique = NULL
// candidate = X (nodes of graph / candidate != NULL do
//                                      choose xi wih degree max
//                                      clique <- clique U {xi}
//                                      candidate <- candidats ∧ { xj / (xj, xi) € A} (intersection of candidate and neighbors of xi)
*/
//}

template <class Key, class T, class Cost, Nature Nat>
std::ostream &operator<<(std::ostream &os, const graph<Key, T, Cost, Nat> &g) {
    return os << *g.generate_grp() << std::endl;
    //return os << std::setw(4) << *g.generate_json() << std::endl;
}

template <class Key, class T, class Cost, Nature Nat>
std::istream &operator>>(std::istream &is, graph<Key, T, Cost, Nat> &g) {
    GRAPH_TRY {
        g.parse_from_grp(is);
    } GRAPH_CATCH (...) {

        GRAPH_THROW_WITH(parse_error, 0, "istream corrupted, fail to parse the graph")

    }

    return is;
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::load(const char* filename) {
    const char* dot = strrchr(filename, '.');
    std::string extension;
    if (dot != nullptr && dot != filename) {
        extension = dot + 1;
    }

    std::ifstream in(filename);
    if (!in) {
        GRAPH_THROW_WITH(invalid_argument, ("Unexistant file: '" + std::string(filename) + "'").c_str())
    }

    if (extension == "json") {
        parse_from_json(in);
    } else if (extension == "dot") {
        GRAPH_THROW_WITH(invalid_argument, "Load from DOT file non supported yet")
    } else {
        GRAPH_TRY {
            parse_from_grp(in);
        } GRAPH_CATCH (exception & e) {
            std::cerr << "Fail to load the file '" << filename << "'; wrong extension or corrupted file." << std::endl;
        }
    }
    in.close();
}

template <class Key, class T, class Cost, Nature Nat>
std::unique_ptr<std::string> graph<Key, T, Cost, Nat>::generate_dot(const std::string &graph_name) const {
    std::string dot;

    const std::string tab{"    "};

    /// Displaying nature + graph name
    if (graph_name.find_first_not_of("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_-") != std::string::npos) {
        GRAPH_THROW_WITH(invalid_argument, "Wrong graph name given; accepted characters: [a-zA-Z0-9_-]")
    }

    if (get_nature() == DIRECTED) {
        dot += "di";
    }
    dot += "graph ";
    if (!graph_name.empty()) {
        dot += graph_name + " ";
    }
    dot += "{\n";

    /// Displaying nodes' name
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        std::stringstream ss;
        ss << it->first;
        dot += tab + ss.str() + "\n";
    }

    if (get_nature() == DIRECTED) {
        for_each(cbegin(), cend(), [this, &dot, tab](const value_type & element) {
            std::list<typename node::edge> child{element.second->get_edges()};
            for_each(child.cbegin(), child.cend(), [this, &dot, tab, &element](const typename node::edge & i) {
                if (i.cost() != infinity) {
                    std::stringstream ss;
                    ss << tab << element.first << " -> " << i.target()->first << '\n';
                    dot += ss.str();
                }
            });
        });
    } else {
        std::set<std::pair<Key, Key >> list_edges;
        for_each(cbegin(), cend(), [this, &dot, &list_edges](const value_type & element) {
            std::list<typename node::edge> child{element.second->get_edges()};
            for_each(child.cbegin(), child.cend(), [&dot, &list_edges, &element](const typename node::edge & i) {
                const Key min{std::min(element.first, i.target()->first)};
                const Key max{std::max(element.first, i.target()->first)};
                list_edges.emplace(std::make_pair(min, max));
            });
        });

        for_each(list_edges.cbegin(), list_edges.cend(), [&dot, tab](const std::pair<Key, Key> &p) {
            std::stringstream ss;
            ss << tab << p.first << " -- " << p.second << '\n';
            dot += ss.str();
        });
    }
    dot += '}';

    return std::make_unique<std::string>(std::forward<std::string>(dot));
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::save_to_dot(const char* filename, const std::string &graph_name) const {
    std::ofstream out(filename);
    out << *generate_dot(graph_name) << std::endl;
    out.close();
}

template <class Key, class T, class Cost, Nature Nat>
std::unique_ptr<nlohmann::json> graph<Key, T, Cost, Nat>::generate_json() const {
    nlohmann::json json;

    using Set = std::list<typename node::edge>;

    json["nature"] = get_nature();

    size_type n{0};
    for (const_iterator node{cbegin()}; node != cend(); ++node, ++n) {
        json["nodes"][n]["key"]   = node->first;
        json["nodes"][n]["value"] = node->second->get();
    }

    size_type p{0};
    for (const_iterator node{cbegin()}; node != cend(); ++node) {
        Set child{node->second->get_edges()};
        for (typename Set::const_iterator edge{child.begin()}; edge != child.end(); ++edge, ++p) {
            json["edges"][p]["from"] = node->first;
            json["edges"][p]["to"]   = edge->target()->first;
            json["edges"][p]["cost"] = edge->cost();
        }
    }
    return std::make_unique<nlohmann::json>(std::forward<nlohmann::json>(json));
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::save_to_json(const char* filename) const {
    std::ofstream out(filename);
    out << std::setw(4) << *generate_json() << std::endl;
    out.close();
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::parse_from_json(std::istream &is) {
    nlohmann::json json;
    is >> json;

    if (static_cast<Nature>(json["nature"]) != get_nature()) {
        std::string error_msg{"Bad graph nature (expected '"};
        error_msg += (Nat == DIRECTED ? "graph')" : "digraph')");
        GRAPH_THROW_WITH(invalid_argument, error_msg.c_str())
    }

    clear();
    for (const nlohmann::json &node : json["nodes"]) {
        key_type k = node["key"];
        graphed_type x = node["value"];
        add_node(k, x);
    }
    for (const nlohmann::json &edge : json["edges"]) {
        key_type from = edge["from"];
        key_type to = edge["to"];
        cost_type c;
        if (edge["cost"].is_null()) {
            c = infinity;
        } else {
            c = edge["cost"];
        }
        add_edge(from, to, c);
    }
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::DEBUG_load_from_json_rust(const char* path) {
    nlohmann::json json;
    std::ifstream is(path);
    if (!is) {
        std::cerr << "Unexistent file '" << path << "'!" << std::endl;
        exit(1);
    }
    is >> json;

    clear();
    for (const nlohmann::json &node : json["nodes"]) {
        add_node(node);
    }

    for (const nlohmann::json &edge : json["edges"]) {
        const_iterator begin{std::next(cbegin(), edge[0])};
        const_iterator end  {std::next(cbegin(), edge[1])};
        add_edge(begin, end);
    }
}

template <class Key, class T, class Cost, Nature Nat>
std::unique_ptr<std::string> graph<Key, T, Cost, Nat>::generate_grp() const {
    using std::max;
    using std::ostringstream;
    using std::setw;
    using std::string;
    using std::stringstream;

    const auto tab{string(4, ' ')};

    string data;

    /// Displaying nature + graph types
    if (get_nature() == DIRECTED) {
        data += "di";
    }

    data += "graph<" + detail::type_name<Key>() + ", " +
            detail::type_name<graphed_type>() + ", " +
            detail::type_name<cost_type>() + "> {\n" +
            tab + "nodes: {\n";

    /// Displaying nodes:  "<name>"; "<value>",
    size_type max_size{3};
    for_each(cbegin(), cend(), [&max_size](const value_type & element) {
        ostringstream out;
        out << element.first;
        const size_type size{static_cast<size_type>(out.tellp())};

        max_size = max(max_size, size);
    });

    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        ostringstream out;
        out << it->first << "\",";

        stringstream ss;
        ss << tab << tab
           << '"' << std::left << setw(static_cast<int>(max_size + 3)) << out.str()
           << '"' << it->second->get() << '"';
        data += ss.str();

        if (it != --cend()) {
            data += ";";
        }
        data += "\n";
    }
    data += tab + "}";

    /// Displaying edges:  "<node 1>"; "<node 2>"; "<cost>",
    if (get_nbr_edges() == 0) {
        data += "\n}";
    } else {
        data += ",\n" + tab + "edges: {\n";
        size_type max_size_1{0}, max_size_2{0};

        for_each(cbegin(), cend(), [&max_size_1, &max_size_2, this](const value_type & element) {
            std::list<typename node::edge> child{element.second->get_edges()};
            for_each(child.cbegin(), child.cend(), [ &, this](const typename node::edge & i) {
                ostringstream out_1, out_2;
                out_1 << element.first;
                out_2 << i.target()->first;

                const size_type size_1{static_cast<size_type>(out_1.tellp())};
                const size_type size_2{static_cast<size_type>(out_2.tellp())};

                max_size_1 = max(max_size_1, size_1);
                max_size_2 = max(max_size_2, size_2);
            });
        });

        size_type p{0};
        for_each(cbegin(), cend(), [this, &data, &p, tab, max_size_1, max_size_2](const value_type & element) {
            std::list<typename node::edge> child{element.second->get_edges()};
            for_each(child.cbegin(), child.cend(), [this, &data, &p, tab, &element, max_size_1, max_size_2](const typename node::edge & i) {
                ostringstream out_1, out_2;
                out_1 << '"' << element.first     << "\",";
                out_2 << '"' << i.target()->first << "\",";

                stringstream ss;
                ss << std::left << tab << tab
                   << setw(static_cast<int>(max_size_1 + 4)) << out_1.str()
                   << setw(static_cast<int>(max_size_2 + 4)) << out_2.str();
                if (i.cost() == infinity) {
                    ss << "infinity";
                } else {
                    ss << '"' << i.cost() << '"';
                }

                if (p < (this->get_nature() == DIRECTED ?
                         this->get_nbr_edges() : 2 * this->get_nbr_edges()) - 1) {
                    ss << ';';
                }
                ss << '\n';
                data += ss.str();
                p++;
            });
        });
        data += tab + "}\n}";
    }

    return std::make_unique<std::string>(std::forward<std::string>(data));
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::save_to_grp(const char* filename) const {
    std::ofstream out(filename);
    out << *generate_grp() << std::endl;
    out.close();
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::parse_from_grp(std::istream &is) {
    /// Nature
    std::string line;
    getline(is, line);
    if (line.substr(0, 5) == "graph") {
        if (get_nature() != UNDIRECTED) {
            GRAPH_THROW_WITH(invalid_argument, "Bad graph nature (expected 'graph')")
        }
    } else if (line.substr(0, 7) == "digraph") {
        if (get_nature() != DIRECTED) {
            GRAPH_THROW_WITH(invalid_argument, "Bad graph nature (expected 'digraph')")
        }
    } else {
        GRAPH_THROW_WITH(parse_error, is.tellg(), "Bad graph nature (expected '[di]graph')")
    }

    /// Nodes
    getline(is, line);
    if (line != "    nodes: {") {
        GRAPH_THROW_WITH(parse_error, is.tellg(), "Bad format for nodes")
    }

    clear();
    while (getline(is, line) && line.find('}') == std::string::npos) {
        std::istringstream iss{line};
        Key key;
        T value;
        detail::read_T(iss, key);
        detail::read_T(iss, value);

        add_node(key, value);
    }

    /// Edges
    getline(is, line);
    if (line == "}") {}
    else if (line != "    edges: {") {
        GRAPH_THROW_WITH(parse_error, is.tellg(), "Bad format for edges")
    } else {
        while (getline(is, line) && line.find('}') == std::string::npos) {
            std::istringstream iss{line};
            key_type from;
            key_type to;
            cost_type cost;
            detail::read_T(iss, from);
            detail::read_T(iss, to);
            detail::read_cost(iss, cost);

            add_edge(from, to, cost);
        }

        getline(is, line);
        if (line != "}") {
            GRAPH_THROW_WITH(parse_error, is.tellg(), "Bad format at the end of the graph")
        }
    }
}

template <class Key, class T, class Cost, Nature Nat>
template <class K, class D, class C, Nature N>
bool graph<Key, T, Cost, Nat>::operator==(const graph<K, D, C, N> &other) const noexcept {
    typedef typename graph<Key, T, Cost, Nat>::const_iterator Iterator1;
    typedef typename graph<K, D, C, N>::const_iterator Iterator2;

    typedef typename graph<Key, T, Cost, Nat>::node::edge Edge1;
    typedef typename graph<K, D, C, N>  ::node::edge Edge2;

    if (get_nature()        != other.get_nature()    ||
            get_nbr_nodes() != other.get_nbr_nodes() ||
            get_nbr_edges() != other.get_nbr_edges()) {
        return false;
    }

    Iterator1 it1{cbegin()};
    Iterator2 it2{other.cbegin()};

    for (; (it1 != cend() || it2 != other.cend()); ++it1, ++it2) {
        /// Test nodes value
        if (!(it1->first                == it2->first)         ||
                !(it1->second->get()    == it2->second->get()) ||
                !(it1->second->degree() == it2->second->degree())) {
            return false;
        }

        /// Test out edges
        std::list<Edge1> edges1{it1->second->get_edges()};
        std::list<Edge2> edges2{it2->second->get_edges()};

        std::map<Key, Edge1> child1;
        std::map<Key, Edge2> child2;

        std::transform(edges1.begin(), edges1.end(), std::inserter(child1, child1.end()), [](const Edge1 & e) {
            return std::make_pair(e.target()->first, e);
        });
        std::transform(edges2.begin(), edges2.end(), std::inserter(child2, child2.end()), [](const Edge2 & e) {
            return std::make_pair(e.target()->first, e);
        });

        typename std::map<Key, Edge1>::const_iterator edge1{child1.cbegin()};
        typename std::map<Key, Edge2>::const_iterator edge2{child2.cbegin()};

        for (; (edge1 != child1.cend() || edge2 != child2.cend()); ++edge1, ++edge2) {
            Iterator1 target1{edge1->second.target()};
            Iterator2 target2{edge2->second.target()};

            if (!(target1->first == target2->first && edge1->second.cost() == edge2->second.cost())) {
                return false;
            }
        }
    }

    return true;
}

template <class Key, class T, class Cost, Nature Nat>
template <class K, class D, class C, Nature N>
bool graph<Key, T, Cost, Nat>::operator!=(const graph<K, D, C, N> &other) const noexcept {
    return !(*this == other);
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::node::node() : node(graphed_type()) {}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::node::node(const graphed_type &d) {
    this->_data = d;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::node &graph<Key, T, Cost, Nat>::node::operator=(const graphed_type &d) {
    this->set(d);
    return *this;
}

template <class Key, class T, class Cost, Nature Nat>
void graph<Key, T, Cost, Nat>::node::set_iterator_values(iterator this_, iterator end, const_iterator cend) {
    this->container_from_this = this_;
    this->end_container       = end;
    this->cend_container      = cend;
}

template <class Key, class T, class Cost, Nature Nat>
template <bool insertFront>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::abstract_first_search(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    std::list<const_iterator> expanded;
    std::deque<search_path> frontier;

    {
        search_path p;
        p.push_back({start, cost_type()});
        frontier.push_front(std::move(p));
    }

    while (!frontier.empty()) {
        search_path p{frontier.front()};
        frontier.pop_front();

        if (std::find(expanded.cbegin(), expanded.cend(), p.back().first) == expanded.end()) {
            const_iterator last{p.back().first};
            expanded.push_back(last);

            if (is_goal(last)) {
                return p;
            }

            std::vector<typename node::edge> legalActions{get_nature() == DIRECTED ? get_out_edges(last) : get_edges(last)};

            for (typename std::vector<typename node::edge>::const_iterator it{legalActions.cbegin()}; it != legalActions.cend(); ++it) {
                search_path newPath{p};
                newPath.push_back({it->target(), it->cost()});
                if (insertFront) {
                    frontier.push_front(newPath);
                } else {
                    frontier.push_back(newPath);
                }
            }
        }
    }

    search_path empty = {};
    return empty;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(key_type start, Key target) const {
    std::list<const_iterator> l;
    l.emplace_back(find(target));
    return bfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(key_type start, std::list<key_type> target_list) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return bfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(key_type start, std::function<bool(key_type)> is_goal) const {
    return bfs(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(const_iterator start, const_iterator target) const {
    std::list<const_iterator> l;
    l.emplace_back(target);
    return bfs(start, l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(const_iterator start, std::list<const_iterator> target_list) const {
    return bfs(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::bfs(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    return abstract_first_search<false>(start, is_goal);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(key_type start, Key target) const {
    std::list<const_iterator> l;
    l.emplace_back(find(target));
    return dfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(key_type start, std::list<key_type> target_list) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return dfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(key_type start, std::function<bool(key_type)> is_goal) const {
    return dfs(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(const_iterator start, const_iterator target) const {
    std::list<const_iterator> l;
    l.emplace_back(target);
    return dfs(start, l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(const_iterator start, std::list<const_iterator> target_list) const {
    return dfs(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dfs(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    return abstract_first_search<true>(start, is_goal);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(key_type start, Key target, size_type depth) const {
    std::list<const_iterator> l;
    l.emplace_back(find(target));
    return dls(find(start), l, depth);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(key_type start, std::list<key_type> target_list, size_type depth) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return dls(find(start), l, depth);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(key_type start, std::function<bool(key_type)> is_goal, size_type depth) const {
    return dls(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    }, depth);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(const_iterator start, const_iterator target, size_type depth) const {
    std::list<const_iterator> l;
    l.emplace_back(target);
    return dls(start, l, depth);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(const_iterator start, std::list<const_iterator> target_list, size_type depth) const {
    return dls(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); }, depth);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::dls(const_iterator start, std::function<bool(const_iterator)> is_goal, size_type depth) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    std::list<const_iterator> expanded;
    std::deque<search_path> frontier;

    {
        search_path p;
        p.push_back({start, cost_type()});
        frontier.push_front(std::move(p));
    }

    int l{0};
    while (!frontier.empty() && l < depth) {
        search_path p{frontier.front()};
        frontier.pop_front();

        if (std::find(expanded.cbegin(), expanded.cend(), p.back().first) == expanded.end()) {
            const_iterator last{p.back().first};
            expanded.push_back(last);

            if (is_goal(last)) {
                return p;
            }

            std::vector<typename node::edge> legalActions{get_nature() == DIRECTED ? get_out_edges(last) : get_edges(last)};

            for (typename std::vector<typename node::edge>::const_iterator it{legalActions.cbegin()}; it != legalActions.cend(); ++it) {
                search_path newPath{p};
                newPath.push_back({it->target(), it->cost()});
                frontier.push_front(newPath);
            }
        }
        ++l;
    }

    search_path empty = {};
    return empty;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(key_type start, Key target) const {
    std::list<const_iterator> l;
    l.emplace_back(find(target));
    return iddfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(key_type start, std::list<key_type> target_list) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return iddfs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(key_type start, std::function<bool(key_type)> is_goal) const {
    return iddfs(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(const_iterator start, const_iterator target) const {
    std::list<const_iterator> l;
    l.emplace_back(target);
    return iddfs(start, l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(const_iterator start, std::list<const_iterator> target_list) const {
    return iddfs(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::iddfs(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    for (size_type i{0}; i < std::numeric_limits<size_type>::max(); ++i) {
        const search_path found{dls(start, is_goal, i)};
        if (!found.empty()) {
            return found;
        }
    }
    search_path empty = {};
    return empty;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(key_type start, Key target) const {
    std::list<const_iterator> l;
    l.emplace_back(find(target));
    return ucs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(key_type start, std::list<key_type> target_list) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return ucs(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(key_type start, std::function<bool(key_type)> is_goal) const {
    return ucs(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(const_iterator start, const_iterator target) const {
    std::list<const_iterator> l;
    l.emplace_back(target);
    return ucs(start, l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(const_iterator start, std::list<const_iterator> target_list) const {
    return ucs(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::ucs(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    std::list<const_iterator> expanded;
    std::priority_queue<search_path, std::vector<search_path>, path_comparator> frontier((path_comparator([](const_iterator) {
        return cost_type();
    })));

    {
        search_path p;
        p.push_back({start, cost_type()});
        frontier.push(std::move(p));
    }

    while (!frontier.empty()) {
        search_path p{frontier.top()};
        frontier.pop();

        if (std::find(expanded.cbegin(), expanded.cend(), p.back().first) == expanded.end()) {
            const_iterator last{p.back().first};
            expanded.push_back(last);

            if (is_goal(last)) {
                return p;
            }

            std::vector<typename node::edge> legalActions{get_nature() == DIRECTED ? get_out_edges(last) : get_edges(last)};

            for (typename std::vector<typename node::edge>::const_iterator it{legalActions.cbegin()}; it != legalActions.cend(); ++it) {
                search_path newPath{p};
                newPath.push_back({it->target(), it->cost()});
                frontier.push(newPath);
            }
        }
    }

    search_path empty = {};
    return empty;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(key_type start, Key target, std::function<cost_type(const_iterator)> heuristic) const {
    const_iterator it{this->find(target)};
    return astar(find(start), [ &it](const_iterator node) -> bool { return it == node; }, heuristic);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(key_type start, std::list<key_type> target_list, std::function<cost_type(const_iterator)> heuristic) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return astar(find(start), l, heuristic);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(key_type start, std::function<bool(key_type)> is_goal, std::function<cost_type(const_iterator)> heuristic) const {
    return astar(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    }, heuristic);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(const_iterator start, const_iterator target, std::function<cost_type(const_iterator)> heuristic) const {
    return astar(start, [ &target](const_iterator node) -> bool { return target == node; }, heuristic);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(const_iterator start, std::list<const_iterator> target_list, std::function<cost_type(const_iterator)> heuristic) const {
    return astar(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); }, heuristic);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::astar(const_iterator start, std::function<bool(const_iterator)> is_goal, std::function<cost_type(const_iterator)> heuristic) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    const cost_type nul_cost{cost_type()};

    std::list<const_iterator> expanded;
    std::priority_queue<search_path, std::vector<search_path>, path_comparator> frontier((path_comparator(heuristic)));

    {
        search_path p;
        p.push_back({start, nul_cost});
        frontier.push(std::move(p));
    }

    while (!frontier.empty()) {
        search_path p{frontier.top()};
        frontier.pop();

        if (std::find(expanded.cbegin(), expanded.cend(), p.back().first) == expanded.end()) {
            const_iterator last{p.back().first};
            expanded.push_back(last);

            if (is_goal(last)) {
                return p;
            }

            std::vector<typename node::edge> legalActions{get_nature() == DIRECTED ? get_out_edges(last) : get_edges(last)};

            for (typename std::vector<typename node::edge>::const_iterator it{legalActions.cbegin()}; it != legalActions.cend(); ++it) {
                /// Dijkstra's algorithm cannot be computed with negative weights.
                if (it->cost() < nul_cost) {
                    GRAPH_THROW(negative_edge)
                }

                search_path newPath{p};
                newPath.push_back({it->target(), it->cost()});
                frontier.push(newPath);
            }
        }
    }

    search_path empty = {};
    return empty;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(key_type start) const {
    return dijkstra(find(start), [](const_iterator) {
        return false;
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(key_type start, key_type target) const {
    const_iterator it{this->find(target)};
    return dijkstra(find(start), [ &it](const_iterator node) -> bool { return it == node; });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(key_type start, std::list<key_type> target_list) const {
    std::list<const_iterator> l;
    for (key_type k : target_list) {
        l.emplace_back(find(k));
    }
    return dijkstra(find(start), l);
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(key_type start, std::function<bool(key_type)> is_goal) const {
    return dijkstra(find(start), [ &is_goal](const_iterator it) {
        return is_goal(it->first);
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(const_iterator start) const {
    return dijkstra(start, [](const_iterator) {
        return false;
    });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(const_iterator start, const_iterator target) const {
    return dijkstra(start, [ &target](const_iterator node) -> bool { return target == node; });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(const_iterator start, std::list<const_iterator> target_list) const {
    return dijkstra(start, [ &target_list](const_iterator node) -> bool { return std::find(target_list.cbegin(), target_list.cend(), node) != target_list.cend(); });
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::dijkstra(const_iterator start, std::function<bool(const_iterator)> is_goal) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    struct pair_iterator_comparator {
        bool operator()(const std::pair<const_iterator, cost_type> &lhs, const std::pair<const_iterator, cost_type> &rhs) const {
            return lhs.second < rhs.second;
        }
    };

    /// Initialization

    const cost_type nul_cost{cost_type()};
    std::priority_queue<std::pair<const_iterator, cost_type>, std::vector<std::pair<const_iterator, cost_type >>, pair_iterator_comparator> Q;

    shortest_paths result(start);
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        result.emplace(it, std::make_pair(cend(), infinity));
    }
    Q.emplace(start, nul_cost);

    typename shortest_paths::iterator S{result.find(start)};
    S->second.first = start;
    S->second.second = nul_cost;

    /// Dijkstra's algorithm

    while (!Q.empty()) {
        const_iterator u{Q.top().first};
        Q.pop();

        if (is_goal(u)) {
            break;
        }

        std::vector<typename node::edge> adj{get_out_edges(u)};
        for (typename std::vector<typename node::edge>::const_iterator edge{adj.cbegin()}; edge != adj.cend(); ++edge) {
            const_iterator v{edge->target()};

            cost_type cost{u->second->get_cost(v)};
            /// Dijkstra's algorithm cannot be computed with negative weights.
            if (cost < nul_cost) {
                GRAPH_THROW(negative_edge)
            }

            cost_type dist_u{result[u].second};
            cost_type dist_v{result[v].second};

            cost_type alt{dist_u + cost};

            if (alt < dist_v) {
                result[v].first = u;
                result[v].second = alt;
                Q.emplace(v, alt);
            }
        }
    }

    return result;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::bellman_ford(key_type start) const {
    return bellman_ford(find(start));
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::shortest_paths graph<Key, T, Cost, Nat>::bellman_ford(const_iterator start) const {
    if (start == cend()) {
        GRAPH_THROW_WITH(invalid_argument, "Start point equals to graph::cend()")
    }

    /// Initialization

    shortest_paths result(start);
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        result.emplace(it, std::make_pair(cend(), infinity));
    }

    typename shortest_paths::iterator S{result.find(start)};
    S->second.first = start;
    S->second.second = cost_type();

    /// Relax edges repeatedly

    bool finished{false};
    for (size_type i{0}; i < get_nbr_edges() - 1 && !finished; ++i) {
        finished = true;

        for (const_iterator u{cbegin()}; u != cend(); ++u) {
            std::vector<typename node::edge> adj{get_out_edges(u)};
            for (typename std::vector<typename node::edge>::const_iterator edge{adj.cbegin()}; edge != adj.cend(); ++edge) {
                const_iterator v{edge->target()};

                cost_type cost{u->second->get_cost(v)};
                cost_type dist_u{result[u].second};
                cost_type dist_v{result[v].second};

                cost_type alt{dist_u + cost};

                if (alt < dist_v) {
                    result[v].first = u;
                    result[v].second = alt;
                    finished = false;
                }
            }
        }
    }

    /// Check for negative-weigh cycles

    for (const_iterator u{cbegin()}; u != cend(); ++u) {
        std::vector<typename node::edge> adj{get_out_edges(u)};
        for (typename std::vector<typename node::edge>::const_iterator edge{adj.cbegin()}; edge != adj.cend(); ++edge) {
            const_iterator v{edge->target()};
            if (result[u].second + u->second->get_cost(v) < result[v].second) {
                GRAPH_THROW(negative_weight_cycle)
            }
        }
    }

    return result;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::search_path::search_path(const search_path &p) : Container(p) {}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::cost_type graph<Key, T, Cost, Nat>::search_path::total_cost() const {
    cost_type total{};
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        total += it->second;
    }
    return total;
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::search_path::contain(const graph::const_iterator &i) const {
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        if (it->first == i) {
            return true;
        }
    }
    return false;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::shortest_paths::shortest_paths(graph::const_iterator start) : _start(start) {}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::shortest_paths::shortest_paths(const shortest_paths &p) : Container(p), _start(p._start) {}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::const_iterator graph<Key, T, Cost, Nat>::shortest_paths::get_previous(graph::const_iterator current) const {
    return this->find(current)->second.first;
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::shortest_paths::get_path(graph::key_type target) const {
    for (const_iterator it{cbegin()}; it != cend(); ++it) {
        if (it->first->first == target) {
            return get_path(it->first);
        }
    }
    return graph::search_path();
}

template <class Key, class T, class Cost, Nature Nat>
typename graph<Key, T, Cost, Nat>::search_path graph<Key, T, Cost, Nat>::shortest_paths::get_path(graph::const_iterator target) const {
    graph::shortest_paths::const_iterator current{this->find(target)};
    if (current == cend() || current->second.second == (std::numeric_limits<cost_type>::has_infinity ? std::numeric_limits<cost_type>::infinity() : std::numeric_limits<cost_type>::max())) {
        return search_path();
    }

    graph::search_path result;
    graph::shortest_paths::const_iterator previous{this->find(current->second.first)};

    while (previous != cend() && current->first != _start) {
        result.emplace_front(current->first, current->second.second - previous->second.second);
        current = previous;
        previous = this->find(current->second.first);
    }

    if (target != _start) {
        result.emplace_front(_start, cost_type());
    }

    return result;
}

template <class Key, class T, class Cost, Nature Nat>
graph<Key, T, Cost, Nat>::path_comparator::path_comparator(std::function<cost_type(const_iterator)> heuristic) : _heuristic(heuristic) {}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::path_comparator::operator() (const search_path &p1, const search_path &p2) const {
    return (p2.total_cost() + _heuristic(p2.back().first)) < (p1.total_cost() + _heuristic(p1.back().first));
}

template <class Key, class T, class Cost, Nature Nat>
bool graph<Key, T, Cost, Nat>::iterator_comparator::operator()(const const_iterator &lhs, const const_iterator &rhs) const {
    return lhs->first < rhs->first;
}

#endif