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?

sehe · Accepted Answer · 2021-06-25T12:15:26.317

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).

You suggest to look at IN/OUT/UTIL. I can understand IN/OUT, but what is UTIL? What does it stand for? If I understand your answer correctly, everything that has a DEFAULT is a property that must be present. For instance, `vertex_distance` and `vertex_predecessor` are specified on that page with DEFAULTs implying that these properties must be specified (Snippet 1 in my OP) and not omitted (Snippet 2 in my OP). `vertex_name_t` is not mentioned on that page except in the example and hence can be omitted as it is not part of the API. Is this understanding correct? — Tryer, Jun 25 '21 at 12:56
UTIL is neither input nor output, but nevertheless required. It gives you control over the datastructure(s) used for internal/termporary storage, which can impact performance (e.g. by controlling when/where allocations happen). And the inverse for DEFAULT: everything that has a default may be optional (provided that the default expression applies). Indeed `name` is not required by the algorithm. Like I said, focus on the docs, not the examples: the examples may have served different purposes beyond the current example. — sehe, Jun 25 '21 at 22:15

Boost graph - understanding compilation errors and minimal properties

1 Answers1