graph.hpp

Go to the documentation of this file.

#pragma once
 
#if !__has_include(<boost/graph/adjacency_list.hpp>)
#error "FATAL: nxpp requires the Boost Graph Library (BGL)."
#endif
 
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#include <boost/graph/adjacency_list.hpp>
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
#include <functional>
#include <vector>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <string>
#include <algorithm>
#include <cmath>
#include <concepts>
#include <utility>
#include <any>
#include <map>
#include <optional>
#include <limits>
#include <set>
#include <initializer_list>
 
namespace nxpp {
 
template <typename T>
concept ValidNodeID =
    std::copy_constructible<T> &&
    std::equality_comparable<T> &&
    requires(const T& lhs, const T& rhs) {
        { std::less<T>{}(lhs, rhs) } -> std::convertible_to<bool>;
    };
 
template <typename T>
concept NumericNodeID = ValidNodeID<T> && std::constructible_from<T, std::size_t>;
 
template <
    typename NodeID = std::string,
    typename EdgeWeight = double,
    bool Directed = false,
    bool Multi = false,
    bool Weighted = true,
    typename OutEdgeSelector = boost::vecS,
    typename VertexSelector = boost::vecS
>
class Graph;
 
namespace detail {
 
template <typename GraphWrapper>
struct MinCostFlowCacheHooks {
    static void invalidate(const void*) {}
    static void clear(const void*) {}
};
 
} // namespace detail
 
} // namespace nxpp
 
namespace boost {
 
// This is an intentional BGL extension point. BGL custom vertex properties are
// installed globally in namespace boost, so keep the nxpp-specific name stable
// and close to the wrapper storage that relies on it.
enum vertex_wrapper_index_t { vertex_wrapper_index };
BOOST_INSTALL_PROPERTY(vertex, wrapper_index);
static_assert(
    std::is_same_v<
        property_kind<vertex_wrapper_index_t>::type,
        vertex_property_tag
    >,
    "nxpp Boost property extension must install vertex_wrapper_index_t as a vertex property"
);
 
} // namespace boost
 
namespace nxpp {
 
template <typename GraphType, bool HasWeight>
struct built_in_weight_traits;
 
template <typename GraphType>
struct built_in_weight_traits<GraphType, true> {
    using map_type = typename boost::property_map<GraphType, boost::edge_weight_t>::type;
 
    static map_type get(GraphType& g) {
        return boost::get(boost::edge_weight, g);
    }
};
 
template <typename GraphType>
struct built_in_weight_traits<GraphType, false> {
    struct map_type {};
 
    static map_type get(GraphType&) {
        return {};
    }
};
 
enum class WeightMode {
    Unweighted,
    BuiltIn
};
 
template <typename Key, typename Value>
class lookup_map {
public:
    using storage_type = std::map<Key, Value>;
    using iterator = typename storage_type::iterator;
    using const_iterator = typename storage_type::const_iterator;
 
    Value& operator[](const Key& key) {
        return data[key];
    }
 
    [[nodiscard]] const Value& operator[](const Key& key) const {
        return data.at(key);
    }
 
    Value& at(const Key& key) {
        return data.at(key);
    }
 
    [[nodiscard]] const Value& at(const Key& key) const {
        return data.at(key);
    }
 
    iterator begin() { return data.begin(); }
    iterator end() { return data.end(); }
    const_iterator begin() const { return data.begin(); }
    const_iterator end() const { return data.end(); }
    const_iterator cbegin() const { return data.cbegin(); }
    const_iterator cend() const { return data.cend(); }
 
private:
    storage_type data;
};
 
template <typename Key, typename Value>
class indexed_lookup_map {
public:
    using storage_type = std::vector<std::pair<Key, Value>>;
    using iterator = typename storage_type::iterator;
    using const_iterator = typename storage_type::const_iterator;
 
    indexed_lookup_map() = default;
 
    void reserve(std::size_t count) {
        data.reserve(count);
    }
 
    void push_back(const Key& key, const Value& value) {
        data.emplace_back(key, value);
    }
 
    void push_back(const Key& key, Value&& value) {
        data.emplace_back(key, std::move(value));
    }
 
    Value& at(const Key& key) {
        auto it = find(key);
        if (it == data.end()) {
            throw std::out_of_range("indexed_lookup_map::at");
        }
        return it->second;
    }
 
    [[nodiscard]] const Value& at(const Key& key) const {
        auto it = find(key);
        if (it == data.end()) {
            throw std::out_of_range("indexed_lookup_map::at");
        }
        return it->second;
    }
 
    Value& operator[](const Key& key) {
        return at(key);
    }
 
    [[nodiscard]] const Value& operator[](const Key& key) const {
        return at(key);
    }
 
    [[nodiscard]] bool contains(const Key& key) const {
        return find(key) != data.end();
    }
 
    iterator find(const Key& key) {
        auto it = lower_bound_for(key);
        if (it == data.end() || key < it->first) {
            return data.end();
        }
        return it;
    }
 
    [[nodiscard]] const_iterator find(const Key& key) const {
        auto it = lower_bound_for(key);
        if (it == data.end() || key < it->first) {
            return data.end();
        }
        return it;
    }
 
    iterator begin() { return data.begin(); }
    iterator end() { return data.end(); }
    const_iterator begin() const { return data.begin(); }
    const_iterator end() const { return data.end(); }
    const_iterator cbegin() const { return data.cbegin(); }
    const_iterator cend() const { return data.cend(); }
 
    [[nodiscard]] bool empty() const { return data.empty(); }
    [[nodiscard]] std::size_t size() const { return data.size(); }
 
private:
    iterator lower_bound_for(const Key& key) {
        return std::lower_bound(
            data.begin(),
            data.end(),
            key,
            [](const auto& entry, const Key& value) { return entry.first < value; }
        );
    }
 
    const_iterator lower_bound_for(const Key& key) const {
        return std::lower_bound(
            data.begin(),
            data.end(),
            key,
            [](const auto& entry, const Key& value) { return entry.first < value; }
        );
    }
 
