Integrating GraphViz and C++
The BGL contains an interface to the dot language. The function read_graphviz(fname, g) can be used to construct a BGL graph g from its representation in the .dot file with the given filename, and the function write_graphviz(fname, g) writes a BGL graph g in dot language in the given file. The graph g that can be used in these functions must be of the specific type boost::GraphvizGraph or boost::GraphvizDigraph, for undirected and directed graphs, respectively. These types carry node and edge attributes in a form suitable for expression in the dot language, namely as pairs of std::string(s), where the first string is the dot attribute name (for instance, shape) and the second one is the attribute value (box, for example). These attributes are accessed through attribute maps (they really are multimaps, in STL terms), which map a vertex to its attributes.
Suppose you want to draw a graph representing the directory structure of a filesystem. In this graph, the nodes will be the directories of the filesystem, and the (directed) edges will connect each directory to its subdirectories. The traversal of the directory hierarchy can be performed in a simple and portable way with the help of the Boost Filesystem Library. Listing Two is our program.
Listing Two
#include <iostream>
#include <string>
#include <boost/lexical_cast.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/exception.hpp>
#include <boost/graph/graphviz.hpp>
namespace bfs = boost::filesystem;
typedef boost::GraphvizDigraph Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
bool TraversePath(bfs::path topDir, VertexDescriptor topDirVertex,
unsigned int depth, Graph& treeGraph);
VertexDescriptor CreateVertex(std::string dirName, Graph& treeGraph);
int main(int argc, char* argv[])
{
// Parse command line arguments
if (argc != 3) {
std::cerr << "Usage: dirtree <topDir> <depth>" << std::endl;
return -1;
}
bfs::path topDir(argv[1]);
if (!is_directory(topDir)) {
std::cerr << "Usage: dirtree <topDir> <depth>" << std::endl;
return -1;
}
unsigned int depth;
try {
depth = boost::lexical_cast<unsigned int>(argv[2]);
}
catch (boost::bad_lexical_cast&) {
std::cerr << "Usage: dirtree <topDir> <depth>" << std::endl;
return -1;
}
// Construct the graph
Graph treeGraph;
VertexDescriptor topDirVertex =
CreateVertex(topDir.native_directory_string(), treeGraph);
TraversePath(topDir, topDirVertex, depth, treeGraph);
// Set properties of the graph
boost::graph_property<Graph, boost::graph_graph_attribute_t>::
type& graphAttr = boost::get_property(treeGraph,
boost::graph_graph_attribute);
graphAttr["name"] = "treeDir";
graphAttr["rankdir"] = "LR";
// Set properties that apply to all the nodes of the graph
boost::graph_property<Graph, boost::graph_vertex_attribute_t>::
type& graphVertAttr = boost::get_property(treeGraph,
boost::graph_vertex_attribute);
graphVertAttr["shape"] = "box";
graphVertAttr["height"] = "0.1";
// Output the graph
boost::write_graphviz("1.dot", treeGraph);
std::cout << num_vertices(treeGraph) << std::endl;
}
bool TraversePath(bfs::path topPath, VertexDescriptor topDirVertex,
unsigned int depth, Graph& treeGraph)
{
// Safety checks
if (!bfs::exists(topPath)) {
return false;
}
bfs::directory_iterator dirIter, endIter;
try {
dirIter = bfs::directory_iterator(topPath);
}
catch (bfs::filesystem_error& err) {
// We cannot traverse this directory, mark it with a dashed line
std::cerr << "Error: " << err.what() << std::endl;
const boost::property_map<Graph, boost::vertex_attribute_t>::
type& vertAttr = boost::get(boost::vertex_attribute, treeGraph);
vertAttr[topDirVertex]["style"] = "dashed";
return false;
}
try {
for ( ; dirIter != endIter; ++dirIter) {
// Process only directories under topPath (discard files)
if (is_directory(*dirIter)) {
VertexDescriptor newVertex =
CreateVertex(dirIter->leaf(), treeGraph);
add_edge(topDirVertex, newVertex, treeGraph);
if (depth > 1) {
// Recursion through the subdirectory
TraversePath(*dirIter, newVertex, depth-1, treeGraph);
}
}
}
}
catch (bfs::filesystem_error& err) {
std::cerr << "Error: " << err.what() << std::endl;
return false;
}
return true;
}
VertexDescriptor CreateVertex(std::string dirName, Graph& treeGraph)
{
// Add the vertex
VertexDescriptor vertex = add_vertex(treeGraph);
// Add its property
const boost::property_map<Graph, boost::vertex_attribute_t>::
type& vertAttrMap = boost::get(boost::vertex_attribute, treeGraph);
vertAttrMap[vertex]["label"] = dirName;
return vertex;
}
The hierarchy traversal starts at a given path. For each subdirectory encountered, a node is added to the graph labeled with its name, and an edge connects it with its parent directory. The process continues recursively, until either no more subdirectories exist or a maximum recursion depth is reached.
The resulting file must be processed with dot to produce the graphical representation of the directory tree. Unfortunately, for deep and involved hierarchies, the graph produced can be very complex. Figure 3 presents a sample directory structure visualized as a graph.
Figure 3: Sample directory.
Another example is a sparse matrix, which is a matrix in which most values are equal to zero. To reduce storage costs, such matrices are represented by storing only the values and coordinates of their non-zero elements. One interface to sparse matrices is provided by uBLAS, the Boost Basic Linear Algebra Library. uBLAS provides different storage models for the sparse matrices, each of them suitable for different access patterns. Typical of C++, their interface is identical, and for this example we use the class sparse_matrix. Iteration through the matrix elements is provided by two iterator classes for the rows and columns of the matrix, respectively.
