flow.hpp

Go to the documentation of this file.

#pragma once
 
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/find_flow_cost.hpp>
#include <boost/graph/successive_shortest_path_nonnegative_weights.hpp>
 
#include <memory>
#include <queue>
#include <mutex>
#include <set>
 
#include "attributes.hpp"
#include "multigraph.hpp"
 
namespace nxpp {
 
template <typename NodeID>
struct MaximumFlowResult {
    long value = 0;
    std::map<std::pair<NodeID, NodeID>, long> flow;
    std::map<std::size_t, long> edge_flows_by_id;
};
 
template <typename NodeID>
struct MinCostMaxFlowResult {
    long flow = 0;
    long cost = 0;
    std::map<std::pair<NodeID, NodeID>, long> edge_flows;
    std::map<std::size_t, long> edge_flows_by_id;
};
 
namespace detail {
 
template <typename NodeID, typename FlowEdgeDesc>
struct FlowEdgeRecord {
    std::size_t edge_id;
    NodeID source_id;
    NodeID target_id;
    FlowEdgeDesc edge_desc;
};
 
template <typename NodeID>
struct CapacityFlowGraphState {
    using FlowTraits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
    using FlowGraph = boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::directedS,
        boost::no_property,
        boost::property<
            boost::edge_capacity_t,
            long,
            boost::property<
                boost::edge_residual_capacity_t,
                long,
                boost::property<boost::edge_reverse_t, typename FlowTraits::edge_descriptor>
            >
        >
    >;
    using CapacityMap = typename boost::property_map<FlowGraph, boost::edge_capacity_t>::type;
    using ResidualMap = typename boost::property_map<FlowGraph, boost::edge_residual_capacity_t>::type;
    using ReverseMap = typename boost::property_map<FlowGraph, boost::edge_reverse_t>::type;
    using FlowEdgeDesc = typename boost::graph_traits<FlowGraph>::edge_descriptor;
 
    FlowGraph flow_graph;
    CapacityMap capacity;
    ResidualMap residual;
    ReverseMap reverse;
    std::vector<FlowEdgeRecord<NodeID, FlowEdgeDesc>> original_edges;
 
    CapacityFlowGraphState()
        : flow_graph(),
          capacity(boost::get(boost::edge_capacity, flow_graph)),
          residual(boost::get(boost::edge_residual_capacity, flow_graph)),
          reverse(boost::get(boost::edge_reverse, flow_graph)) {}
};
 
template <typename NodeID>
struct WeightedFlowGraphState {
    using FlowTraits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
    using FlowGraph = boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::directedS,
        boost::no_property,
        boost::property<
            boost::edge_weight_t,
            long,
            boost::property<
                boost::edge_capacity_t,
                long,
                boost::property<
                    boost::edge_residual_capacity_t,
                    long,
                    boost::property<boost::edge_reverse_t, typename FlowTraits::edge_descriptor>
                >
            >
        >
    >;
    using WeightMap = typename boost::property_map<FlowGraph, boost::edge_weight_t>::type;
    using CapacityMap = typename boost::property_map<FlowGraph, boost::edge_capacity_t>::type;
    using ResidualMap = typename boost::property_map<FlowGraph, boost::edge_residual_capacity_t>::type;
    using ReverseMap = typename boost::property_map<FlowGraph, boost::edge_reverse_t>::type;
    using FlowEdgeDesc = typename boost::graph_traits<FlowGraph>::edge_descriptor;
 
    FlowGraph flow_graph;
    WeightMap weight;
    CapacityMap capacity;
    ResidualMap residual;
    ReverseMap reverse;
    std::vector<FlowEdgeRecord<NodeID, FlowEdgeDesc>> original_edges;
 