    storage_type data;
};
 
// Core Graph Class
 
template <
    typename NodeID,
    typename EdgeWeight,
    bool Directed,
    bool Multi,
    bool Weighted,
    typename OutEdgeSelector,
    typename VertexSelector
>
class Graph {
public:
    using NodeType = NodeID;
    using EdgeWeightType = EdgeWeight;
    using OutEdgeListSelector = OutEdgeSelector;
    using VertexListSelector = VertexSelector;
    using DirectedSelector = typename std::conditional<Directed, boost::bidirectionalS, boost::undirectedS>::type;
    using VertexProperty = boost::property<
        boost::vertex_name_t,
        NodeID,
        boost::property<boost::vertex_wrapper_index_t, std::size_t>
    >;
    using EdgeProperty = typename std::conditional<
        Weighted,
        boost::property<boost::edge_weight_t, EdgeWeight, boost::property<boost::edge_index_t, std::size_t>>,
        boost::property<boost::edge_index_t, std::size_t>
    >::type;
    using GraphType = boost::adjacency_list<OutEdgeSelector, VertexSelector, DirectedSelector,
                                            VertexProperty, EdgeProperty>;
    using VertexDesc = typename boost::graph_traits<GraphType>::vertex_descriptor;
    using EdgeDesc = typename boost::graph_traits<GraphType>::edge_descriptor;
    using WeightMap = typename built_in_weight_traits<GraphType, Weighted>::map_type;
    using VertexNameMap = typename boost::property_map<GraphType, boost::vertex_name_t>::type;
    using WrapperIndexMap = typename boost::property_map<GraphType, boost::vertex_wrapper_index_t>::type;
    using VertexIndexMap = WrapperIndexMap;
    using EdgeIdMap = typename boost::property_map<GraphType, boost::edge_index_t>::type;
    using IdMap = std::map<NodeID, VertexDesc>;
    using AttrMap = std::map<std::string, std::any>;
    using NodeAttrStorage = std::map<NodeID, AttrMap>;
    using EdgeAttrStorage = std::map<std::size_t, AttrMap>;
    using EdgeIdIndex = std::map<std::size_t, EdgeDesc>;
    static constexpr bool is_directed = Directed;
    static constexpr bool has_builtin_edge_weight = Weighted;
 
private:
    static_assert(
        ValidNodeID<NodeID>,
        "nxpp::Graph requires NodeID to satisfy nxpp::ValidNodeID: copy-constructible, equality comparable, and orderable with std::less."
    );
 
    GraphType g;
    WeightMap weight_map;
    VertexNameMap vertex_name_map;
    VertexIndexMap vertex_index_map;
    EdgeIdMap edge_id_map;
    IdMap id_to_bgl;
    std::vector<NodeID> bgl_to_id;
    std::size_t next_edge_id = 0;
    NodeAttrStorage node_properties;
    EdgeAttrStorage edge_properties;
    EdgeIdIndex edge_id_to_desc;
 
private:
    static_assert(
        !(Multi && std::is_same_v<OutEdgeSelector, boost::setS>),
        "nxpp does not support Multi=true with boost::setS because setS suppresses parallel edges."
    );
 
    using EdgeAttrMap = AttrMap;
 
    static std::any normalize_attr_any(std::any value) {
        if (value.type() == typeid(const char*)) {
            return std::string(std::any_cast<const char*>(value));
        }
        if (value.type() == typeid(char*)) {
            return std::string(std::any_cast<char*>(value));
        }
        return value;
    }
 
    template <typename T>
    static std::any make_attr_any(const T& value) {
        if constexpr (std::is_convertible_v<T, const char*> && !std::is_same_v<std::decay_t<T>, std::string>) {
            return std::string(value);
        } else {
            return std::any(value);
        }
    }
 
    static std::runtime_error invalid_flow_capacity_error() {
        return std::runtime_error("Flow capacity setup failed: capacity must be a non-negative integral value representable as long.");
    }
 
    template <typename T>
    static long checked_flow_capacity_value(T value) {
        if constexpr (std::is_same_v<T, bool>) {
            throw invalid_flow_capacity_error();
        } else if constexpr (std::is_integral_v<T> && std::is_signed_v<T>) {
            if (value < 0 || static_cast<long double>(value) > static_cast<long double>(std::numeric_limits<long>::max())) {
                throw invalid_flow_capacity_error();
            }
            return static_cast<long>(value);
        } else if constexpr (std::is_integral_v<T> && std::is_unsigned_v<T>) {
            if (static_cast<long double>(value) > static_cast<long double>(std::numeric_limits<long>::max())) {
                throw invalid_flow_capacity_error();
            }
            return static_cast<long>(value);
        } else if constexpr (std::is_floating_point_v<T>) {
            if (!std::isfinite(value) || value < 0 || value > static_cast<T>(std::numeric_limits<long>::max()) ||
                std::trunc(value) != value) {
                throw invalid_flow_capacity_error();
            }
            return static_cast<long>(value);
        } else {
            throw invalid_flow_capacity_error();
        }
    }
 
    template <typename T>
    static std::optional<long> try_flow_capacity_any_cast(const std::any& value) {
        if (const auto* typed_value = std::any_cast<T>(&value)) {
            return checked_flow_capacity_value(*typed_value);
        }
        return std::nullopt;
    }
 
    long get_edge_flow_capacity(std::size_t edge_id, const std::string& key) const {
        if (key == "weight") {
            if constexpr (Weighted) {
                return checked_flow_capacity_value(get_edge_weight(edge_id));
            } else {
                throw std::runtime_error("Edge attribute lookup failed: graph has no built-in edge weight.");
            }
        }
 
        auto edge_it = edge_properties.find(edge_id);
        if (edge_it == edge_properties.end()) {
            throw std::runtime_error("Edge attribute lookup failed: edge has no attributes.");
        }
        auto attr_it = edge_it->second.find(key);
        if (attr_it == edge_it->second.end()) {
            throw std::runtime_error("Edge attribute lookup failed: key not found.");
        }
 
        const auto& value = attr_it->second;
        if (auto capacity = try_flow_capacity_any_cast<int>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<long>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<long long>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<unsigned int>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<unsigned long>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<unsigned long long>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<float>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<double>(value)) return *capacity;
        if (auto capacity = try_flow_capacity_any_cast<long double>(value)) return *capacity;
 
        throw std::runtime_error("Flow capacity setup failed: capacity attribute is not numeric.");
    }
 
