Adding edges to a graph in Boost.Graph

Question

I am trying to use the Boost.Graph Library to run Goldberg's Max-Flow Algorithm. Boost.Graph calls it push_relabel_max_flow.

However, I have a very hard time understanding the library and its type-system. The documentation, which I linked above, gives an example code. But in that example, the graph is read from a file. I want to generate the graph at runtime. This is the code I have so far (mostly copied from the example):

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 
        boost::property<boost::vertex_name_t, std::string>, 
        boost::property<boost::edge_capacity_t, long, 
            boost::property<boost::edge_residual_capacity_t, long, 
                boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> DirectedGraph;

DirectedGraph g;
Traits::vertex_descriptor s, t;


s = boost::add_vertex(g);
t = boost::add_vertex(g);
boost::add_vertex(g);
boost::add_vertex(g);

After I added 4 vertices to the graph I should "connect" them, i.e., making edges with a capacity, residual capacity and the reverse value. The function for this task is boost::add_edge() but I have no clue how I can pass my arguments. The example code does not show it, because as I said, the data is read from a file and then directly parsed to a graph. Maybe someone with experience in the Boost.Graph library can show me how.

Answer 1

You can add an edge between vertices s and t like so:

boost::add_edge(s, t, {33, 44}, g);

Here setting edge_capacity to 33, and edge_residual_capacity to 44.

To actually access the edge properties, as far as I know you must do something like this:

std::cout << boost::get(boost::edge_capacity, g, boost::edge(s,t,g).first) << '\n';

which is annoying. It's easier if you use bundled properties instead, like so:

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;

struct VertexProps {
    std::string name;
};

struct EdgeProps {
    long capacity;
    long residual_capacity;
    Traits::edge_descriptor reverse;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                              VertexProps, EdgeProps > DirectedGraph;

Then you can add vertices and edges just the same way, but it's easier to access edge properties, e.g.

auto e = boost::edge(s,t,g).first; // get the edge descriptor for an edge from s to t, if any
std::cout << g[e].capacity << '\n';

To add an edge between the anonymous third and fourth vertices you added, you can get away with

boost::add_edge(2, 3, {17, 26}, g);

since the underlying storage is vector, and so vertex_descriptor is just the vector index (aka size_t, aka unsigned long around here). But to be more strictly correct you should do

boost:add_edge(boost::vertex(2, g), boost::vertex(3, g), {17, 26}, g);

in order to get the vertex_descriptor for the 3rd and 4th vertices.