Boost graphic library has a function vertex_descriptor vertex(vertices_size_type n, const adjacency_list& g), which returns the nth vertex_descriptor. What is the inverse of this function? That is, to obtain the order number of a given vertex_descriptor?
Asked
Active
Viewed 147 times
2
xuhdev
- 8,018
- 2
- 41
- 69
-
1**[Vertex Order](http://mathworld.wolfram.com/VertexOrder.html)** means something else in graph theory: _"The number of graph edges meeting at a given node in a graph is called the order of that graph vertex."_ – sehe Jan 29 '15 at 10:28
-
You'd better call this _index_ or somesuch. "Order" is already used to mean something else, and "order number" has never been a clear way to discuss something's index within a collection. – Lightness Races in Orbit Jan 29 '15 at 10:30
-
@Lightness Races in Orbit Thanks. I called it this name because there is a `vertex_index_t` internal property in this library. – xuhdev Jan 29 '15 at 10:50
1 Answers
1
There isn't an efficient way, generically, because it depends on how the vertices are stored.
If you don't care for performance you could create a function like this:
template <typename Graph>
size_t index_of(Graph const& g, typename Graph::vertex_descriptor const& vd)
{
auto vs = vertices(g);
auto lookup = std::find(vs.first, vs.second, vd);
assert(lookup != vs.second);
return std::distance(vs.first, lookup);
}
In the "comprehensive" test below it is shown to work for a plethora of different configurations of adjacency_list<> graph types.
The performance of the above should be reasonable with vecS storage, but it could be abysmal if otherwise. In such cases, it would be far better to supply your own vertex_index mapping, as many other algorithms do require (e.g. write_graphviz):
Test Program
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/random.hpp>
using namespace boost;
template <typename Graph>
size_t index_of(Graph const& g, typename Graph::vertex_descriptor const& vd)
{
auto vs = vertices(g);
auto lookup = std::find(vs.first, vs.second, vd);
assert(lookup != vs.second);
return std::distance(vs.first, lookup);
}
static mt19937 rnd(time(0));
template <typename Graph, size_t num_vertices = 200, size_t num_edges = 300>
void test_index_of()
{
Graph g;
generate_random_graph(g, 100, 300, rnd);
for(auto const& v : make_iterator_range(vertices(g))) {
assert(v == boost::vertex(index_of(g, v), g));
}
}
int main()
{
test_index_of<adjacency_list<vecS, vecS, undirectedS> >();
test_index_of<adjacency_list<vecS, setS, undirectedS> >();
test_index_of<adjacency_list<vecS, listS, undirectedS> >();
test_index_of<adjacency_list<setS, vecS, undirectedS> >();
test_index_of<adjacency_list<setS, setS, undirectedS> >();
test_index_of<adjacency_list<setS, listS, undirectedS> >();
test_index_of<adjacency_list<listS, vecS, undirectedS> >();
test_index_of<adjacency_list<listS, setS, undirectedS> >();
test_index_of<adjacency_list<listS, listS, undirectedS> >();
test_index_of<adjacency_list<vecS, vecS, directedS> >();
test_index_of<adjacency_list<vecS, setS, directedS> >();
test_index_of<adjacency_list<vecS, listS, directedS> >();
test_index_of<adjacency_list<setS, vecS, directedS> >();
test_index_of<adjacency_list<setS, setS, directedS> >();
test_index_of<adjacency_list<setS, listS, directedS> >();
test_index_of<adjacency_list<listS, vecS, directedS> >();
test_index_of<adjacency_list<listS, setS, directedS> >();
test_index_of<adjacency_list<listS, listS, directedS> >();
}