    std::size_t vertex_index_of(VertexDesc v) const {
        return boost::get(vertex_index_map, v);
    }
 
    const NodeID& node_id_of(VertexDesc v) const {
        return boost::get(vertex_name_map, v);
    }
 
    template <typename Value, typename BuildValue>
    indexed_lookup_map<NodeID, Value> build_node_indexed_result(BuildValue&& build_value) const {
        indexed_lookup_map<NodeID, Value> result;
        result.reserve(id_to_bgl.size());
        for (const auto& [id, desc] : id_to_bgl) {
            result.push_back(id, build_value(desc));
        }
        return result;
    }
 
    template <typename Value>
    indexed_lookup_map<NodeID, Value> build_sparse_node_indexed_result(
        const std::vector<std::optional<Value>>& values
    ) const {
        indexed_lookup_map<NodeID, Value> result;
        for (const auto& [id, desc] : id_to_bgl) {
            const auto index = get_vertex_index(desc);
            if (index < values.size() && values[index].has_value()) {
                result.push_back(id, *values[index]);
            }
        }
        return result;
    }
 
    void rebuild_vertex_maps() {
        id_to_bgl.clear();
        bgl_to_id.clear();
 
        std::size_t index = 0;
        for (auto [v, vend] = boost::vertices(g); v != vend; ++v, ++index) {
            boost::put(vertex_index_map, *v, index);
            NodeID id = boost::get(vertex_name_map, *v);
            id_to_bgl[id] = *v;
            bgl_to_id.push_back(id);
        }
    }
 
    void rebind_property_maps() {
        weight_map = built_in_weight_traits<GraphType, Weighted>::get(g);
        vertex_name_map = boost::get(boost::vertex_name, g);
        vertex_index_map = boost::get(boost::vertex_wrapper_index, g);
        edge_id_map = boost::get(boost::edge_index, g);
    }
 
    VertexDesc get_or_create_vertex(const NodeID& id) {
        auto it = id_to_bgl.find(id);
        if (it != id_to_bgl.end()) {
            return it->second;
        }
        VertexDesc v = boost::add_vertex(g);
        boost::put(vertex_name_map, v, id);
        boost::put(vertex_index_map, v, bgl_to_id.size());
        id_to_bgl[id] = v;
        bgl_to_id.push_back(id);
        return v;
    }
 
    std::optional<VertexDesc> find_vertex_by_id(const NodeID& id) const {
        for (auto [v, vend] = boost::vertices(g); v != vend; ++v) {
            if (boost::get(vertex_name_map, *v) == id) {
                return *v;
            }
        }
        return std::nullopt;
    }
 
    std::size_t get_edge_id(EdgeDesc e) const {
        return boost::get(edge_id_map, e);
    }
 
    void set_edge_id(EdgeDesc e, std::size_t edge_id) {
        edge_id_map[e] = edge_id;
        edge_id_to_desc[edge_id] = e;
    }
 
    std::size_t assign_next_edge_id(EdgeDesc e) {
        const auto edge_id = next_edge_id++;
        set_edge_id(e, edge_id);
        return edge_id;
    }
 
    void erase_edge_id_index(std::size_t edge_id) {
        edge_id_to_desc.erase(edge_id);
    }
 
    void rebuild_edge_id_index() {
        edge_id_to_desc.clear();
        for (auto [e, eend] = boost::edges(g); e != eend; ++e) {
            edge_id_to_desc[get_edge_id(*e)] = *e;
        }
    }
 
    std::optional<EdgeDesc> try_find_edge_desc_by_id(std::size_t edge_id) const {
        auto edge_it = edge_id_to_desc.find(edge_id);
        if (edge_it != edge_id_to_desc.end()) {
            return edge_it->second;
        }
        return std::nullopt;
    }
 
    EdgeDesc get_edge_desc_by_id(std::size_t edge_id) const {
        auto edge_desc = try_find_edge_desc_by_id(edge_id);
        if (!edge_desc.has_value()) {
            throw std::runtime_error("Edge lookup failed: edge not found.");
        }
        return *edge_desc;
    }
 
    std::vector<std::size_t> collect_edge_ids_between(VertexDesc u, VertexDesc v) const {
        std::vector<std::size_t> edge_ids;
        for (auto [e, eend] = boost::out_edges(u, g); e != eend; ++e) {
            if constexpr (Directed) {
                if (boost::target(*e, g) == v) {
                    edge_ids.push_back(get_edge_id(*e));
                }
            } else {
                const auto source = boost::source(*e, g);
                const auto target = boost::target(*e, g);
                if ((source == u && target == v) || (source == v && target == u)) {
                    const auto edge_id = get_edge_id(*e);
                    if (std::find(edge_ids.begin(), edge_ids.end(), edge_id) == edge_ids.end()) {
                        edge_ids.push_back(edge_id);
                    }
                }
            }
        }
        return edge_ids;
    }
 
    void erase_incident_edge_properties(VertexDesc v) {
        std::vector<std::size_t> edge_ids;
        for (auto [e, eend] = boost::out_edges(v, g); e != eend; ++e) {
            edge_ids.push_back(get_edge_id(*e));
        }
        if constexpr (Directed) {
            for (auto [e, eend] = boost::in_edges(v, g); e != eend; ++e) {
                if (boost::source(*e, g) != v) {
                    edge_ids.push_back(get_edge_id(*e));
                }
            }
        }
        for (auto edge_id : edge_ids) {
            edge_properties.erase(edge_id);
            erase_edge_id_index(edge_id);
        }
    }
 
