Traversing Vertices and Edges

Once you've created a graph, you'll need to access its vertices and edges. BGL provides several iterator-based interfaces for traversing graph structure.

Accessing All Vertices

The VertexListGraph interface provides the vertices() function, which returns a pair of vertex iterators:

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

using namespace boost;

typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

int main()
{
    Graph g(5);
    // ... add edges ...
    
    // Get vertex iterators
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    std::pair<vertex_iter, vertex_iter> vp;
    
    std::cout << "Vertices: ";
    for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
        std::cout << *vp.first << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Vertices: 0 1 2 3 4

Note: Dereferencing a vertex iterator gives a vertex descriptor, which is an opaque handle used to access vertex information. When using vecS for the VertexList, vertex descriptors are just integers.

Accessing All Edges

The EdgeListGraph interface provides the edges() function, which returns a pair of edge iterators:

typedef graph_traits<Graph>::edge_iterator edge_iter;
edge_iter ei, ei_end;

std::cout << "Edges: ";
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
    std::cout << "(" << source(*ei, g) << ","
              << target(*ei, g) << ") ";
}
std::cout << std::endl;

Output:

Edges: (0,1) (0,3) (2,0) (3,2) (2,4) (1,3) (3,4)

Note: We use boost::tie() as a convenient way to assign both iterators in one line. The source() and target() functions extract the endpoints of an edge.

Out-Edges of a Vertex

The IncidenceGraph interface provides out_edges() to access all edges leaving a vertex:

typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::out_edge_iterator out_edge_iter;

Vertex v = 0;  // vertex to examine

std::cout << "Out-edges of vertex " << v << ": ";
out_edge_iter out_i, out_end;
for (boost::tie(out_i, out_end) = out_edges(v, g); 
     out_i != out_end; ++out_i) {
    Vertex src = source(*out_i, g);
    Vertex targ = target(*out_i, g);
    std::cout << "(" << src << "," << targ << ") ";
}
std::cout << std::endl;

Output for vertex 0:

Out-edges of vertex 0: (0,1) (0,2) (0,3) (0,4)

In-Edges of a Vertex (Bidirectional Graphs Only)

If you created your graph with bidirectionalS, you can also access in-edges using the BidirectionalGraph interface:

typedef graph_traits<Graph>::in_edge_iterator in_edge_iter;

std::cout << "In-edges of vertex " << v << ": ";
in_edge_iter in_i, in_end;
for (boost::tie(in_i, in_end) = in_edges(v, g);
     in_i != in_end; ++in_i) {
    Vertex src = source(*in_i, g);
    Vertex targ = target(*in_i, g);
    std::cout << "(" << src << "," << targ << ") ";
}
std::cout << std::endl;

Output for vertex 0:

In-edges of vertex 0: (2,0)

Important: in_edges() is only available when using bidirectionalS. Using it requires extra memory to store reverse edges.

Adjacent Vertices

Sometimes you only care about which vertices are reachable, not the edges themselves. The AdjacencyGraph interface provides adjacent_vertices():

typedef graph_traits<Graph>::adjacency_iterator adjacency_iter;

std::cout << "Adjacent vertices of " << v << ": ";
adjacency_iter ai, ai_end;
for (boost::tie(ai, ai_end) = adjacent_vertices(v, g);
     ai != ai_end; ++ai) {
    std::cout << *ai << " ";
}
std::cout << std::endl;

Output for vertex 4:

Adjacent vertices of 4: 0 1

Using boost::tie()

The boost::tie() utility function (from the Boost.Tuple library) makes code more concise by unpacking iterator pairs:

// Without tie - more verbose
std::pair<vertex_iter, vertex_iter> vp = vertices(g);
for (; vp.first != vp.second; ++vp.first) { ... }

// With tie - cleaner
vertex_iter vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { ... }

Vertex and Edge Descriptors

It's important to understand that vertex and edge iterators give you descriptors, not actual data:

Vertex descriptor: An opaque handle to a vertex. For vecS graphs, it's just an integer. For listS graphs, it's a more complex handle.
Edge descriptor: An opaque handle to an edge. Contains information to locate the edge in the graph data structure.

You use descriptors with functions like source(), target(), out_edges(), etc., to access graph structure and properties.

Degree of a Vertex

You can get the number of out-edges (out-degree) or in-edges (in-degree) of a vertex:

typedef graph_traits<Graph>::degree_size_type degree_t;

Vertex v = 0;

degree_t out_deg = out_degree(v, g);
std::cout << "Out-degree of vertex " << v << ": " << out_deg << std::endl;

// For bidirectional graphs only:
degree_t in_deg = in_degree(v, g);
std::cout << "In-degree of vertex " << v << ": " << in_deg << std::endl;

// Total degree (for undirected graphs or bidirectional)
degree_t deg = degree(v, g);  // out_degree + in_degree for directed

Checking if an Edge Exists

Use the edge() function to check if an edge exists between two vertices:

Vertex u = 0, v = 1;
std::pair<Graph::edge_descriptor, bool> result = edge(u, v, g);

if (result.second) {
    std::cout << "Edge (" << u << "," << v << ") exists" << std::endl;
} else {
    std::cout << "Edge (" << u << "," << v << ") does not exist" << std::endl;
}

The time complexity of edge() depends on your OutEdgeList choice:

vecS, listS: O(E/V) (linear search)
setS: O(log(E/V)) (binary search)
hash_setS: O(1) average (hash lookup)

Complete Example

Here's a complete example that demonstrates all traversal methods:

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

using namespace boost;

int main()
{
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
    typedef graph_traits<Graph>::vertex_descriptor Vertex;
    
    Graph g(5);
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 3, g);
    add_edge(2, 3, g);
    add_edge(3, 4, g);
    
    // Iterate over all vertices
    std::cout << "All vertices: ";
    auto vp = vertices(g);
    for (auto vi = vp.first; vi != vp.second; ++vi)
        std::cout << *vi << " ";
    std::cout << "\n\n";
    
    // For each vertex, show its adjacency
    for (auto vi = vp.first; vi != vp.second; ++vi) {
        Vertex v = *vi;
        std::cout << "Vertex " << v << ":\n";
        
        std::cout << "  Out-degree: " << out_degree(v, g) << "\n";
        std::cout << "  In-degree: " << in_degree(v, g) << "\n";
        
        std::cout << "  Out-edges: ";
        auto oep = out_edges(v, g);
        for (auto ei = oep.first; ei != oep.second; ++ei)
            std::cout << "(" << source(*ei, g) << "," 
                      << target(*ei, g) << ") ";
        std::cout << "\n";
        
        std::cout << "  Adjacent: ";
        auto ap = adjacent_vertices(v, g);
        for (auto ai = ap.first; ai != ap.second; ++ai)
            std::cout << *ai << " ";
        std::cout << "\n\n";
    }
    
    return 0;
}