[Boost-users] [graph] Sorted vertices in graph

Subject: [Boost-users] [graph] Sorted vertices in graph
From: Tryptik (tryptik_2002_at_[hidden])
Date: 2008-10-19 18:05:08

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,
            <custom_container or multisetS>
            bidirectionalS,
            Node_t> // struct that has the vertex data
            Graph;

size_t find(const Graph& g, const T& t, std::vector<vertex_descriptor>& result)
{
  std::pair<vertex_iterator, vertex_iterator> 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<vertex_descriptor> 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