Personally, I’ve always been ashamed of not writing many programs to work with graphs, but being able to do figure this one out was really nice.
#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
Here are the basic includes for the sample program.
// Use a DIMACS network flow file as stdin.
// Example file found inline at: http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm
// Usage: max_flow < max_flow.dat
int
main()
{
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
// define our graph with so-called internal properties
typedef adjacency_list<listS, vecS, directedS,
// vertex properties
property<vertex_name_t, std::string,
property<vertex_color_t, default_color_type> >,
// edge properties
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, Traits::edge_descriptor> > >
> Graph;
Graph g;
Strictly speaking, the graph itself is restricted to the first three template parameters. The first two parameters tell you how the edges and vertices are represented. In our case, they are both stored in std::vectors – the first two vecS are special types defined in Boost for that. There’s the usual tradeoffs to consider and it’s nice to not have to worry about it. The last parameter tells you if you have a directed or undirected graph – again, using a special Boost type.
All of the properties following the first three are internal properties, which can basically be thought of as associated data specific to either the vertices or the edges. They are internal properties because they are attached to the graph itself, but Boost gives you the option to keep it external if you want. There are a bunch of graph predefined properties that you only bring in when you run an algorithm that makes use of them. In particular, Edmonds-Karp max flow makes use of vertex colors internally.
// make references to the internal properties of the graph
property_map<Graph, edge_capacity_t>::type
capacity = get(edge_capacity, g);
property_map<Graph, edge_reverse_t>::type
rev = get(edge_reverse, g);
property_map<Graph, edge_residual_capacity_t>::type
residual_capacity = get(edge_residual_capacity, g);
property_map<Graph, vertex_color_t>::type
color = get(vertex_color, g);
Traits::vertex_descriptor s, t;
We get references to some of the properties for passing to the algorithm. In this way, we’ll retain the colored vertices and can get what we really want out of max flow, which is the cutset.
// read in the graph from stdin
read_dimacs_max_flow(g, capacity, rev, s, t);
long flow = edmonds_karp_max_flow(g, s, t,
capacity_map( capacity )
.reverse_edge_map( rev )
.residual_capacity_map( residual_capacity )
.color_map( color ));
Here we load in the graph from a dimacs file. Go to the site in the header comment to get a sample file. We pass in all of our relevant data structures to edmonds_karp_max_flow, the last argument being all of the property maps bundled together using those helper functions that chain together.
std::cout << "number of vertices: " << num_vertices(g) << std::endl;
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::cout << "c flow values:" << std::endl;
graph_traits::vertex_iterator u_iter, u_end;
graph_traits::out_edge_iterator ei, e_end;
const char* name = "abcdef";
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
{
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
{
if (capacity[*ei] > 0)
std::cout << "f " << name[*u_iter] << " " << name[target(*ei, g)] << " "
<< (capacity[*ei] - residual_capacity[*ei]) << " "
<< "(" << residual_capacity[*ei] << ")" << std::endl;
}
}
Above is just printing out the flow. Notice how vertices returns a pair of vertex iterators. boost::tie is a macro that lets you assign multiple variables at the same time, like assigning tuples in Perl. You can see how the property maps work – they map the edge or vertex descriptor to the property associated with that descriptor.
std::cout << std::endl << "the min cut:" << std::endl;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
{
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
{
if (color[*u_iter] == color[s] && color[target(*ei, g)] == color[t])
{
// damn yeah
std::cout << name[*u_iter] << "-" << name[target(*ei, g)];
std::cout << " (" << capacity[*ei] << ")" << std::endl;
}
}
}
Finally, this is how to actually get the edges that make up the cutset from the colored vertices. The vertices will be colored based on which partition it ends up being on, and the cut edges are precisely the ones that bridge between the partitions ie. the ones that go from a vertex of one color to a vertex of the other color.
Thoughts
I really had a tough time looking for the usable types and the interfaces to these types. The above program was mostly part of an example program in the documentation, tweaked to include the color map and the code that uses the information to extract the edges. It took my the longest time to figure out how to pass in the color map to the algorithm that I wanted it to use. Even then, I wasn’t sure that I would get something useful in return and it just took rounds of attempted compiles and runs to see what all of the code actually does. I feel like this was much harder than it should have been, but I wonder if it’s something that someone with experience with templated C++ would have an easier time with. It just seems like there’s nothing like a straightforward equivalent of the Java API.
Well let’s post this before I go crazy from the way the editor eats the templates in the C++ code when I toggle between visual and HTML editing.
Feral Chicken 