0

Consider the following original input graph on which the max flow algorithm is applied:

enter image description here

The following code (thanks to user sehe) compiles and runs fine and gives the correct output. Code is reproduced below for completion:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/range/adaptors.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
using boost::adaptors::filtered;

using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using V      = Traits::vertex_descriptor;
using E      = Traits::edge_descriptor;

using Capacity = double;
using Color    = boost::default_color_type;

struct VertexProps {
    // std::string name;
    Color    color;
    Capacity distance;
    E        preedcessor;
};

struct EdgeProps {
    int      id;
    Capacity weight, residual;
    E        reverse;
};

using Graph = boost::adjacency_list<
    boost::vecS, boost::vecS, boost::directedS,
    VertexProps,
    // see https://stackoverflow.com/a/64744086/85371 :(
    boost::property<boost::edge_capacity_t, Capacity, EdgeProps>>;

struct MyGraph {
    MyGraph(size_t nnodes) : _g(nnodes) {}

    void runSimulation(std::vector<std::pair<V, V>> const& arcs,
                       std::vector<Capacity> const&        capacities)
    {
        reconfigure(arcs, capacities);

        Capacity maxflow = solve_max_flow(0, 3);

        auto cap       = get(boost::edge_capacity, _g);
        auto is_source = [this](V v) { return _g[v].color == Color::black_color; };

        fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow,
                   vertices(_g) | filtered(is_source));

        for (E e : boost::make_iterator_range(edges(_g))) {
            bool st_cut =
                is_source(source(e, _g)) and
                not is_source(target(e, _g));

            fmt::print("Edge {} (id #{:2}), capacity {:3} {}\n", e, _g[e].id,
                       cap[e], st_cut ? "(ST Cut)" : "");
        }
    }

  private:
    Graph _g;

    void reconfigure(auto const& arcs, auto const& capacities)
    {
        assert(arcs.size() == capacities.size());

        for (auto v : boost::make_iterator_range(vertices(_g))) {
            // boost::clear_out_edges(v, g);
            boost::clear_vertex(v, _g);
        }

        auto cap  = get(boost::edge_capacity, _g);
        auto eidx = get(&EdgeProps::id, _g);
        auto rev  = get(&EdgeProps::reverse, _g);

        auto  eindex = 0;

        for (auto [fr, to] : arcs) {
            auto edf  = add_edge(fr, to, _g).first;
            auto edr  = add_edge(to, fr, _g).first;
            eidx[edf] = 2 * eindex;
            eidx[edr] = eidx[edf] + 1;
            cap[edf]  = cap[edr] = capacities[eindex];

            rev[edf] = edr;
            rev[edr] = edf;

            ++eindex;
        }
    }

    Capacity solve_max_flow(V src, V sink)
    {
        return boykov_kolmogorov_max_flow(
            _g, src, sink,
            // named arguments
            boost::reverse_edge_map(get(&EdgeProps::reverse, _g))
                .residual_capacity_map(get(&EdgeProps::residual, _g))
                .vertex_color_map(get(&VertexProps::color,       _g))
                .predecessor_map(get(&VertexProps::preedcessor,  _g))
                .distance_map(get(&VertexProps::distance,        _g))
            // end named arguments
        );
    }
};

int main() {
    MyGraph g{4};

    g.runSimulation({{0, 1}, {0, 2}, {1, 2}, {2, 1}, {1, 3}, {2, 3}},
                    {10, 1, 10, 1, 1, 10});

}

My questions relate particularly to arcs (1->2) and (2->1).

(a) Boost documentation for the max flow algorithm requires the user to explicitly provide the reverse arcs for each of the arcs in the original input graph. So, in the example above, the directed arcs (1 -> 2) and (2 -> 1) are added to the graph object twice in the following code snippet:

  auto edf  = add_edge(fr, to, _g).first; //Arc (1->2) added, Arc (2->1) added
  auto edr  = add_edge(to, fr, _g).first; //Arc (2->1) added, Arc (1->2) added
  eidx[edf] = 2 * eindex;
  eidx[edr] = eidx[edf] + 1;
  cap[edf]  = cap[edr] = capacities[eindex];
  rev[edf] = edr;
  rev[edr] = edf;

While in this particular example the correctness of the solution could be seen, is this guaranteed in all cases? That is, can the repeated arc addition of the same arc multiple times (once as the forward arc, and once as the reverse arc) to the graph object cause any internal stuff to break in the boost algorithm for this problem?

(b) The boost documentation states the following:

Remarks: While the push-relabel method states that each edge in E^T has to have capacity of 0, the reverse edges for this algorithm ARE allowed to carry capacities. If there are already reverse edges in the input Graph G, those can be used. This can halve the amount of edges and will noticeably increase the performance.

Does this mean that in this particular case, when I add the forward arc (1->2), I need NOT explicitly add the reverse arc (2->1) and likewise when I add the forward arc (2->1), I need NOT explicitly add the reverse arc (1->2) as happened in the code snippet above?

Tryer
  • 3,580
  • 1
  • 26
  • 49
  • 1
    I think the docs couldn't state much more explicitly that you don't need to add the reverse edge twice. – j_random_hacker May 23 '21 at 12:35
  • @j_random_hacker well, usually, in directed network problems, there is a distinction usually made between an edge and an arc. The former is usually undirected, while the latter is directed. I think it is a valid question as to what happens in boost if the graph object has arc (1->2) twice, once with capacity a and another time with capacity b. The documentation can certainly be made more explicit and clearer, imho. – Tryer May 23 '21 at 12:45
  • 2
    Sure, "arc" is common for a directed edge, but so is "edge" -- even Diestel (3rd Ed.) defines digraphs as consisting of vertices and edges. I wouldn't read undirectedness into the documentation's use of the word "edge". – j_random_hacker May 23 '21 at 12:53

0 Answers0