I am attempting to create a DAG with boost graph where the vertices are sorted. This would allow fast lookup by key - as in the following pseudo code:
adjacency_list<
setS,
bidirectionalS,
Node_t> // struct that has the vertex data
Graph;
size_t find(const Graph& g, const T& t, std::vector& result)
{
std::pair p = vertices(g); //The vertices are sorted
vertex_iterator it = std::lower_bound(p.first, p.second, t);
vertex_iterator end = std::upper_bound(p.first, p.second, t);
std::vector tmp(it, end);
result.swap(tmp);
return result.size();
}
My attempts to sort the actual vertices has been futile. I have tried using a mulitset as well as my own custom sorted container. I would like to avoid calling a seperate sort operation everytime a vertex is added, as this is a mutable graph - I was thinking I could insert the vertex into the sorted storage.
Is there any way to make this work?
Thanks
-J
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