    WeightedFlowGraphState()
        : flow_graph(),
          weight(boost::get(boost::edge_weight, flow_graph)),
          capacity(boost::get(boost::edge_capacity, flow_graph)),
          residual(boost::get(boost::edge_residual_capacity, flow_graph)),
          reverse(boost::get(boost::edge_reverse, flow_graph)) {}
};
 
template <typename FlowState>
void add_flow_vertices(FlowState& state, std::size_t count) {
    for (std::size_t i = 0; i < count; ++i) {
        boost::add_vertex(state.flow_graph);
    }
}
 
template <typename FlowState>
auto add_capacity_edge_pair(FlowState& state, std::size_t source_index, std::size_t target_index, long capacity_value) {
    auto [edge, added] = boost::add_edge(source_index, target_index, state.flow_graph);
    auto [reverse_edge, reverse_added] = boost::add_edge(target_index, source_index, state.flow_graph);
    (void)added;
    (void)reverse_added;
    state.capacity[edge] = capacity_value;
    state.capacity[reverse_edge] = 0;
    state.reverse[edge] = reverse_edge;
    state.reverse[reverse_edge] = edge;
    return edge;
}
 
template <typename GraphWrapper, typename FlowState, typename EdgeIdFn, typename CapacityFn>
void add_capacity_flow_edges(
    const GraphWrapper& graph,
    FlowState& state,
    EdgeIdFn&& edge_id_for,
    CapacityFn&& capacity_for
) {
    const auto& impl = graph.get_impl();
    for (auto [eit, eend] = boost::edges(impl); eit != eend; ++eit) {
        const auto source = boost::source(*eit, impl);
        const auto target = boost::target(*eit, impl);
        const auto source_index = graph.get_vertex_index(source);
        const auto target_index = graph.get_vertex_index(target);
        const auto& source_id = graph.get_node_id(source);
        const auto& target_id = graph.get_node_id(target);
        const auto edge_id = edge_id_for(*eit);
        const auto edge = add_capacity_edge_pair(state, source_index, target_index, capacity_for(edge_id));
        state.original_edges.push_back({edge_id, source_id, target_id, edge});
    }
}
 
template <typename GraphWrapper, typename FlowState, typename EdgeIdFn, typename CapacityFn, typename WeightFn>
void add_weighted_flow_edges(
    const GraphWrapper& graph,
    FlowState& state,
    EdgeIdFn&& edge_id_for,
    CapacityFn&& capacity_for,
    WeightFn&& weight_for
) {
    const auto& impl = graph.get_impl();
    for (auto [eit, eend] = boost::edges(impl); eit != eend; ++eit) {
        const auto source = boost::source(*eit, impl);
        const auto target = boost::target(*eit, impl);
        const auto source_index = graph.get_vertex_index(source);
        const auto target_index = graph.get_vertex_index(target);
        const auto& source_id = graph.get_node_id(source);
        const auto& target_id = graph.get_node_id(target);
        const auto edge_id = edge_id_for(*eit);
        const auto edge = add_capacity_edge_pair(state, source_index, target_index, capacity_for(edge_id));
        const auto reverse_edge = state.reverse[edge];
        state.weight[edge] = weight_for(edge_id);
        state.weight[reverse_edge] = -state.weight[edge];
        state.original_edges.push_back({edge_id, source_id, target_id, edge});
    }
}
 
template <typename NodeID, typename FlowEdgeDesc, typename CapacityMap, typename ResidualMap>
void fill_flow_views(
    const std::vector<FlowEdgeRecord<NodeID, FlowEdgeDesc>>& original_edges,
    const CapacityMap& capacity,
    const ResidualMap& residual,
    std::map<std::pair<NodeID, NodeID>, long>& endpoint_flows,
    std::map<std::size_t, long>& edge_flows_by_id
) {
    for (const auto& edge : original_edges) {
        const long flow_value = capacity[edge.edge_desc] - residual[edge.edge_desc];
        endpoint_flows[{edge.source_id, edge.target_id}] += flow_value;
        edge_flows_by_id[edge.edge_id] = flow_value;
    }
}
 
template <typename NodeID>
struct MinCostFlowState : WeightedFlowGraphState<NodeID> {
    NodeID source_id;
    NodeID target_id;
    long value = 0;
    long cost = 0;
};
 
template <typename GraphWrapper>
auto& min_cost_flow_cache() {
    using NodeID = typename GraphWrapper::NodeType;
    static std::map<const void*, std::unique_ptr<MinCostFlowState<NodeID>>> cache;
    return cache;
}
 
template <typename GraphWrapper>
auto& invalidated_min_cost_flow_graphs() {
    static std::set<const void*> invalidated;
    return invalidated;
}
 
template <typename GraphWrapper>
auto& min_cost_flow_cache_mutex() {
    static std::mutex mutex;
    return mutex;
}
 
} // namespace detail
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
struct detail::MinCostFlowCacheHooks<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>> {
    static void invalidate(const void* graph_ptr) {
        std::lock_guard lock(detail::min_cost_flow_cache_mutex<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>());
        auto& cache = detail::min_cost_flow_cache<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
        if (cache.erase(graph_ptr) > 0) {
            detail::invalidated_min_cost_flow_graphs<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>().insert(graph_ptr);
        }
    }
 
