c++graphboostmax-flowpush-relabel

Using boost::push_relabel_max_flow


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.


Solution

  • 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}