Boost Graph Library

The Boost Graph Library (BGL) is a library that defines a generic interface for graph as well as providing a few general class that implements this interface and some generic algorithm for graphs.

The Boost Graph Libray is part of Boost, a collection of non standard C++ libraries. You can find more information about the BGL in its documentation.

In our case, we will use the Boost Graph Library to create and manipulate the control flow graph and the interference graph at TC-8 and TC-9.

Vertices iterators:

// Returns an iterator-range providing access to all the vertices in the graph g.
std::pair<vertex_iterator, vertex_iterator> vertices(Graph g)

// Returns an iterator-range providing access to the vertices adjacent to vertex v in graph g.
std::pair<vertex_iterator, vertex_iterator> adjacent_vertices(vertex_descriptor v, Graph g)

Edges iterators:

// Returns an iterator-range providing access to all the edges in the graph g.
std::pair<edge_iterator, edge_iterator> edges(Graph g)

// Returns an iterator-range providing access to the in-edges of vertex v in graph g.
std::pair<vertex_iterator, vertex_iterator> in_edges(vertex_descriptor v, Graph g)

// Returns an iterator-range providing access to the out-edges of vertex v in graph g.
std::pair<vertex_iterator, vertex_iterator> out_edges(vertex_descriptor v, Graph g)

Access:

// Returns a pair consisting of a boolean indicating whether there is an edge
// between u and v in graph g, and the edge descriptor if the edge was found.
std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor, v, Graph g)

// Returns the label of the given vertex v in the graph g.
VertexLabel operator[](vertex_descriptor v)

// Returns the vertex descriptor for u of the edge (u, v) represented by e.
vertex_descriptor source(edge_descriptor e, Graph g)

// Returns the vertex descriptor for v of the edge (u, v) represented by e.
vertex_descriptor target(edge_descriptor e, Graph g)

Counts:

// Returns the number of vertices in the graph g.
vertices_size_type num_vertices(Graph g)

// Returns the number of in-edges and out-edges (for directed graphs) or
// the number of incident edges (for undirected graphs) of vertex v in graph g.
degree_size_type degree(vertex_descriptor v, Graph g)

// Returns the number of in-edges (for directed graphs) or the number of
// incident edges (for undirected graphs) of vertex v in graph g.
degree_size_type in_degree(vertex_descriptor v, Graph g)

// Returns the number of out-edges (for directed graphs) or the number of
// incident edges (for undirected graphs) of vertex v in graph g.
degree_size_type out_degree(vertex_descriptor v, Graph g)

Adaptor:

// Construct a reversed version of the graph g, effectively flipping all in-edges and out-edges.
reverse_graph(BidirectionalGraph& g)