    void assign_edge_attrs(EdgeDesc e, const EdgeAttrMap& attrs) {
        auto& edge_attr_map = edge_properties[get_edge_id(e)];
        for (const auto& [key, value] : attrs) {
            edge_attr_map[key] = normalize_attr_any(value);
        }
    }
 
    void assign_edge_attrs(EdgeDesc e, std::initializer_list<std::pair<std::string, std::any>> attrs) {
        auto& edge_attr_map = edge_properties[get_edge_id(e)];
        for (const auto& [key, value] : attrs) {
            edge_attr_map[key] = normalize_attr_any(value);
        }
    }
 
    void assign_edge_attr(EdgeDesc e, const std::pair<std::string, std::any>& attr) {
        edge_properties[get_edge_id(e)][attr.first] = normalize_attr_any(attr.second);
    }
 
    template <typename NodeRange>
    Graph build_subgraph(const NodeRange& selected_nodes) const {
        Graph result;
        std::set<NodeID> selected;
 
        for (const auto& node : selected_nodes) {
            if (!has_node(node)) {
                throw std::invalid_argument("Subgraph extraction failed: node not found.");
            }
            if (!selected.insert(node).second) {
                continue;
            }
 
            result.add_node(node);
            auto node_attr_it = node_properties.find(node);
            if (node_attr_it != node_properties.end()) {
                result.node_properties[node] = node_attr_it->second;
            }
        }
 
        for (auto [edge, edge_end] = boost::edges(g); edge != edge_end; ++edge) {
            const NodeID& source = node_id_of(boost::source(*edge, g));
            const NodeID& target = node_id_of(boost::target(*edge, g));
            if (!selected.contains(source) || !selected.contains(target)) {
                continue;
            }
 
            auto [new_edge, added] = boost::add_edge(result.id_to_bgl.at(source), result.id_to_bgl.at(target), result.g);
            (void)added;
            if constexpr (Weighted) {
                result.weight_map[new_edge] = weight_map[*edge];
            }
            const auto new_edge_id = result.next_edge_id++;
            result.set_edge_id(new_edge, new_edge_id);
 
            const auto old_edge_id = get_edge_id(*edge);
            const auto edge_attr_it = edge_properties.find(old_edge_id);
            if (edge_attr_it != edge_properties.end()) {
                result.edge_properties[new_edge_id] = edge_attr_it->second;
            }
        }
 
        return result;
    }
 
public:
    Graph()
        : g(),
          weight_map(built_in_weight_traits<GraphType, Weighted>::get(g)),
          vertex_name_map(boost::get(boost::vertex_name, g)),
          vertex_index_map(boost::get(boost::vertex_wrapper_index, g)),
          edge_id_map(boost::get(boost::edge_index, g)),
          id_to_bgl() {}
 
    Graph(const Graph& other)
        : g(other.g),
          weight_map(built_in_weight_traits<GraphType, Weighted>::get(g)),
          vertex_name_map(boost::get(boost::vertex_name, g)),
          vertex_index_map(boost::get(boost::vertex_wrapper_index, g)),
          edge_id_map(boost::get(boost::edge_index, g)),
          id_to_bgl(),
          bgl_to_id(),
          next_edge_id(other.next_edge_id),
          node_properties(other.node_properties),
          edge_properties(other.edge_properties) {
        rebuild_vertex_maps();
        rebuild_edge_id_index();
    }
 
    Graph(Graph&& other) noexcept
        : g(std::move(other.g)),
          weight_map(built_in_weight_traits<GraphType, Weighted>::get(g)),
          vertex_name_map(boost::get(boost::vertex_name, g)),
          vertex_index_map(boost::get(boost::vertex_wrapper_index, g)),
          edge_id_map(boost::get(boost::edge_index, g)),
          id_to_bgl(),
          bgl_to_id(),
          next_edge_id(other.next_edge_id),
          node_properties(std::move(other.node_properties)),
          edge_properties(std::move(other.edge_properties)) {
        rebuild_vertex_maps();
        rebuild_edge_id_index();
        other.clear_min_cost_flow_state();
        other.clear();
    }
 
    Graph& operator=(const Graph& other) {
        if (this == &other) {
            return *this;
        }
 
        clear_min_cost_flow_state();
        g = other.g;
        rebind_property_maps();
        next_edge_id = other.next_edge_id;
        node_properties = other.node_properties;
        edge_properties = other.edge_properties;
        rebuild_vertex_maps();
        rebuild_edge_id_index();
        return *this;
    }
 
    Graph& operator=(Graph&& other) noexcept {
        if (this == &other) {
            return *this;
        }
 
        clear_min_cost_flow_state();
        g = std::move(other.g);
        rebind_property_maps();
        next_edge_id = other.next_edge_id;
        node_properties = std::move(other.node_properties);
        edge_properties = std::move(other.edge_properties);
        rebuild_vertex_maps();
        rebuild_edge_id_index();
        other.clear_min_cost_flow_state();
        other.clear();
        return *this;
    }
 
    ~Graph() {
        clear_min_cost_flow_state();
    }
 
    void add_node(const NodeID& id) {
        invalidate_min_cost_flow_state();
        get_or_create_vertex(id);
    }
 
    void add_nodes_from(const std::vector<NodeID>& nodes) {
        for (const auto& n : nodes) {
            add_node(n);
        }
    }
 
    [[nodiscard]] EdgeDesc get_edge_desc(const NodeID& u, const NodeID& v) const {
        auto it_u = id_to_bgl.find(u);
        auto it_v = id_to_bgl.find(v);
        if (it_u == id_to_bgl.end() || it_v == id_to_bgl.end()) throw std::runtime_error("Node lookup failed: node not found.");
        auto [e, exists] = boost::edge(it_u->second, it_v->second, g);
        if (!exists) throw std::runtime_error("Edge lookup failed: edge not found.");
        return e;
    }
 
    [[nodiscard]] bool has_edge(const NodeID& u, const NodeID& v) const {
        auto it_u = id_to_bgl.find(u);
        auto it_v = id_to_bgl.find(v);
        if (it_u == id_to_bgl.end() || it_v == id_to_bgl.end()) return false;
        auto [e, exists] = boost::edge(it_u->second, it_v->second, g);
        return exists;
    }
 
