Boost graph - understanding compilation errors and minimal properties

Question

The following code (Snippet 1) compiles fine:

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
typedef adjacency_list_traits<vecS, vecS, undirectedS> Traits_vvu;

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type,
    property<vertex_distance_t, double,
    property<vertex_predecessor_t, Traits_vvd::edge_descriptor>
    > > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits_vvd::edge_descriptor>
> > > > >
Graph_vvd;

class MAXFLOW_ {
public:
    double solve_max_flow(int s, int t){
        double retval = boykov_kolmogorov_max_flow(g, s, t);
        return retval;
    }
private:
    Graph_vvd g;
};

int main(){
    return 0;
}

However, on removing vertex_distance_t and vertex_predecessor_t from the graph, we have this code (Snippet 2) that fails to compile:

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
typedef adjacency_list_traits<vecS, vecS, undirectedS> Traits_vvu;

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type
    > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits_vvd::edge_descriptor>
> > > > >
Graph_vvd;

class MAXFLOW_ {
public:
    double solve_max_flow(int s, int t){
        double retval = boykov_kolmogorov_max_flow(g, s, t);
        return retval;
    }
private:
    Graph_vvd g;
};

int main(){
    return 0;
}

The only difference between Snippet 1 and Snippet 2 is that in the second, there are no vertex properties related to vertex_distance_t and vertex_predecessor_t.

My questions are:

(1) The compilation errors here are unintelligible to me. Is there a way to begin to make sense of the errors and subsequently figure out that one has missed specifying the required properties for proper functioning of the algorithm, in this case algorithm to find the max flow using boykov_kolmogorov method?

(2) On going through the code example provided in boost documentation for this algorithm, available here, indeed the vertices have the required properties:

property < vertex_name_t, std::string,
    property < vertex_index_t, long,
    property < vertex_color_t, boost::default_color_type,
    property < vertex_distance_t, long,
    property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,

But this code also has some unnecessary properties such as vertex_name_t without which Snippet 1 compiled just fine. Is there a way to figure out the bare minimal set of properties to specify for proper functioning of boost algorithms?

Answer 1

The required properties are documented with the algorithm: https://www.boost.org/doc/libs/1_76_0/libs/graph/doc/boykov_kolmogorov_max_flow.html

You can see which arguments are IN/OUT or UTIL, and which of them have defaults (making them non-mandatory unless the default expression is not valid for your graph type).

I've done this repeatedly on your previous questions:

• Boost Graph max-flow algorithm to find out the arcs on the minimal S/T cut where I already reduced to the minimal set of properties¹ and also show how to pass them as named-argument as opposed to relying on internal properties to "magically" pick them up.

  ¹ except perhaps edge-id as I assumed they were essential for your surrounding code, as you had put considerable effort into generating values for that property

• This older answer where I essentially did the same work Boost graph clear_out_edges argument mismatch (but still kept the name property uncommented), and also pointed out the known issue with boykov_kolmogorov_max_flow: Boost max flow algorithms do not compile. error: forming reference to void

In short:

• The compiler messages are daunting. Reading them takes some experience with the library. This is, sadly, an inevitable effect of using C++03 with highly generic templates. If you don't require the raw power of such a generic library, there are probably more user-friendly libraries for graph algorithms out there.

  I say C++03 because newer standards would allow for better diagnostics. Specifically, I'd be thrilled to have a concepts-enabled version of BGL. "Unfortunately" (?) BGL remains C++03 compatible.

• Basically, what you can do is focus on the documentation, instead of the compiler messages. You will still have to grok the messages if you "mess up" something C++-specific, not library-specific (or run into a snag)

• If you're interested in the minimal requirements, focus on the API reference, not the examples. Examples frequently evolved over time, or re-use data/models from other examples so they cannot be assumed to be minimal. (What is minimal might even depend on your choices and preferences some of the time).