The example in boost is from the doc
https://www.boost.org/doc/libs/1_85_0/libs/graph/example/connected_components.cpp
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
/*
This example demonstrates the usage of the connected_components
algorithm on a undirected graph. The example graphs come from
"Introduction to Algorithms", Cormen, Leiserson, and Rivest p. 87
(though we number the vertices from zero instead of one).
Sample output:
Total number of components: 3
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 1
Vertex 3 is in component 2
Vertex 4 is in component 0
Vertex 5 is in component 1
*/
using namespace std;
int main(int , char* [])
{
using namespace boost;
{
typedef adjacency_list <vecS, vecS, undirectedS> Graph;
Graph G;
add_edge(0, 1, G);
add_edge(1, 4, G);
add_edge(4, 0, G);
add_edge(2, 5, G);
std::vector<int> component(num_vertices(G));
int num = connected_components(G, &component[0]);
std::vector<int>::size_type i;
cout << "Total number of components: " << num << endl;
for (i = 0; i != component.size(); ++i)
cout << "Vertex " << i <<" is in component " << component[i] << endl;
cout << endl;
}
return 0;
}
This works fine.
https://godbolt.org/z/3jYaEM9Ks
However there is a catch. What about a vertex this is not connected by edges to any other vertex. It should end in a component by itself. However I'm not sure how to change the code to achieve this?
I've tried adding
add_vertex(6, G);
but that intuition does not work.
However there is a catch. What about a vertex this is not connected by edges to any other vertex. It should end in a component by itself.
In your example, vertex #3 is such a vertex. It is already in its own component. SUCCESS!
I've tried adding
add_vertex(6, G);but that intuition does not work.
I have no idea what that should accomplish. You're calling add_vertex with an argument 6 to initialize the vertex properties with. But you have no vertex properties ¯\(ツ)/¯.
If you want to add a vertex, just say auto descriptor = add_vertex(G);. But as you've seen above there is no need because vertex 3 was ALREADY unconnected.
If you meant to make sure that 7 vertices exist (0,1,2,3,4,5,6), just make it so: Live On Coliru
Graph g(7);
Now it prints, as you expected:
Total number of components: 4
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 1
Vertex 3 is in component 2
Vertex 4 is in component 0
Vertex 5 is in component 1
Vertex 6 is in component 3
If you really are just confused about implicit vertex indices in vecS storage, compare to listS storage:
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <iostream>
#include <vector>
int main(int, char*[]) {
using Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS>;
using VDesc = Graph::vertex_descriptor;
Graph g;
std::array<VDesc, 7> vv;
for (auto& v : vv)
v = add_vertex(g);
add_edge(vv[0], vv[1], g);
add_edge(vv[1], vv[4], g);
add_edge(vv[4], vv[0], g);
add_edge(vv[2], vv[5], g);
std::map<VDesc, int> component;
std::map<VDesc, size_t> index;
auto compmap = boost::make_assoc_property_map(component);
auto idmap = boost::make_assoc_property_map(index);
for (auto v : boost::make_iterator_range(vertices(g)))
index.emplace(v, index.size());
int num = connected_components( //
g, //
compmap,
boost::vertex_index_map(idmap));
std::cout << "Total number of components: " << num << std::endl;
// Iterate vertices
for (auto v : boost::make_iterator_range(vertices(g)))
std::cout << "Vertex " << v << " (id " << idmap[v] << ") is in component " << compmap[v] << std::endl;
// Iterate map
std::cout << "Total number mappings: " << component.size() << std::endl;
for (auto const& [v, comp] : component)
std::cout << "Vertex " << v << " (id " << idmap[v] << ") is in component " << comp << std::endl;
std::cout << std::endl;
}
Printing e.g.
Total number of components: 4
Vertex 0x504000000050 (id 0) is in component 0
Vertex 0x504000000090 (id 1) is in component 0
Vertex 0x5040000000d0 (id 2) is in component 1
Vertex 0x504000000110 (id 3) is in component 2
Vertex 0x504000000150 (id 4) is in component 0
Vertex 0x504000000190 (id 5) is in component 1
Vertex 0x5040000001d0 (id 6) is in component 3
Total number mappings: 7
Vertex 0x504000000050 (id 0) is in component 0
Vertex 0x504000000090 (id 1) is in component 0
Vertex 0x5040000000d0 (id 2) is in component 1
Vertex 0x504000000110 (id 3) is in component 2
Vertex 0x504000000150 (id 4) is in component 0
Vertex 0x504000000190 (id 5) is in component 1
Vertex 0x5040000001d0 (id 6) is in component 3