Accessing specific vertices in boost::graph

Question

I mostly work with my own network flow algorithms. However, I have just begun using boost recently, but am struggling to define graphs. More specifically, vertices in my own code are numbered 0 through n-1. Edges are numbered 0 through m-1. I am trying to build a very simple network with 4 edges.

The capacity of all four edges is 4 units. I am looking for boost to find me a maximum flow from s = 0 to t = 3. (The answer is 8.)

To get this to run, I have the following code, but although it compiles and builds without errors, the code is not doing what I expect. Please see comments in the code for my specific questions. There are two questions (Q1) and (Q2).

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>


using namespace boost;


typedef adjacency_list_traits < vecS, vecS, directedS > Traits;

typedef adjacency_list < vecS, vecS, directedS,

    property < vertex_name_t, std::string,
    property < vertex_index_t, int,
    property < vertex_color_t, boost::default_color_type,
    property < vertex_distance_t, double,
    property < vertex_predecessor_t, Traits::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::edge_descriptor > > > > > > Graph;

int main()
{
    Graph g;
    property_map<Graph, vertex_index_t>::type v = get(vertex_index, g);
    property_map<Graph, edge_index_t>::type e = get(edge_index, g);
    property_map<Graph, edge_capacity_t>::type cap = get(edge_capacity, g);
    property_map<Graph, edge_weight_t>::type cost = get(edge_weight, g);
    property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
    property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);

    int nonodes = 4;

    for (int i = 0; i < nonodes; i++) {
        Traits::vertex_descriptor vd;
        vd = add_vertex(g);
        assert(v[vd] == i);//(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?
    }

    Graph::vertex_iterator vertexIt, vertexEnd;
    tie(vertexIt, vertexEnd) = vertices(g);

    //Create edges
    Traits::edge_descriptor edf, edb;//Max flow algorithms seem to want both forward and backward edges. edf is for forward, edb is for backward

//Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error when boykov_kolmogorov_max_flow() is finally called.
    edf = (add_edge(*(vertexIt+0), *(vertexIt + 1), g)).first;
    edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;
    e[edf] = 0;
    e[edb] = 1;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 0), *(vertexIt + 2), g)).first;
    edb = (add_edge(*(vertexIt + 2), *(vertexIt + 0), g)).first;
    e[edf] = 2;
    e[edb] = 3;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 1), *(vertexIt + 3), g)).first;
    edb = (add_edge(*(vertexIt + 3), *(vertexIt + 1), g)).first;
    e[edf] = 4;
    e[edb] = 5;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 2), *(vertexIt + 3), g)).first;
    edb = (add_edge(*(vertexIt + 3), *(vertexIt + 2), g)).first;
    e[edf] = 6;
    e[edb] = 7;
    cap[edf] = 4;
    cap[edb] = 4;

    double flow = boykov_kolmogorov_max_flow(g, *(vertexIt + 0), *(vertexIt + 3));
    return 0;
}

Regarding Q1) I looked up the solution provided On C++ Boost Graph Creation and the vertex_index Property.. However, it is unclear to me why v[vd] = i; causes a compile time error, but e[edf] = 0; later on does not cause a compile time error.

Regarding Q2) What I am really looking for is a way to access vertices to pass to the add_edge() function. More generally, is there a way to access the 2nd edge (counting from 0) via some mechanism such as vertex[2] or to access the 3rd edge (counting from 0) via some mechanism such as edge[3], etc.?

Answer 1

i); //(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?

When you use vecS the vertex index is implicit and is the integral index into the vertex vector. Hence, you cannot assign it without physically shuffling the vertices around.

However, you are free to do without the built-in implicit vertex index, by selecting a non-random access vertex container, e.g. listS.

HOWEVER: if you do, you can (obviously) no longer use the ID as a vertex descriptor, making all the code like

edf = (add_edge(*(vertexIt + 0), *(vertexIt + 1), g)).first;
edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;

very clumsy, more like

auto find_vertex_by_id = [&g](size_t id) {
    for(auto vd : boost::make_iterator_range(boost::vertices(g)))
        if (id == g[vd])
            return vd;
    throw std::range_error("vertex id " + std::to_string(id));
};

edf = (add_edge(find_vertex_by_id(g[*vertexIt].id + 0), find_vertex_by_id(g[*vertexIt].id + 1), g)).first;
edb = (add_edge(find_vertex_by_id(g[*vertexIt].id + 1), find_vertex_by_id(g[*vertexIt].id + 0), u)).first;

See it Live On Coliru, I hope you agree it's aggravating.

Note it also crashes. Don't worry, that's a minor issue (mainly because the reverse edge map is not built up correctly). Fixing that, quickly, gives you the elusive Flow: 8! Sneak Preview

I'd suggest to go the other way! Embrace implicit vertex index, which coincides with the descriptor type. Then, don't bother with the roundabout way with iterators, just address absolutely:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <iostream>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits;

