Some questions about the C++ boost graph library

Question

So I'm posting this because I'm currently working on an algorithm project and might gonna use the boost library for building a graph from an input text file. So I have noticed that there is a descriptor for the vertex in a graph, but since I have a very large graph to be built, do I need to allocate a descriptor for every vertex in that graph? If I don't, can I traverse the whole graph after it's been built?

I'm a newbie to the boost library and this is a little emergent so if anybody can explain this I will be very grateful!

Answer 1

A vertex descriptor describes a vertex (in cheap, graph model independent way).

A graph model describes a graph.

Iterators

When you want to traverse a graph, you traverse the graph, using the iterators:

typedef boost::adjacency_list<> Graph;
typedef Graph::vertex_iterator Vit;

Vit begin, end;
boost::tie(begin, end) = vertices(g);

Dereferencing a valid iterator gives you the descriptor (same thing goes for edge iterators).

Simple demo:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main () {
    typedef boost::adjacency_list<> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g(10);

    add_edge(2,5,g);
    add_edge(5,3,g);
    add_edge(3,8,g);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
    }
}

Prints:

vertex #2 has 1 outgoing edge(s)
vertex #3 has 1 outgoing edge(s)
vertex #5 has 1 outgoing edge(s)

Graph Model With Node-Based Vertex Containers

Not all graph have integral vertex descriptors, so adding edges becomes more complicated, and printing them doesn't look so "friendly"

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main () {
    typedef boost::adjacency_list<boost::setS, boost::listS/*, boost::undirectedS*/> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g(10);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    {
        std::vector<Graph::vertex_descriptor> vindex(begin, end);
        add_edge(vindex[2], vindex[5], g);
        add_edge(vindex[5], vindex[3], g);
        add_edge(vindex[3], vindex[8], g);
    }

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
    }
}

Printing

vertex #0x994d00 has 1 outgoing edge(s)
vertex #0x994d70 has 1 outgoing edge(s)
vertex #0x994e50 has 1 outgoing edge(s)

Properties

In such cases, consider adding a property bundle.

This way, arbitrary application-specific information can be attached to model vertices (or edges, or graphs).

The main downside, in my opinion, of this is that there's no natural indexing for the properties, so looking up a graph entity by its (bundled) property could get bad performance (linear search) unless you keep an extra index outside of the graph manually.

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

struct VertexProperties {
    std::string name;
    VertexProperties(std::string name) : name(name) {}
};

int main () {
    typedef boost::adjacency_list<boost::setS, boost::listS, boost::directedS, VertexProperties> Graph;
    typedef Graph::vertex_iterator Vit;
    Graph g;

    add_vertex(VertexProperties ("zero"), g);
    add_vertex(VertexProperties ("one"), g);
    add_vertex(VertexProperties ("two"), g);
    add_vertex(VertexProperties ("three"), g);
    add_vertex(VertexProperties ("four"), g);
    add_vertex(VertexProperties ("five"), g);
    add_vertex(VertexProperties ("six"), g);
    add_vertex(VertexProperties ("seven"), g);
    add_vertex(VertexProperties ("eight"), g);
    add_vertex(VertexProperties ("nine"), g);

    Vit begin, end;
    boost::tie(begin, end) = vertices(g);

    {
        std::vector<Graph::vertex_descriptor> vindex(begin, end);

        add_edge(vindex[2], vindex[5], g);
        add_edge(vindex[5], vindex[3], g);
        add_edge(vindex[3], vindex[8], g);
    }

    for (Vit it = begin; it != end; ++it) {
        unsigned edges = out_degree(*it, g);
        if (edges)
            std::cout << "vertex '" << g[*it].name << "' has " << edges << " outgoing edge(s)\n";
    }
}

Prints

vertex 'two' has 1 outgoing edge(s)
vertex 'three' has 1 outgoing edge(s)
vertex 'five' has 1 outgoing edge(s)