GraphViz and C++

Listing Three

#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);
}

Figure 4: Graph representation of the sparse matrix (row-major).

Figure 5: Graph representation of the sparse matrix (column-major) in Figure 4.

Conclusion

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.

References

1. GraphViz development web site: http://www.graphviz.org/.
2. Official GraphViz web site: http://www.research.att.com/sw/tools/ graphviz/.
3. Junger, Michael and Petra Mutzel (editors). Graph Drawing Software, Mathematics + Visualization, Springer, ISBN 3540008810.
4. Kamada, T. and S. Kawai. "An Algorithm for Drawing General Undirected Graphs," Information Processing Letters, April 1989.
5. Gansner, Emden R., Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. "A Technique for Drawing Directed Graphs," IEEE Trans. Software Engineering, May 1993.
6. http://www.geocities.com/foetsch/mfgraph/index.htm.
7. Boost Library web site: http://www.boost.org/.

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].