typedef adjacency_list<
    vecS, vecS, directedS,

    property<
        vertex_name_t, std::string,
        property<vertex_index_t, int,
        property<vertex_color_t, boost::default_color_type,
        property<vertex_distance_t, double,
        property<vertex_predecessor_t, Traits::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::edge_descriptor>
    > > > > >
    Graph;

int main() {
    Graph g;
    property_map<Graph, edge_index_t>::type             e      = get(edge_index,             g);
    property_map<Graph, edge_capacity_t>::type          cap    = get(edge_capacity,          g);
    //property_map<Graph, edge_weight_t>::type            cost   = get(edge_weight,            g);
    //property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
    property_map<Graph, edge_reverse_t>::type           rev    = get(edge_reverse,           g);

    int nonodes = 4;

    for (int i = 0; i < nonodes; i++) {
        Traits::vertex_descriptor vd;
        vd = add_vertex(g);
        assert(vd == i);
    }

    // Create edges
    Traits::edge_descriptor edf, edb; // Max flow algorithms seem to want both forward and backward edges. edf is for
                                      // forward, edb is for backward

    // Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error
    // when boykov_kolmogorov_max_flow() is finally called.
    edf = (add_edge(0, 1, g)).first;
    edb = (add_edge(1, 0, g)).first;

    e[edf] = 0;
    e[edb] = 1;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(0, 2, g)).first;
    edb = (add_edge(2, 0, g)).first;
    e[edf] = 2;
    e[edb] = 3;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(1, 3, g)).first;
    edb = (add_edge(3, 1, g)).first;
    e[edf] = 4;
    e[edb] = 5;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(2, 3, g)).first;
    edb = (add_edge(3, 2, g)).first;
    e[edf] = 6;
    e[edb] = 7;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    double flow = boykov_kolmogorov_max_flow(g, 0, 3);
    std::cout << "Flow: " << flow << "\n";
}

Prints

Flow: 8

Isn't that much better? Now, let's keep chipping away at whatever is still ugly/annoying

Bonus 1: just create 4 nodes, already

The add_vertex loop now seems rather impotent:

for (int i = 0; i < nonodes; i++) {
    Traits::vertex_descriptor vd;
    vd = add_vertex(g);
    assert(vd == i);
}

Indeed, let's just write:

Graph g(nonodes);

Bonus 2: Bundle those properties

At the cost of making it necessary to pass the property maps to the algorithms, you can make building the graph a lot more palatable by using Bundled Properties:

Live On Coliru

Wait - what? That's not an improvement, is it? Well, wait until you see this:

struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
int edge_id = 0;
for (auto& edge : edges) {
    auto edf = add_edge(edge.from, edge.to, EdgeProperty{edge_id++, 4}, g).first,
         edb = add_edge(edge.to, edge.from, EdgeProperty{edge_id++, 4}, g).first;

    rev[edf] = edb;
    rev[edb] = edf;
}

Live On Coliru

Yay!

Bonus 3: separate temporary vertex properties out

Those flow-algorithm specific properties don't really belong in the graph, so why have them in? Let's do some fancy footwork and use external maps. This is starting to get advanced but really drives home the point of property-maps: they're like lenses for C++.

Presented without comment:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <functional>
#include <iostream>

using namespace boost;

struct VertexProperty { std::string name; };

struct EdgeProperty {
    int id;
    double capacity, residual_capacity;

    EdgeProperty(int id, double cap, double res = 0)
        : id(id), capacity(cap), residual_capacity(res)
    { }
};

typedef adjacency_list<vecS, vecS, directedS, VertexProperty, EdgeProperty> Graph;

int main() {
    int nonodes = 4;
    Graph g(nonodes);

    // reverse edge map
    auto e      = get(&EdgeProperty::id, g);
    auto rev    = make_vector_property_map<Graph::edge_descriptor>(e);

    // Create edges
    struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
    int edge_id = 0;

    for (auto& pair : edges) {
        auto a = add_edge(pair.from, pair.to, EdgeProperty { edge_id++, 4 }, g).first;
        auto b = add_edge(pair.to, pair.from, EdgeProperty { edge_id++, 4 }, g).first;
        rev[a] = b;
        rev[b] = a;
    }

    // property maps
    struct VertexEx {
        default_color_type color;
        double distance;
        Graph::edge_descriptor pred;
    };

    auto idx    = get(vertex_index, g);
    auto vex    = make_vector_property_map<VertexEx>(idx);
    auto pred   = make_transform_value_property_map(std::mem_fn(&VertexEx::pred),     vex);
    auto color  = make_transform_value_property_map(std::mem_fn(&VertexEx::color),    vex);
    auto dist   = make_transform_value_property_map(std::mem_fn(&VertexEx::distance), vex);

    auto cap    = get(&EdgeProperty::capacity, g);
    auto rescap = get(&EdgeProperty::residual_capacity, g);

    // algorithm
    double flow = boykov_kolmogorov_max_flow(g, cap, rescap, rev, pred, color, dist, idx, 0, 3);
    std::cout << "Flow: " << flow << "\n";
}

Bonus 4: also for edge property maps

Live On Coliru, presented with even less comment.