    [[nodiscard]] bool has_edge_id(std::size_t edge_id) const;
    [[nodiscard]] std::vector<std::size_t> edge_ids() const;
    [[nodiscard]] std::vector<std::size_t> edge_ids(const NodeID& u, const NodeID& v) const;
    [[nodiscard]] std::pair<NodeID, NodeID> get_edge_endpoints(std::size_t edge_id) const;
 
    template <bool W = Weighted>
    requires(W)
    void add_edge(const NodeID& u, const NodeID& v, EdgeWeight w = 1.0) {
        invalidate_min_cost_flow_state();
        VertexDesc bu = get_or_create_vertex(u);
        VertexDesc bv = get_or_create_vertex(v);
        
        if constexpr (!Multi) {
            auto [e, exists] = boost::edge(bu, bv, g);
            if (exists) {
                weight_map[e] = w;
                return;
            }
        }
        
        auto [e, added] = boost::add_edge(bu, bv, g);
        (void)added;
        weight_map[e] = w;
        assign_next_edge_id(e);
    }
 
    template <bool W = Weighted>
    requires(W)
    std::size_t add_edge_with_id(const NodeID& u, const NodeID& v, EdgeWeight w = 1.0);
 
    template <bool W = Weighted>
    requires(!W)
    void add_edge(const NodeID& u, const NodeID& v) {
        invalidate_min_cost_flow_state();
        VertexDesc bu = get_or_create_vertex(u);
        VertexDesc bv = get_or_create_vertex(v);
 
        if constexpr (!Multi) {
            auto [e, exists] = boost::edge(bu, bv, g);
            if (exists) {
                return;
            }
        }
 
        auto [e, added] = boost::add_edge(bu, bv, g);
        (void)added;
        assign_next_edge_id(e);
    }
 
    template <bool W = Weighted>
    requires(!W)
    std::size_t add_edge_with_id(const NodeID& u, const NodeID& v);
 
 
    template <bool W = Weighted>
    requires(W)
    void add_edge(const NodeID& u, const NodeID& v, EdgeWeight w, const EdgeAttrMap& attrs);
 
    void add_edge(const NodeID& u, const NodeID& v, const EdgeAttrMap& attrs);
 
    template <bool W = Weighted>
    requires(W)
    void add_edge(const NodeID& u, const NodeID& v, EdgeWeight w, const std::pair<std::string, std::any>& attr);
 
    void add_edge(const NodeID& u, const NodeID& v, const std::pair<std::string, std::any>& attr);
 
    template <bool W = Weighted>
    requires(W)
    void add_edge(const NodeID& u, const NodeID& v, EdgeWeight w, std::initializer_list<std::pair<std::string, std::any>> attrs);
 
    void add_edge(const NodeID& u, const NodeID& v, std::initializer_list<std::pair<std::string, std::any>> attrs);
    template <bool W = Weighted>
    requires(W)
    void add_edges_from(const std::vector<std::tuple<NodeID, NodeID, EdgeWeight>>& edges) {
        for (const auto& edge : edges) {
            add_edge(std::get<0>(edge), std::get<1>(edge), std::get<2>(edge));
        }
    }
 
    void add_edges_from(const std::vector<std::pair<NodeID, NodeID>>& edges) {
        for (const auto& edge : edges) {
            add_edge(edge.first, edge.second);
        }
    }
 
    void clear() {
        invalidate_min_cost_flow_state();
        g = GraphType();
        id_to_bgl.clear();
        bgl_to_id.clear();
        node_properties.clear();
        edge_properties.clear();
        weight_map = built_in_weight_traits<GraphType, Weighted>::get(g);
        vertex_name_map = boost::get(boost::vertex_name, g);
        vertex_index_map = boost::get(boost::vertex_wrapper_index, g);
        edge_id_map = boost::get(boost::edge_index, g);
        next_edge_id = 0;
    }
 
    template <typename NodeRange>
    [[nodiscard]] Graph subgraph(const NodeRange& selected_nodes) const {
        return build_subgraph(selected_nodes);
    }
 
    [[nodiscard]] Graph subgraph(std::initializer_list<NodeID> selected_nodes) const {
        return build_subgraph(selected_nodes);
    }
 
    void remove_edge(const NodeID& u, const NodeID& v) {
        invalidate_min_cost_flow_state();
        auto it_u = id_to_bgl.find(u);
        auto it_v = id_to_bgl.find(v);
        if (it_u == id_to_bgl.end() || it_v == id_to_bgl.end()) {
            throw std::runtime_error("Node lookup failed: node not found.");
        }
        auto [e, exists] = boost::edge(it_u->second, it_v->second, g);
        if (!exists) {
            throw std::runtime_error("Edge lookup failed: edge not found.");
        }
        for (auto edge_id : collect_edge_ids_between(it_u->second, it_v->second)) {
            edge_properties.erase(edge_id);
            erase_edge_id_index(edge_id);
        }
        if constexpr (!Directed && Multi) {
            const auto bu = it_u->second;
            const auto bv = it_v->second;
            boost::remove_edge_if(
                [this, bu, bv](const EdgeDesc& edge) {
                    const auto source = boost::source(edge, g);
                    const auto target = boost::target(edge, g);
                    return (source == bu && target == bv) || (source == bv && target == bu);
                },
                g
            );
        } else {
            boost::remove_edge(it_u->second, it_v->second, g);
        }
    }
 
    void remove_edge(std::size_t edge_id);
 
    void remove_node(const NodeID& u) {
        invalidate_min_cost_flow_state();
        auto it = id_to_bgl.find(u);
        if (it == id_to_bgl.end()) {
            throw std::runtime_error("Node lookup failed: node not found.");
        }
        VertexDesc v = it->second;
 
        erase_incident_edge_properties(v);
        boost::clear_vertex(v, g);
        boost::remove_vertex(v, g);
        
        node_properties.erase(u);
        rebuild_vertex_maps();
        rebuild_edge_id_index();
    }
 
