|
The Boost Graph Library (BGL) is a great way to use GraphViz to draw directed and undirected graphs of your data structures.
December 01, 2005
URL:http://www.drdobbs.com/cpp/graphviz-and-c/184402049
GraphViz is a software package for drawing directed and undirected graphs [1]. Developed by AT&T [2], GraphViz is mainly written in C, although newer parts are written in C++ and Java. Bindings for GraphViz exist in many high-level languages. For C++, mfgraph [6] is a simple binding to dot, the GraphViz language, although it appears unmaintained. A more recent binding is contained in the Boost Graph Library (BGL) [7]. The BGL offers a generic interface for representing and manipulating graphs, so its connection to GraphViz is natural. In this article, we present examples of using the BGL to create GraphViz graphs. Although there are graphical tools based on GraphViz that can graphically create graphs, in this article we focus on command-line tools in combination with C++. We use GraphViz 2.0, g++ 3.4.1, and Boost 1.32.0.
There are three major programs for creating graphs, all of which use the dot language:
A graph contains nodes and edges, each of them having attributes. Table 1 shows some of the available attributes for dot nodes, while Table 2 shows part of the available edge attributes. There are also attributes for the graph that are not mentioned here. Similar attributes exist for the NEATO program.
| Name | Explanation | Allowed Values |
| shape | Shape of the node | ellipse, diamond, box, circle, etc. |
| height | Height in inches | number |
| width | Width in inches | number |
| label | Name of the node | alphanumeric |
| fontsize | Size of the font | number |
| fontname | Name of the font | Courier, Helvetica, Times-Roman |
| fontcolor | Color of the font | white, black, blue, etc. |
| style | Style name | bold, dotted, filled, etc. |
| color | Color of the node shape | white, black, etc. |
| pos | Coordinates of the position | — |
| Name | Explanation | Allowed Values |
| label | Label of the edge | alphanumeric |
| fontsize | Size of the font | — |
| fontname | Name of the font | — |
| fontcolor | Color of the font | — |
| style | Style name | bold, dotted, filled, etc. |
| color | Color of the edge | white, black, blue, etc. |
| len | Length of the edge | — |
| dir | Direction of the edge | forward, back, both or none |
| decorate | Draws line that connects labels with their edges | 0 or 1 |
| id | Optional value to denote different edges | alphanumeric |
Before getting the output of a GraphViz source file, the source file should be compiled. The general form of execution is:
toolname -Tps ftc.dot -o output.ps
where toolname denotes the name of the tool to execute (dot, NEATO, or twopi); -Tps denotes that the output file is in PostScript (other supported output formats are GIF, PNG, JPEG, HP-GL/2 vector format, VRML, and FrameMaker MIF); ftc.dot shows the name of the file to be processed; and -o output.ps tells what the output filename should be.
To illustrate how you can use the GraphViz language, we start with the familiar "Hello world!" example. This code produces the output in Figure 1:
digraph G
{
"Hello world!";
}
while this command produces the PostScript file for Figure 1:
dot -Tps hw.dot -o hw.ps
The word digraph means that a directed graph is going to be created. For creating an undirected graph, use the word graph instead.
Listing One is dot code to draw the hash table in Figure 2. The command rankdir = LR denotes that the graph nodes are going to be drawn from left to right. The command node [shape=record, width=.1, height=.1] defines some node attributes. The {} characters inside the label parameter of the nodes tell the dot language to arrange the record parts left to right instead of one above another. Commands of the type nd0:p2 -> nd6:e create the connections between the nodes (the edges of the graph).
digraph G
{
rankdir = LR;
node [shape=record, width=.1, height=.1];
nd0 [label = "<p0> | <p1> | <p2> | <p3> | <p4> | | ", height = 4];
node[ width=1.5 ];
nd1 [label = "{<e> HA0 | 123 | <p> }" ];
nd2 [label = "{<e> HA10 | PIK | <p> }" ];
nd3 [label = "{<e> HA11 | 23 | <p> }" ];
nd6 [label = "{<e> HA20 | 123 | <p> }" ];
nd7 [label = "{<e> HA40 | CUJ | <p> }" ];
nd8 [label = "{<e> HA41 | C++ | <p> }" ];
nd9 [label = "{<e> HA42 | DDJ | <p> }" ];
nd0:p0 -> nd1:e;
nd0:p1 -> nd2:e;
nd2:p -> nd3:e;
nd0:p2 -> nd6:e;
nd0:p4 -> nd7:e;
nd7:p -> nd8:e;
nd8:p -> nd9:e;
}
The command that produces Figure 2 is:
dot -Tps hashtable.dot -o hashtable.ps
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.
#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.
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.
Listing Three presents functions for the row-major and column-major traversal of the tables. Let us describe the first one briefly, which creates a row-major graph representation of a sparse matrix. A node is created for each row (a "row head"), labeled with its number. Then, for each element of that row, a node is created, labeled with the column number of the element and its value; these nodes are shaped as dot "records" so that they can be subdivided into two fields, just like the nodes of the aforementioned hash table. Figure 4 is a graph representation of a sparse matrix; Figure 5 is the graph representation of the same sparse matrix.
#include <boost/numeric/ublas/matrix_sparse.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/graph/graphviz.hpp>
namespace ublas = boost::numeric::ublas;
typedef ublas::sparse_matrix<double> spmd;
typedef boost::GraphvizDigraph Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;
void GraphRowMajor(const spmd& M, std::string dotFile);
void GraphColMajor(const spmd& M, std::string dotFile);
int main()
{
// Construct a sample sparse matrix
spmd M(5, 5);
M(0,0) = 11; M(0,2) = 13;
M(1,0) = 21; M(1,1) = 22;
M(2,2) = 33; M(2,4) = 35;
M(3,3) = 44;
M(4,0) = 52; M(4,4) = 55;
// Construct its row-major and column-major representation
GraphRowMajor(M, "row.dot");
GraphColMajor(M, "col.dot");
}
void GraphRowMajor(const spmd& M, std::string dotFile)
{
// The graph that will represent the matrix
Graph matrixGraph;
// Assign some graph attributes
boost::graph_property<Graph, boost::graph_graph_attribute_t>::
type& graphAttr = boost::get_property(matrixGraph,
boost::graph_graph_attribute);
graphAttr["name"] = "MatrixRowMajor";
graphAttr["rankdir"] = "LR";
// Assign some properties to all nodes of the graph
boost::graph_property<Graph, boost::graph_vertex_attribute_t>::
type& graphVertAttr = boost::get_property(matrixGraph,
boost::graph_vertex_attribute);
graphVertAttr["shape"] = "record";
graphVertAttr["height"] = "0.1";
// Get the propery maps for node (vertex) and edge attributes
const boost::property_map<Graph, boost::vertex_attribute_t>::
type& vertAttr = boost::get(boost::vertex_attribute, matrixGraph);
const boost::property_map<Graph, boost::edge_attribute_t>::
type& edgeAttr = boost::get(boost::edge_attribute, matrixGraph);
// Process the matrix
VertexDescriptor prevHead, curHead;
EdgeDescriptor edge;
bool inserted;
// Cheat: add a vertex to represent the matrix. Format it differently
curHead = boost::add_vertex(matrixGraph);
vertAttr[curHead]["shape"] = "diamond";
vertAttr[curHead]["label"] = "M";
// Iterate through its rows
for (spmd::const_iterator1 it1 = M.begin1(); it1 != M.end1(); ++it1) {
prevHead = curHead;
// Add a vertex for the row head
curHead = boost::add_vertex(matrixGraph);
vertAttr[curHead]["shape"] = "box";
vertAttr[curHead]["label"] = boost::
lexical_cast<std::string>(it1.index1());
// Connect it with the previous row head
tie(edge, inserted) = boost::add_edge(prevHead, curHead, matrixGraph);
edgeAttr[edge]["constraint"] = "false";
edgeAttr[edge]["color"] = "grey";
// Add row elements
VertexDescriptor prevNode, curNode;
prevNode = curHead;
spmd::const_iterator2 it2 = it1.begin();
while (it2 != it1.end()) {
curNode = boost::add_vertex(matrixGraph);
vertAttr[curNode]["label"] =
"{" + boost::lexical_cast<std::string>(it2.index2()) +
" | " + boost::lexical_cast<std::string>(*it2) + "}";
tie(edge,inserted)= boost::add_edge(prevNode,curNode,matrixGraph);
prevNode = curNode;
++it2;
}
}
// Write the dot file
boost::write_graphviz(dotFile, matrixGraph);
}
void GraphColMajor(const spmd& M, std::string dotFile)
{
// The graph that will represent the matrix
Graph matrixGraph;
// Assign some graph attributes
boost::graph_property<Graph, boost::graph_graph_attribute_t>::
type& graphAttr = boost::get_property(matrixGraph,
boost::graph_graph_attribute);
graphAttr["name"] = "MatrixColMajor";
graphAttr["rankdir"] = "TB";
// Assign some properties to all nodes of the graph
boost::graph_property<Graph, boost::graph_vertex_attribute_t>::
type& graphVertAttr = boost::get_property(matrixGraph,
boost::graph_vertex_attribute);
graphVertAttr["shape"] = "record";
graphVertAttr["height"] = "0.1";
// Get the propery maps for node (vertex) and edge attributes
const boost::property_map<Graph, boost::vertex_attribute_t>::
type& vertAttr = boost::get(boost::vertex_attribute, matrixGraph);
const boost::property_map<Graph, boost::edge_attribute_t>::
type& edgeAttr = boost::get(boost::edge_attribute, matrixGraph);
// Process the matrix
VertexDescriptor prevHead, curHead;
EdgeDescriptor edge;
bool inserted;
// Cheat: add a vertex to represent the matrix. Format it differently
curHead = boost::add_vertex(matrixGraph);
vertAttr[curHead]["shape"] = "diamond";
vertAttr[curHead]["label"] = "M";
// Iterate through its columns
for (spmd::const_iterator2 it2 = M.begin2(); it2 != M.end2(); ++it2) {
prevHead = curHead;
// Add a vertex for the column head
curHead = boost::add_vertex(matrixGraph);
vertAttr[curHead]["shape"] = "box";
vertAttr[curHead]["label"] =
boost::lexical_cast<std::string>(it2.index2());
// Connect it with the previous column head
tie(edge, inserted) =
boost::add_edge(prevHead, curHead, matrixGraph);
edgeAttr[edge]["constraint"] = "false";
edgeAttr[edge]["color"] = "grey";
// Add column elements
VertexDescriptor prevNode, curNode;
prevNode = curHead;
spmd::const_iterator1 it1 = it2.begin();
while (it1 != it2.end()) {
curNode = boost::add_vertex(matrixGraph);
vertAttr[curNode]["label"] =
boost::lexical_cast<std::string>(it1.index1()) +
" | " + boost::lexical_cast<std::string>(*it1);
tie(edge, inserted) =
boost::add_edge(prevNode, curNode, matrixGraph);
prevNode = curNode;
++it1;
}
}
// Write the dot file
boost::write_graphviz(dotFile, matrixGraph);
}
GraphViz is a useful set of tools for drawing both directed and undirected graphs. It offers great flexibility either alone or combined with C++ with the help of the Boost Graph Library. In this article, we presented examples that demonstrate how various data structures can be represented as graphs in the BGL and visualized with GraphViz. More advanced uses of the Boost GraphViz C++ interface are possible, which will require more complex handling of the graph structure.
Nikos Platis holds a Ph.D. in computer science from the University of Athens, Greece. His research interests are in multiresolution methods for computer graphics. He can be reached at [email protected]. Mihalis Tsoukalos holds a B.S. in mathematics from the University of Patras in Greece and an M.S. in IT from the University College, London. His research interests are in DBMS. He can be reached at [email protected].
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.