This article describes a small workaround for a "shortcoming" of Boost Graph. My situation is the following: Given a directed graph, I want to display just the component containing a special node. Technically speaking I'm looking for the connected component containing a special node. Although Boost Graph comes with plenty of algorithms, there is no direct function for this.
For this discussion we will use the following graph: 
0 -> 1
0 -> 2
1 -> 2
4 -> 3
If the graph was undirected we could use boost::connected_components and be happy. But this algorithm is not made for directed graphs and correspondingly gives bad results; we get three components for our graph:
Node: 0 component: 0
Node: 1 component: 0
Node: 2 component: 0
Node: 3 component: 1
Node: 4 component: 2
For directed graphs there is boost::strong_components. But two vertices A and B are only in one strong component if there is a path from A to B and vice versa. That is not given in the sample graph from above and we get five strong components for this graph.
Ideally we would have an adapter to create a shallow copy of a directed graph which is undirected. Currently I am not aware of such a feature, so we might go with a copy instead. However copying the whole graph will give some performance issues on large graphs, so we just transform the given graph and reverse the transform after the calculation.
We want each component to behave like a strong component. So whenever we have a path from A to B we need to make sure, that the path from B to A is also available. The simplest solution might be to just add all edges with inverted direction:
boost::add_edge(boost::target(edge, graph), boost::source(edge, graph), graph);
A small encapsulation for transform, the calculation and the reversal of the transform may then look like this:
void strong_components(graph_t &graph) {
std::vector<edge_t> temp_edges;
auto edges = boost::edges(graph);
for (auto it = edges.first; it != edges.second; ++it) {
auto pair = boost::add_edge(boost::target(*it, graph),
boost::source(*it, graph),
graph);
temp_edges.push_back(pair.first);
}
graph[boost::graph_bundle].number_of_components =
boost::strong_components(graph,
boost::get(&node_properties::component, graph));
for (const auto & e : temp_edges) {
boost::remove_edge(e, graph);
}
}
Note:
boost::remove_edgemight invalidate other edge descriptors. In this example we are using an adjacency list for which this ok (see Iterator and Descriptor Stability/Invalidation).- Once the graph is transformed the algorithm
boost::connected_componentsshould give the same results since every route in a connected component is now available. Furthermore it should be faster, since it doesn't need to check for strong connectivity. However, this is not specified by Boost Graph and depends heavily on the implementation. So be very cautious if you replaceboost::strong_componentsand check the implementation in your case.
Complete example
Here is the full example to play:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/strong_components.hpp>
#include <iostream>
#include <vector>
//==============================================================================
struct node_properties {
int component;
};
struct edge_properties {
};
struct graph_properties {
int number_of_components;
};
//--------------------------------------
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
node_properties, edge_properties, graph_properties> graph_t;
typedef typename boost::graph_traits<graph_t>::vertex_descriptor vertex_t;
typedef typename boost::graph_traits<graph_t>::edge_descriptor edge_t;
//==============================================================================
void print_graph(const graph_t &graph) {
std::cout << "Graph:" << std::endl;
auto edges = boost::edges(graph);
for (auto it = edges.first; it != edges.second; ++it) {
std::cout << boost::source(*it, graph) << " -> "
<< boost::target(*it, graph) << std::endl;
}
}
//==============================================================================
void print_components(const graph_t &graph) {
std::cout << "\nComponents: "
<< graph[boost::graph_bundle].number_of_components << std::endl;
auto nodes = boost::vertices(graph);
for (auto it = nodes.first; it != nodes.second; ++it) {
std::cout << "Node: " << *it << " component: " << graph[*it].component
<< std::endl;
}
}
//==============================================================================
void strong_components(graph_t &graph) {
std::vector<edge_t> temp_edges;
auto edges = boost::edges(graph);
for (auto it = edges.first; it != edges.second; ++it) {
auto pair = boost::add_edge(boost::target(*it, graph),
boost::source(*it, graph),
graph);
temp_edges.push_back(pair.first);
}
graph[boost::graph_bundle].number_of_components =
boost::strong_components(graph,
boost::get(&node_properties::component, graph));
for (const auto & e : temp_edges) {
boost::remove_edge(e, graph);
}
}
//==============================================================================
int main() {
graph_t graph;
std::vector<vertex_t> vertices;
vertices.push_back(boost::add_vertex(graph));
vertices.push_back(boost::add_vertex(graph));
vertices.push_back(boost::add_vertex(graph));
vertices.push_back(boost::add_vertex(graph));
vertices.push_back(boost::add_vertex(graph));
boost::add_edge(vertices.at(0), vertices.at(1), graph);
boost::add_edge(vertices.at(0), vertices.at(2), graph);
boost::add_edge(vertices.at(1), vertices.at(2), graph);
boost::add_edge(vertices.at(4), vertices.at(3), graph);
graph[boost::graph_bundle].number_of_components =
boost::connected_components(graph,
boost::get(&node_properties::component, graph));
std::cout << "Without adaption:\n-----------------" << std::endl;
print_graph(graph);
print_components(graph);
strong_components(graph);
std::cout << "\nWith additional edges:\n----------------------" << std::endl;
print_graph(graph);
print_components(graph);
}
Output:
Without adaption:
-----------------
Graph:
0 -> 1
0 -> 2
1 -> 2
4 -> 3
Components: 3
Node: 0 component: 0
Node: 1 component: 0
Node: 2 component: 0
Node: 3 component: 1
Node: 4 component: 2
With additional edges:
----------------------
Graph:
0 -> 1
0 -> 2
1 -> 2
4 -> 3
Components: 2
Node: 0 component: 0
Node: 1 component: 0
Node: 2 component: 0
Node: 3 component: 1
Node: 4 component: 1
Note: You might get maybe unintialized warnings when using gcc to compile this. Those are not a problem of the example but well known.