    void remove_nodes_from(const std::vector<NodeID>& nodes) {
        std::vector<NodeID> unique_nodes;
        std::set<NodeID> seen;
        for (const auto& node : nodes) {
            if (seen.insert(node).second) {
                unique_nodes.push_back(node);
            }
        }
 
        for (const auto& node : unique_nodes) {
            if (!has_node(node)) {
                throw std::runtime_error("Node lookup failed: node not found.");
            }
        }
 
        if (unique_nodes.empty()) {
            return;
        }
 
        invalidate_min_cost_flow_state();
        for (const auto& node : unique_nodes) {
            auto vertex = find_vertex_by_id(node);
            if (!vertex.has_value()) {
                continue;
            }
 
            erase_incident_edge_properties(*vertex);
            boost::clear_vertex(*vertex, g);
            boost::remove_vertex(*vertex, g);
            node_properties.erase(node);
        }
 
        rebuild_vertex_maps();
        rebuild_edge_id_index();
    }
 
    [[nodiscard]] std::vector<NodeID> neighbors(const NodeID& u) const {
        auto it = id_to_bgl.find(u);
        if (it == id_to_bgl.end()) {
            throw std::runtime_error("Node lookup failed: node not found.");
        }
        std::vector<NodeID> res;
        for (auto [e, eend] = boost::out_edges(it->second, g); e != eend; ++e) {
            res.push_back(node_id_of(boost::target(*e, g)));
        }
        return res;
    }
 
    [[nodiscard]] std::vector<NodeID> successors(const NodeID& u) const {
        return neighbors(u);
    }
 
    [[nodiscard]] std::vector<NodeID> predecessors(const NodeID& u) const {
        auto it = id_to_bgl.find(u);
        if (it == id_to_bgl.end()) {
            throw std::runtime_error("Node lookup failed: node not found.");
        }
 
        std::vector<NodeID> res;
        if constexpr (Directed) {
            for (auto [e, eend] = boost::in_edges(it->second, g); e != eend; ++e) {
                res.push_back(node_id_of(boost::source(*e, g)));
            }
        } else {
            for (auto [e, eend] = boost::out_edges(it->second, g); e != eend; ++e) {
                res.push_back(node_id_of(boost::target(*e, g)));
            }
        }
        return res;
    }
 
    [[nodiscard]] bool has_node(const NodeID& u) const {
        return id_to_bgl.find(u) != id_to_bgl.end();
    }
 
 
    [[nodiscard]] bool has_node_attr(const NodeID& u, const std::string& key) const;
    [[nodiscard]] bool has_edge_attr(const NodeID& u, const NodeID& v, const std::string& key) const;
    [[nodiscard]] bool has_edge_attr(std::size_t edge_id, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] T get_node_attr(const NodeID& u, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] T get_edge_attr(const NodeID& u, const NodeID& v, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] T get_edge_attr(std::size_t edge_id, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] std::optional<T> try_get_node_attr(const NodeID& u, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] std::optional<T> try_get_edge_attr(const NodeID& u, const NodeID& v, const std::string& key) const;
 
    template <typename T>
    [[nodiscard]] std::optional<T> try_get_edge_attr(std::size_t edge_id, const std::string& key) const;
 