    static void clear(const void* graph_ptr) {
        std::lock_guard lock(detail::min_cost_flow_cache_mutex<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>());
        auto& cache = detail::min_cost_flow_cache<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
        auto& invalidated = detail::invalidated_min_cost_flow_graphs<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
        cache.erase(graph_ptr);
        invalidated.erase(graph_ptr);
    }
};
 
template <typename NodeID>
struct MinimumCutResult {
    long value = 0;
    std::vector<NodeID> reachable;
    std::vector<NodeID> non_reachable;
    std::vector<std::pair<NodeID, NodeID>> cut_edges;
    std::vector<std::size_t> cut_edge_ids;
};
 
template <typename GraphWrapper>
[[deprecated("Use G.edmonds_karp_maximum_flow(source, target, capacity_attr) instead.")]]
auto edmonds_karp_maximum_flow(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity") {
    return G.edmonds_karp_maximum_flow(source_id, target_id, capacity_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.push_relabel_maximum_flow_result(source, target, capacity_attr) instead.")]]
auto push_relabel_maximum_flow_result(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity") {
    return G.push_relabel_maximum_flow_result(source_id, target_id, capacity_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.maximum_flow(source, target, capacity_attr) instead.")]]
auto maximum_flow(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity") {
    return G.maximum_flow(source_id, target_id, capacity_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.minimum_cut(source, target, capacity_attr) instead.")]]
auto minimum_cut(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity") {
    return G.minimum_cut(source_id, target_id, capacity_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.max_flow_min_cost_cycle_canceling(source, target, capacity_attr, weight_attr) instead.")]]
auto max_flow_min_cost_cycle_canceling(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") {
    return G.max_flow_min_cost_cycle_canceling(source_id, target_id, capacity_attr, weight_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.push_relabel_maximum_flow(source, target, capacity_attr, weight_attr) instead.")]]
long push_relabel_maximum_flow(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") {
    return G.push_relabel_maximum_flow(source_id, target_id, capacity_attr, weight_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.cycle_canceling(weight_attr) instead.")]]
auto cycle_canceling(const GraphWrapper& G, const std::string& weight_attr = "weight") {
    return G.cycle_canceling(weight_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.successive_shortest_path_nonnegative_weights(source, target, capacity_attr, weight_attr) instead.")]]
auto successive_shortest_path_nonnegative_weights(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") {
    return G.successive_shortest_path_nonnegative_weights(source_id, target_id, capacity_attr, weight_attr);
}
 
template <typename GraphWrapper>
[[deprecated("Use G.max_flow_min_cost_successive_shortest_path(source, target, capacity_attr, weight_attr) instead.")]]
auto max_flow_min_cost_successive_shortest_path(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") {
    return G.max_flow_min_cost_successive_shortest_path(source_id, target_id, capacity_attr, weight_attr);
}
template <typename GraphWrapper>
[[deprecated("Use G.max_flow_min_cost(source, target, capacity_attr, weight_attr) instead.")]]
auto max_flow_min_cost(const GraphWrapper& G, const typename GraphWrapper::NodeType& source_id, const typename GraphWrapper::NodeType& target_id, const std::string& capacity_attr = "capacity", const std::string& weight_attr = "weight") {
    return G.max_flow_min_cost(source_id, target_id, capacity_attr, weight_attr);
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::edmonds_karp_maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    detail::CapacityFlowGraphState<NodeID> state;
    detail::add_flow_vertices(state, get_bgl_to_id_map().size());
    detail::add_capacity_flow_edges(
        *this,
        state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); }
    );
 
    const long flow_value = boost::edmonds_karp_max_flow(
        state.flow_graph,
        get_vertex_index(get_id_to_bgl_map().at(source_id)),
        get_vertex_index(get_id_to_bgl_map().at(target_id))
    );
    MaximumFlowResult<NodeID> result;
    result.value = flow_value;
    detail::fill_flow_views(state.original_edges, state.capacity, state.residual, result.flow, result.edge_flows_by_id);
    return result;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::push_relabel_maximum_flow_result(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    detail::CapacityFlowGraphState<NodeID> state;
    detail::add_flow_vertices(state, get_bgl_to_id_map().size());
    detail::add_capacity_flow_edges(
        *this,
        state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); }
    );
 
    const long flow_value = boost::push_relabel_max_flow(
        state.flow_graph,
        get_vertex_index(get_id_to_bgl_map().at(source_id)),
        get_vertex_index(get_id_to_bgl_map().at(target_id))
    );
    MaximumFlowResult<NodeID> result;
    result.value = flow_value;
    detail::fill_flow_views(state.original_edges, state.capacity, state.residual, result.flow, result.edge_flows_by_id);
    return result;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr) const { return edmonds_karp_maximum_flow(source_id, target_id, capacity_attr); }
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::minimum_cut(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    detail::CapacityFlowGraphState<NodeID> state;
    const auto& index_to_node = get_bgl_to_id_map();
    detail::add_flow_vertices(state, index_to_node.size());
    detail::add_capacity_flow_edges(
        *this,
        state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); }
    );
    const auto source_index = get_vertex_index(get_id_to_bgl_map().at(source_id));
    const auto target_index = get_vertex_index(get_id_to_bgl_map().at(target_id));
    const long cut_value = boost::edmonds_karp_max_flow(state.flow_graph, source_index, target_index);
    std::vector<bool> visited(index_to_node.size(), false);
    std::queue<std::size_t> q;
    visited[source_index] = true;
    q.push(source_index);
    while (!q.empty()) {
        const auto current = q.front();
        q.pop();
        for (auto [eit, eend] = boost::out_edges(current, state.flow_graph); eit != eend; ++eit) {
            const auto next = boost::target(*eit, state.flow_graph);
            if (!visited[next] && state.residual[*eit] > 0) { visited[next] = true; q.push(next); }
        }
    }
    MinimumCutResult<NodeID> result;
    result.value = cut_value;
    for (std::size_t i = 0; i < index_to_node.size(); ++i) {
        if (visited[i]) result.reachable.push_back(index_to_node[i]);
        else result.non_reachable.push_back(index_to_node[i]);
    }
    for (auto [eit, eend] = boost::edges(g); eit != eend; ++eit) {
        const auto source = boost::source(*eit, g);
        const auto target = boost::target(*eit, g);
        const auto source_index_for_cut = get_vertex_index(source);
        const auto target_index_for_cut = get_vertex_index(target);
        if (visited[source_index_for_cut] && !visited[target_index_for_cut]) {
            result.cut_edges.emplace_back(get_node_id(source), get_node_id(target));
            result.cut_edge_ids.push_back(get_edge_id(*eit));
        }
    }
    return result;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::max_flow_min_cost_cycle_canceling(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr, const std::string& weight_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    detail::WeightedFlowGraphState<NodeID> state;
    detail::add_flow_vertices(state, get_bgl_to_id_map().size());
    detail::add_weighted_flow_edges(
        *this,
        state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); },
        [this, &weight_attr](std::size_t edge_id) { return static_cast<long>(get_edge_numeric_attr(edge_id, weight_attr)); }
    );
    boost::push_relabel_max_flow(
        state.flow_graph,
        get_vertex_index(get_id_to_bgl_map().at(source_id)),
        get_vertex_index(get_id_to_bgl_map().at(target_id))
    );
    boost::cycle_canceling(state.flow_graph);
    const long cost = boost::find_flow_cost(state.flow_graph);
    MinCostMaxFlowResult<NodeID> result;
    result.cost = cost;
    detail::fill_flow_views(state.original_edges, state.capacity, state.residual, result.edge_flows, result.edge_flows_by_id);
    for (const auto& edge : state.original_edges) {
        if (edge.source_id == source_id) {
            result.flow += result.edge_flows_by_id[edge.edge_id];
        }
    }
    return result;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
long Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::push_relabel_maximum_flow(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr, const std::string& weight_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    auto state = std::make_unique<detail::MinCostFlowState<NodeID>>();
    state->source_id = source_id;
    state->target_id = target_id;
    detail::add_flow_vertices(*state, get_bgl_to_id_map().size());
    detail::add_weighted_flow_edges(
        *this,
        *state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); },
        [this, &weight_attr](std::size_t edge_id) { return static_cast<long>(get_edge_numeric_attr(edge_id, weight_attr)); }
    );
    state->value = boost::push_relabel_max_flow(
        state->flow_graph,
        get_vertex_index(get_id_to_bgl_map().at(source_id)),
        get_vertex_index(get_id_to_bgl_map().at(target_id))
    );
    const long flow_value = state->value;
    {
        std::lock_guard lock(detail::min_cost_flow_cache_mutex<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>());
        auto& cache = detail::min_cost_flow_cache<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
        auto& invalidated = detail::invalidated_min_cost_flow_graphs<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
        cache[static_cast<const void*>(this)] = std::move(state);
        invalidated.erase(static_cast<const void*>(this));
    }
    return flow_value;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::cycle_canceling(const std::string& weight_attr) const {
    std::lock_guard lock(detail::min_cost_flow_cache_mutex<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>());
    auto& cache = detail::min_cost_flow_cache<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
    auto& invalidated = detail::invalidated_min_cost_flow_graphs<Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>>();
    auto it = cache.find(static_cast<const void*>(this));
    if (it == cache.end()) {
        if (invalidated.contains(static_cast<const void*>(this))) {
            throw std::runtime_error("Min-cost-flow state invalidated by graph mutation: rerun push_relabel_maximum_flow(...) before cycle_canceling().");
        }
        throw std::runtime_error("Min-cost-flow state unavailable: run push_relabel_maximum_flow(...) first.");
    }
    auto& state = *it->second;
    for (const auto& edge : state.original_edges) {
        state.weight[edge.edge_desc] = static_cast<long>(get_edge_numeric_attr(edge.edge_id, weight_attr));
        const auto rev = state.reverse[edge.edge_desc];
        state.weight[rev] = -state.weight[edge.edge_desc];
    }
    boost::cycle_canceling(state.flow_graph);
    state.cost = boost::find_flow_cost(state.flow_graph);
    return state.cost;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::successive_shortest_path_nonnegative_weights(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr, const std::string& weight_attr) const {
    if (!has_node(source_id) || !has_node(target_id)) throw std::runtime_error("Flow setup failed: source or target node not found.");
    detail::WeightedFlowGraphState<NodeID> state;
    detail::add_flow_vertices(state, get_bgl_to_id_map().size());
    detail::add_weighted_flow_edges(
        *this,
        state,
        [this](EdgeDesc edge) { return get_edge_id(edge); },
        [this, &capacity_attr](std::size_t edge_id) { return get_edge_flow_capacity(edge_id, capacity_attr); },
        [this, &weight_attr](std::size_t edge_id) { return static_cast<long>(get_edge_numeric_attr(edge_id, weight_attr)); }
    );
    const auto source_index = get_vertex_index(get_id_to_bgl_map().at(source_id));
    const auto target_index = get_vertex_index(get_id_to_bgl_map().at(target_id));
    boost::successive_shortest_path_nonnegative_weights(state.flow_graph, source_index, target_index);
    long flow_value = 0;
    for (auto [eit, eend] = boost::out_edges(source_index, state.flow_graph); eit != eend; ++eit) {
        flow_value += state.capacity[*eit] - state.residual[*eit];
    }
    const long cost = boost::find_flow_cost(state.flow_graph);
    MinCostMaxFlowResult<NodeID> result;
    result.flow = flow_value;
    result.cost = cost;
    detail::fill_flow_views(state.original_edges, state.capacity, state.residual, result.edge_flows, result.edge_flows_by_id);
    return result;
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::max_flow_min_cost_successive_shortest_path(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr, const std::string& weight_attr) const {
    return successive_shortest_path_nonnegative_weights(source_id, target_id, capacity_attr, weight_attr);
}
 
template <typename NodeID, typename EdgeWeight, bool Directed, bool Multi, bool Weighted, typename OutEdgeSelector, typename VertexSelector>
auto Graph<NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector>::max_flow_min_cost(const NodeID& source_id, const NodeID& target_id, const std::string& capacity_attr, const std::string& weight_attr) const {
    return max_flow_min_cost_cycle_canceling(source_id, target_id, capacity_attr, weight_attr);
}
 
} // namespace nxpp