Wednesday, July 30, 2008

Boost graph bundle + write_graphviz

I couldn't find a decent example of using the new Boost Graph library "bundle" functionality with write_graphviz, so I created one:




 foo.cpp






// first, the standard libraries
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <iterator>
#include <vector>
#include <queue>

// boost and other semi-standards should go here
#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/shared_array.hpp>
#include <boost/scoped_array.hpp>
#include <boost/graph/graphviz.hpp>

#include <sys/times.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using std::string;
using std::vector;
using namespace boost;
using std::ostream;
using std::ofstream;
using std::multiset;
using std::pair;
using std::multimap;
using std::map;

struct City
{
  string name;
  int population;
  vector<int> zipcodes;
};
      
struct Highway
{
  string name;
  double miles;
  int speed_limit;
  int lanes;
  bool divided;
};
      
typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway> Map;
      
void outputgraph(Map&);

main()
{
        Map map; // load the map
        bool inserted;

        Map::vertex_descriptor v = add_vertex(map);
        Map::edge_descriptor e;

        map[v].name = "Troy";
        map[v].population = 49170;
        map[v].zipcodes.push_back(12180);
        tie(e,inserted) = add_edge(v, v, map);
        if (inserted) {
                map[e].name = "I-87";
                map[e].miles = 10;
                map[e].speed_limit = 65;
                map[e].lanes = 4;
                map[e].divided = true;
        }

        vector<double> distances(num_vertices(map));
        Map::vertex_descriptor from = *vertices(map).first;
        dijkstra_shortest_paths(map, from,
                                weight_map(get(&Highway::miles, map))
                                .distance_map(make_iterator_property_map(distances.begin(),
                                                                         get(vertex_index, map))));
        graph_traits < Map >::vertex_iterator vi, vend;
        for (tie(vi, vend) = vertices(map); vi != vend; ++vi) {
                std::cout << "name " << map[*vi].name <<
                        ", " << "population " << map[*vi].population;
        }
        std::cout << std::endl;

        outputgraph(map);
}

struct my_node_writer {
        // my_node_writer() {}
        my_node_writer(Map& g_) : g (g_) {};
        template <class Vertex>
        void operator()(std::ostream& out, Vertex v) {
                out << " [label=\"" << v << "\"]" << std::endl;
        };
        // bleah.  I can't get references right...
        // according to http://www.knowledgesearch.org/doc/examples.html
        // it should be a reference here, not the type itself.
        // but g++ either barfs, or the program segfaults.
        Map g;
};

struct my_edge_writer {
        my_edge_writer(Map& g_) : g (g_) {};
        template <class Edge>
        void operator()(std::ostream& out, Edge e) {
                // just an example, showing that local options override global
                out << " [color=purple]" << std::endl;
                out << " [label=\"" << e  <<":" << g[e].miles << "\"]" << std::endl;
        };
        Map g;
};

struct my_graph_writer {
        void operator()(std::ostream& out) const {
                out << "graph [bgcolor=lightgrey]" << std::endl;
                out << "node [shape=circle color=blue]" << std::endl;
                // just an example, showing that local options override global
                out << "edge [color=red]" << std::endl;
        }
} myGraphWrite;

void outputgraph(Map& map){
        std::ofstream gout;
        gout.open("graphname.dot");
        write_graphviz(gout,map,my_node_writer(map),my_edge_writer(map),myGraphWrite);
        // std::cout() << "done writing graph" << std::endl;
}