    [[nodiscard]] double get_edge_numeric_attr(const NodeID& u, const NodeID& v, const std::string& key) const;
    [[nodiscard]] double get_edge_numeric_attr(std::size_t edge_id, const std::string& key) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] EdgeWeight get_edge_weight(const NodeID& u, const NodeID& v) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] EdgeWeight get_edge_weight(std::size_t edge_id) const;
 
    template <bool W = Weighted>
    requires(W)
    void set_edge_weight(std::size_t edge_id, EdgeWeight w);
 
    template <typename T>
    void set_edge_attr(std::size_t edge_id, const std::string& key, const T& value);
 
    [[nodiscard]] std::vector<NodeID> nodes() const {
        std::vector<NodeID> res;
        for (auto [v, vend] = boost::vertices(g); v != vend; ++v) {
            res.push_back(node_id_of(*v));
        }
        return res;
    }
 
    [[nodiscard]] std::vector<std::pair<NodeID, NodeID>> edges() const {
        std::vector<std::pair<NodeID, NodeID>> res;
        for (auto [e, eend] = boost::edges(g); e != eend; ++e) {
            NodeID source_id = node_id_of(boost::source(*e, g));
            NodeID target_id = node_id_of(boost::target(*e, g));
            res.emplace_back(source_id, target_id);
        }
        return res;
    }
 
    [[nodiscard]] std::vector<std::pair<NodeID, NodeID>> edge_pairs() const {
        return edges();
    }
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] std::vector<std::tuple<NodeID, NodeID, EdgeWeight>> weighted_edges() const {
        std::vector<std::tuple<NodeID, NodeID, EdgeWeight>> res;
        for (auto [e, eend] = boost::edges(g); e != eend; ++e) {
            NodeID source_id = node_id_of(boost::source(*e, g));
            NodeID target_id = node_id_of(boost::target(*e, g));
            res.emplace_back(source_id, target_id, weight_map[*e]);
        }
        return res;
    }
 
    [[nodiscard]] const GraphType& get_impl() const { return g; }
    [[nodiscard]] const std::vector<NodeID>& get_bgl_to_id_map() const { return bgl_to_id; }
    [[nodiscard]] const IdMap& get_id_to_bgl_map() const { return id_to_bgl; }
    [[nodiscard]] const AttrMap& node_attrs(const NodeID& u) const {
        static const AttrMap empty;
        auto it = node_properties.find(u);
        return it == node_properties.end() ? empty : it->second;
    }
    [[nodiscard]] const AttrMap& edge_attrs(std::size_t edge_id) const {
        static const AttrMap empty;
        auto it = edge_properties.find(edge_id);
        return it == edge_properties.end() ? empty : it->second;
    }
    [[nodiscard]] const NodeID& get_node_id(VertexDesc v) const { return node_id_of(v); }
    [[nodiscard]] std::size_t get_vertex_index(VertexDesc v) const { return vertex_index_of(v); }
 
    // Proxy Pattern per simulare G[u][v] = weight
    struct EdgeAttrProxy {
        Graph* graph;
        NodeID u, v;
        std::string key;
 
        template <typename T>
        EdgeAttrProxy& operator=(const T& val) {
            if (!graph->has_edge(u, v)) {
                if constexpr (Weighted) graph->add_edge(u, v, static_cast<EdgeWeight>(1.0));
                else graph->add_edge(u, v);
            }
            auto e = graph->get_edge_desc(u, v);
            graph->edge_properties[graph->get_edge_id(e)][key] = Graph::make_attr_any(val);
            return *this;
        }
 
        template <typename T>
        operator T() const {
            return graph->template get_edge_attr<T>(u, v, key);
        }
    };
 
    class EdgeProxy {
        Graph* graph;
        NodeID u, v;
    public:
        EdgeProxy(Graph* g, NodeID u, NodeID v) : graph(g), u(u), v(v) {}
        
        template <bool W = Weighted>
        requires(W)
        EdgeProxy& operator=(EdgeWeight w) {
            graph->add_edge(u, v, w);
            return *this;
        }
 
        template <bool W = Weighted>
        requires(W)
        operator EdgeWeight() const {
            return graph->get_edge_weight(u, v);
        }
 
        EdgeAttrProxy operator[](const std::string& key) {
            return {graph, u, v, key};
        }
 
        EdgeAttrProxy operator[](const char* key) {
            return {graph, u, v, std::string(key)};
        }
    };
 
    struct NodeAttrProxy {
        Graph* graph;
        NodeID u;
        std::string key;
 
        template <typename T>
        NodeAttrProxy& operator=(const T& val) {
            if (!graph->has_node(u)) graph->add_node(u);
            graph->node_properties[u][key] = Graph::make_attr_any(val);
            return *this;
        }
 
        template <typename T>
        operator T() const {
            return graph->template get_node_attr<T>(u, key);
        }
    };
 
    struct ConstEdgeAttrProxy {
        const Graph* graph;
        NodeID u, v;
        std::string key;
 
        template <typename T>
        operator T() const {
            return graph->template get_edge_attr<T>(u, v, key);
        }
    };
 
    class ConstEdgeProxy {
        const Graph* graph;
        NodeID u, v;
    public:
        ConstEdgeProxy(const Graph* g, NodeID u, NodeID v) : graph(g), u(u), v(v) {}
 
        template <bool W = Weighted>
        requires(W)
        operator EdgeWeight() const {
            return graph->get_edge_weight(u, v);
        }
 
        ConstEdgeAttrProxy operator[](const std::string& key) const {
            return {graph, u, v, key};
        }
 
        ConstEdgeAttrProxy operator[](const char* key) const {
            return {graph, u, v, std::string(key)};
        }
    };
 
    class NodeProxy {
        Graph* graph;
        NodeID u;
    public:
        NodeProxy(Graph* g, NodeID u) : graph(g), u(u) {}
        
        EdgeProxy operator[](const NodeID& v) {
            return EdgeProxy(graph, u, v);
        }
    };
 
    class ConstNodeProxy {
        const Graph* graph;
        NodeID u;
    public:
        ConstNodeProxy(const Graph* g, NodeID u) : graph(g), u(u) {}
 
        ConstEdgeProxy operator[](const NodeID& v) const {
            return ConstEdgeProxy(graph, u, v);
        }
    };
 
    class NodeAttrBaseProxy {
        Graph* graph;
        NodeID u;
    public:
        NodeAttrBaseProxy(Graph* g, NodeID u) : graph(g), u(u) {}
        
        NodeAttrProxy operator[](const std::string& key) {
            return {graph, u, key};
        }
 
        NodeAttrProxy operator[](const char* key) {
            return {graph, u, std::string(key)};
        }
    };
 
    NodeProxy operator[](const NodeID& u) {
        if (!has_node(u)) {
            add_node(u);
        }
        return NodeProxy(this, u);
    }
 
    ConstNodeProxy operator[](const NodeID& u) const {
        if (!has_node(u)) {
            throw std::out_of_range("Graph::operator[] const: node not found");
        }
        return ConstNodeProxy(this, u);
    }
 
    NodeAttrBaseProxy node(const NodeID& u) {
        if (!has_node(u)) add_node(u);
        return NodeAttrBaseProxy(this, u);
    }
 
    [[nodiscard]] auto bfs_edges(const NodeID& start) const;
    [[nodiscard]] auto bfs_edges_view(const NodeID& start) const;
    [[nodiscard]] auto bfs_tree(const NodeID& start) const;
    [[nodiscard]] auto bfs_successors(const NodeID& start) const;
    template <typename Visitor>
    void breadth_first_search(const NodeID& start, Visitor& visitor) const;
    template <typename OnVertex, typename OnTreeEdge>
    void bfs_visit(const NodeID& start, OnVertex&& on_vertex, OnTreeEdge&& on_tree_edge) const;
    [[nodiscard]] auto dfs_edges(const NodeID& start) const;
    [[nodiscard]] auto dfs_edges_view(const NodeID& start) const;
    [[nodiscard]] auto dfs_tree(const NodeID& start) const;
    [[nodiscard]] auto dfs_predecessors(const NodeID& start) const;
    [[nodiscard]] auto dfs_successors(const NodeID& start) const;
    template <typename Visitor>
    void depth_first_search(const NodeID& start, Visitor& visitor) const;
    template <typename OnTreeEdge, typename OnBackEdge>
    void dfs_visit(const NodeID& start, OnTreeEdge&& on_tree_edge, OnBackEdge&& on_back_edge) const;
 
    [[nodiscard]] auto shortest_path(const NodeID& source_id, const NodeID& target_id) const;
    [[nodiscard]] auto shortest_path(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
    [[nodiscard]] auto shortest_path(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
    [[nodiscard]] double shortest_path_length(const NodeID& source_id, const NodeID& target_id) const;
    [[nodiscard]] double shortest_path_length(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
    [[nodiscard]] double shortest_path_length(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path(const NodeID& source_id, const NodeID& target_id) const;
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_shortest_paths(const NodeID& source_id) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path_length(const NodeID& source_id) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path_length(const NodeID& source_id, const NodeID& target_id) const;
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path_length(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dijkstra_path_length(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path(const NodeID& source_id, const NodeID& target_id) const;
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_shortest_paths(const NodeID& source_id) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path_length(const NodeID& source_id, const NodeID& target_id) const;
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path_length(const NodeID& source_id, const NodeID& target_id, WeightMode mode) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto bellman_ford_path_length(const NodeID& source_id, const NodeID& target_id, const std::string& weight) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto dag_shortest_paths(const NodeID& source_id) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto floyd_warshall_all_pairs_shortest_paths() const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto floyd_warshall_all_pairs_shortest_paths_map() const;
 
    [[nodiscard]] auto connected_component_groups() const;
    [[nodiscard]] auto connected_components() const;
    [[nodiscard]] auto strongly_connected_component_groups() const;
    [[nodiscard]] auto strong_component_map() const;
    [[nodiscard]] auto strong_components() const;
    [[nodiscard]] auto connected_component_map() const;
    [[nodiscard]] auto strongly_connected_components() const;
    [[nodiscard]] auto strongly_connected_component_map() const;
    [[nodiscard]] auto strongly_connected_component_roots() const;
    [[nodiscard]] auto topological_sort() const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto kruskal_minimum_spanning_tree() const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto prim_minimum_spanning_tree(const NodeID& root_id) const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto minimum_spanning_tree() const;
 
    template <bool W = Weighted>
    requires(W)
    [[nodiscard]] auto minimum_spanning_tree(const NodeID& root_id) const;
 
    [[nodiscard]] auto edmonds_karp_maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity") const;
    [[nodiscard]] auto push_relabel_maximum_flow_result(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity") const;
    [[nodiscard]] auto maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity") const;
    [[nodiscard]] auto minimum_cut(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity") const;
    [[nodiscard]] auto max_flow_min_cost_cycle_canceling(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") const;
    [[nodiscard]] long push_relabel_maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") const;
    [[nodiscard]] auto cycle_canceling(const std::string& weight_attr = "weight") const;
    [[nodiscard]] auto successive_shortest_path_nonnegative_weights(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") const;
    [[nodiscard]] auto max_flow_min_cost_successive_shortest_path(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") const;
    [[nodiscard]] auto max_flow_min_cost(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") const;
 
    [[nodiscard]] auto num_vertices() const noexcept;
    [[nodiscard]] std::size_t num_edges() const noexcept;
    [[nodiscard]] auto degree_centrality() const;
    [[nodiscard]] auto pagerank(double tolerance = 1e-6, std::size_t max_iterations = 100) const;
    [[nodiscard]] auto betweenness_centrality() const;
 
private:
    void invalidate_min_cost_flow_state() const {
        detail::MinCostFlowCacheHooks<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>::invalidate(
            static_cast<const void*>(this)
        );
    }
 
    void clear_min_cost_flow_state() const {
        detail::MinCostFlowCacheHooks<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>::clear(
            static_cast<const void*>(this)
        );
    }
 
    [[nodiscard]] auto floyd_warshall_matrix_with_order() const;
};
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
[[nodiscard]] auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::num_vertices() const noexcept {
    return static_cast<int>(boost::num_vertices(g));
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
[[nodiscard]] std::size_t Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::num_edges() const noexcept {
    return static_cast<std::size_t>(boost::num_edges(g));
}
 
 
template <typename GraphWrapper>
[[deprecated("Use G.num_vertices() instead.")]]
[[nodiscard]] auto num_vertices(const GraphWrapper& G) {
    return G.num_vertices();
}
 
template <typename GraphWrapper>
[[deprecated("Use G.num_edges() instead.")]]
[[nodiscard]] auto num_edges(const GraphWrapper& G) {
    return G.num_edges();
}
 
 
using WeightedGraphInt = Graph<int, int>;                     
using WeightedDiGraphInt = Graph<int, int, true>;              
using WeightedGraphStr = Graph<std::string>;                   
using WeightedDiGraphStr = Graph<std::string, double, true>;   
using WeightedMultiGraphInt = Graph<int, int, false, true>;   
using WeightedMultiDiGraphInt = Graph<int, int, true, true>;  
using WeightedMultiGraphStr = Graph<std::string, double, false, true>;  
using WeightedMultiDiGraphStr = Graph<std::string, double, true, true>; 
 
using WeightedDiGraph = Graph<std::string, double, true>;              
using WeightedMultiGraph = Graph<std::string, double, false, true>;    
using WeightedMultiDiGraph = Graph<std::string, double, true, true>;   
 
using GraphInt = Graph<int, int>;                            
using DiGraphInt = Graph<int, int, true>;              
using GraphStr = Graph<std::string>;                   
using MultiGraphInt = Graph<int, int, false, true>;   
using MultiDiGraphInt = Graph<int, int, true, true>;  
 
using DiGraph = Graph<std::string, double, true>;            
using MultiGraph = Graph<std::string, double, false, true>;  
using MultiDiGraph = Graph<std::string, double, true, true>; 
 
using UnweightedGraphInt = Graph<int, double, false, false, false>;            
using UnweightedDiGraphInt = Graph<int, double, true, false, false>;           
using UnweightedGraphStr = Graph<std::string, double, false, false, false>;    
using UnweightedDiGraph = Graph<std::string, double, true, false, false>;      
using UnweightedMultiGraphInt = Graph<int, double, false, true, false>;        
using UnweightedMultiDiGraphInt = Graph<int, double, true, true, false>;       
using UnweightedMultiGraph = Graph<std::string, double, false, true, false>;   
using UnweightedMultiDiGraph = Graph<std::string, double, true, true, false>;  
 
} // namespace nxpp