Finding the cutset with Boost

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.

New desktop

For Christmas, I got a sweet new desktop computer, which is definitely going to come in handy for who-knows-what sort of crazy algorithms I’ll be running in the years to come. Without further ado, the details:

  • Intel i7 950
  • Asus P6X58D-E Motherboard
  • OCZ Gold PC12800 DDR3 Triple Channel Memory
  • OCZ Vertex 60GB SSD
  • Thermaltake TR2 RX 750W PSU
  • Scythe Mugen SCINF-1000 Heatsink

Thanks Tuan for the help!

Vim sessions and map leader

So a common use case when you’re hacking away at a project in an IDE is that you’ve got several files open in tabs in different locations. You can have this using Vim by opening tabs or split window views, and it’s really nice especially when you’ve got full 1080p worth of screen space to exploit. The problem is when you exit Vim, you have to close all your tabs and you lose all of your context, especially when you put the project away for a little while, it can be annoying to open up all the files. There’s a simple fix for that, and it’s the mksession command.

Just running :mksession in Vim will create a snapshot of your tab and window layout etc. and save it in a session file. You can check the help on the command for the exact details. Here’s a convenient mapping that lets me hit ,wq and have all files written and tabs saved in a session file.

let mapleader=","
:map <leader>wq :wa:mksession!:qa
:map <leader>ls :source Session.vim

So my map leader is the comma. Hitting that puts Vim in a mode where if you complete one of the map rules, the corresponding command will be executed.

The first command executes three commands. First, it writes all files that are open. Then it creates a session file into Session.vim in the current working directory. The exclamation mark means overwrite Session.vim if it exists already. Last, it exits out of Vim by closing all open tabs.

The second command sets up Vim from the Session.vim in the current working directory. You run this the very first thing you do when you open Vim in the directory where your work is at, and your workspace is restored to exactly the way you left it.

I guess having the map leader is what makes this effective because it opens up a whole new range of keystrokes for defining new mappings. Some other ideas: toggle paste mode when pasting from the system clipboard. I always have to type :set paste and :set nopaste whenever I need to bring stuff into Vim through the clipboard without having the indentation go haywire, but you now I’ve got this in my rc file:

set pastetoggle=pp

Any other ideas people have? Did you already know about this? I’m constantly learning new stuff about Vim – that is, whenever I’m not just using it to do work and actually poking about the documentation and configuration.

Hi 2011

WordPress just emailed to say that I averaged one post per month in 2010 and that that is great. I guess I can do better. I even missed the first post opportunity on January 1, 2011 – not a great start blogging…

On the other hand, I made a good start programming on my sweet new desktop – I owe a shout-out and some details about my new desktop on Wednesday. It took a while but I figured out how to find the edges in a min-cut of a graph in C++ using the Boost library. It was *such* a headache trying to figure things out from the docs and making sense of the generic code. I think I’ll give it some time to sink in but I’ll definitely write about how its done, my impression of BGL, and thoughts on graphs in general by Friday. Along the way, I found yet more cool stuff with vim, which I’ll write about on Monday.

Winter quarter starts here at UC Davis tomorrow. Aside from taking courses in algorithms, network theory, and neuroimaging, I’m going to be a TA for introductory C programming. The prof said besides teaching the language, he also wanted to introduce applications, both old and new, to sort of motivate/reinforce the learning. It’s an interesting question: what’s new and interesting that people are doing with C? This is an ongoing question to think about and try to answer this quarter.

If there’s some new year’s resolution that I’ll take seriously, it’s to read more code. I’m going to renew my efforts in following some interesting open source projects and mailing lists, follow some bugs, and read some code that way. I don’t know yet what I’ll write about as commentary, but there’s bound to be interesting things worth mention.