Using boost::push_relabel_max_flow

Question

I am having trouble calculating the maximum flow for a given graph using boost::push_relabel_max_flow. I've written the following code:

std::map<Graph::edge_descriptor, long> edge2rescap;
boost::associative_property_map<std::map<Graph::edge_descriptor, long> > out(edge2rescap);
int flow_val = boost::push_relabel_max_flow (g_transformed_for_max_flow, v_start, v_end, capacity_map(boost::get(&EdgeProps::edge_capacity, g_transformed_for_max_flow))
                   .reverse_edge_map(boost::get(&EdgeProps::reverse_edge, g_transformed_for_max_flow))
                   .vertex_index_map(boost::get(boost::vertex_index, g_transformed_for_max_flow))
                   .residual_capacity_map(out)); 

The graph was defined as follows:

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Graph;
struct VertexProperty{ };
struct EdgeProps{
  // long edge_capacity;
  long edge_capacity;
  Graph::edge_descriptor reverse_edge;
  EdgeProps(long capacity, Graph::edge_descriptor reverseEdge): edge_capacity(capacity), reverse_edge(reverseEdge){};
  EdgeProps(long capacity):                                     edge_capacity(capacity){};
  EdgeProps(){};
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperty, EdgeProps > DirectedGraph_maxflow;
typedef boost::graph_traits <DirectedGraph_maxflow>::edge_iterator edgeIt_dir;
typedef boost::graph_traits<DirectedGraph_maxflow>::out_edge_iterator out_edge_iterator;

My code compiles perfectly for my simple graph example. However, strangely it does so only if all capacities are chosen equally. If i change just one capacity the compiler outputs: Assertion `algo.is_flow()' failed.

Maybe someone has had this issue once before and knows how to solve it. If not, it would be nice if someone of you could maybe share with me a small working example (using a non-trivial graph). Thank you in advance for your responses.

Answer 1

Without self-contained example, my best bet is you invoke UB because the back edges are inconsistent?

Perhaps you can edit this Live Example to demonstrate the issue you're having:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>

using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using V      = Traits::vertex_descriptor;
using E      = Traits::edge_descriptor;
template <> struct fmt::formatter<E> : fmt::ostream_formatter {};
struct VertexProps {};

struct EdgeProps {
    long edge_capacity = 0;
    E    reverse_edge  = {};

    EdgeProps(long capacity = 0, E reverseEdge = {}) //
        : edge_capacity(capacity)
        , reverse_edge(reverseEdge){};
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProps, EdgeProps>;

int main() {
    Graph g(5);
    auto ecap = get(&EdgeProps::edge_capacity, g);
    auto reve = get(&EdgeProps::reverse_edge, g);

    auto insert = [&](V s, V t, EdgeProps p) {
        auto fwd  = add_edge(s, t, p, g).first;
        auto bck  = add_edge(t, s, {}, g).first;
        reve[fwd] = bck;
        reve[bck] = fwd;
    };

    insert(0, 1, {6});
    insert(1, 2, {7});
    insert(2, 3, {3});
    insert(3, 4, {1});
    V v_start = 1, v_end = 4;

    std::map<E, long> residuals;

    int flow_val = push_relabel_max_flow(
        g, v_start, v_end,
        capacity_map(ecap)
            .reverse_edge_map(reve)
            .residual_capacity_map(make_assoc_property_map(residuals)));

    fmt::print("flow: {} residuals: {}\n", flow_val, residuals);
}

Printing

flow: 1 residuals: {(0,1): 6, (1,0): 0, (1,2): 6, (2,1): 1, (2,3): 2, (3,2): 1, (3,4): 0, (4,3): 1}