howto store vertex-iterators as internal graph property?
Hi folks! I got a cyclic type-dependency problem. I am trying to let every vertex store a iterator to a list which stores vertex-iterators. This sounds weired, but I need to keep track of very few vertices within my graph which have a particle located at it. Thus I created a list of vertex-iterators who carry my particle positions in the graph. In order to be able to tell quickly if a vertice is taken by a particle I want each vertice to include a pointer to a null element representing the absence of a particle or a pointer into that list. My non-working code looks like: Definition of my graph: struct Spot { // acutally I need the vertex_iterator to be defined already // in order to define particle, but this is not yet defined // so I am using the knowledge that it is going to be represented // by a vector<std::size_t>::iterator (at least I hope so) // this assumption is WRONG!! typedef std::list< std::vector<std::size_t>::iterator >::iterator \\ particle_t; particle_t particle; }; typedef boost::adjacency_list<boost::vecS, boost::vecS, \\ boost::undirectedS, Spot > graph_t; Here I initialise my particles to be distributed in the graph object bg. m_posA is of type: std::list<RandomGraph::gtraits::vertex_iterator> // first initialise every position to the null-flag for(; vi != vend; ++vi) bg[*vi].particle = Spot::particle_t(); // now place particles at random positions boost::tie(vi, vend) = boost::vertices(bg); for(std::size_t i = 0; i < initialA; i++) { std::size_t pos; //aList_t::iterator iter; // find a random empty vertice do { pos = rand_gen(); } while(bg[pos].particle != m_posA_end); // place particle A there RandomGraph::gtraits::vertex_iterator vref = vi + pos; // put returns an iterator to the list-element where // vref has been stored bg[pos].particle = m_posA.put(vref); } Any help would be great. Thanks in adavance. Greetings, Sebastian Weber
Hi Sebastian,
Hi folks!
I got a cyclic type-dependency problem. I am trying to let every vertex store a iterator to a list which stores vertex-iterators. This sounds weired, but I need to keep track of very few vertices within my graph which have a particle located at it. Thus I created a list of vertex-iterators who carry my particle positions in the graph. In order to be able to tell quickly if a vertice is taken by a particle I want each vertice to include a pointer to a null element representing the absence of a particle or a pointer into that list. My non-working code looks like:
Definition of my graph:
struct Spot { // acutally I need the vertex_iterator to be defined already // in order to define particle, but this is not yet defined // so I am using the knowledge that it is going to be represented // by a vector<std::size_t>::iterator (at least I hope so) // this assumption is WRONG!! typedef std::list< std::vector<std::size_t>::iterator >::iterator \\
There are two approaches. 1. Use pimpl or incomplete type to postpone defining the property type until you know the iterator type. struct Spot; typedef boost::adjacency_list<boost::vecS, boost::vecS, \\ boost::undirectedS, Spot* > graph_t; struct Spot { ............. } ; 2. Don't bother with iterators, store vector<unsigned> inside the Spot class. For VecS/VecS graph, using unsigned to identify vertices should be OK. BTW, I'm not sure why your code does not work. It should work, maybe after changing size_t to int -- don't remember if vertex_descrption is signed or not. - Volodya
On Nov 29, 2004, at 7:14 AM, Vladimir Prus wrote:
Hi Sebastian,
2. Don't bother with iterators, store vector<unsigned> inside the Spot class. For VecS/VecS graph, using unsigned to identify vertices should be OK.
Better yet... use adjacency_list_traits to get the vertex_descriptor type instead of guessing at "unsigned". adjacency_list_traits is documented along with the adjacency_list class here, under the "Associated types" section: http://www.boost.org/libs/graph/doc/adjacency_list.html Basically, it depends on the vertex list type, out edge list type, and directedness, but not the properties, so it is ideal for what Vladimir is proposing. Doug
Hi Sebastian, Why do you want to store vertex iterators instead of just vertex descriptors? You can use adjacency_list_traits to get the vertex_descriptor type prior to creating the graph type. Cheers, Jeremy On Nov 29, 2004, at 7:14 AM, Vladimir Prus wrote:
Hi Sebastian,
Hi folks!
I got a cyclic type-dependency problem. I am trying to let every vertex store a iterator to a list which stores vertex-iterators. This sounds weired, but I need to keep track of very few vertices within my graph which have a particle located at it. Thus I created a list of vertex-iterators who carry my particle positions in the graph. In order to be able to tell quickly if a vertice is taken by a particle I want each vertice to include a pointer to a null element representing the absence of a particle or a pointer into that list. My non-working code looks like:
Definition of my graph:
struct Spot { // acutally I need the vertex_iterator to be defined already // in order to define particle, but this is not yet defined // so I am using the knowledge that it is going to be represented // by a vector<std::size_t>::iterator (at least I hope so) // this assumption is WRONG!! typedef std::list< std::vector<std::size_t>::iterator >::iterator \\
There are two approaches.
1. Use pimpl or incomplete type to postpone defining the property type until you know the iterator type.
struct Spot; typedef boost::adjacency_list<boost::vecS, boost::vecS, \\ boost::undirectedS, Spot* > graph_t;
struct Spot { ............. } ;
2. Don't bother with iterators, store vector<unsigned> inside the Spot class. For VecS/VecS graph, using unsigned to identify vertices should be OK.
BTW, I'm not sure why your code does not work. It should work, maybe after changing size_t to int -- don't remember if vertex_descrption is signed or not.
- Volodya
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________
Hi Jeremy!
Why do you want to store vertex iterators instead of just vertex descriptors?
Maybe this is what I want to store :-) I want to store something which points to a vertex which allows me the fastest possible access to the vertex with all it's internal properties connected to it. If a reference to a vertex descriptor does that, this is what I want. I guess I gotta read a little more the docs
You can use adjacency_list_traits to get the vertex_descriptor type prior to creating the graph type.
Doug already pointed that out. Once again I gotta read a little more documentation ... Thanks although! Greetings, Sebastian
Cheers, Jeremy
On Nov 29, 2004, at 7:14 AM, Vladimir Prus wrote:
Hi Sebastian,
Hi folks!
I got a cyclic type-dependency problem. I am trying to let every vertex store a iterator to a list which stores vertex-iterators. This sounds weired, but I need to keep track of very few vertices within my graph which have a particle located at it. Thus I created a list of vertex-iterators who carry my particle positions in the graph. In order to be able to tell quickly if a vertice is taken by a particle I want each vertice to include a pointer to a null element representing the absence of a particle or a pointer into that list. My non-working code looks like:
Definition of my graph:
struct Spot { // acutally I need the vertex_iterator to be defined already // in order to define particle, but this is not yet defined // so I am using the knowledge that it is going to be represented // by a vector<std::size_t>::iterator (at least I hope so) // this assumption is WRONG!! typedef std::list< std::vector<std::size_t>::iterator >::iterator \\
There are two approaches.
1. Use pimpl or incomplete type to postpone defining the property type until you know the iterator type.
struct Spot; typedef boost::adjacency_list<boost::vecS, boost::vecS, \\ boost::undirectedS, Spot* > graph_t;
struct Spot { ............. } ;
2. Don't bother with iterators, store vector<unsigned> inside the Spot class. For VecS/VecS graph, using unsigned to identify vertices should be OK.
BTW, I'm not sure why your code does not work. It should work, maybe after changing size_t to int -- don't remember if vertex_descrption is signed or not.
- Volodya
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Be aware that the vertex which a vertex descriptor references to can change as vertices are removed from the graph. Its just a vector index after all... Sebastian Weber wrote:
Hi Jeremy!
Why do you want to store vertex iterators instead of just vertex descriptors?
Maybe this is what I want to store :-)
I want to store something which points to a vertex which allows me the fastest possible access to the vertex with all it's internal properties connected to it. If a reference to a vertex descriptor does that, this is what I want. I guess I gotta read a little more the docs
You can use adjacency_list_traits to get the vertex_descriptor type prior to creating the graph type.
Doug already pointed that out. Once again I gotta read a little more documentation ...
Thanks although!
Greetings,
Sebastian
Cheers, Jeremy
On Nov 29, 2004, at 7:14 AM, Vladimir Prus wrote:
Hi Sebastian,
Hi folks!
I got a cyclic type-dependency problem. I am trying to let every vertex store a iterator to a list which stores vertex-iterators. This sounds weired, but I need to keep track of very few vertices within my graph which have a particle located at it. Thus I created a list of vertex-iterators who carry my particle positions in the graph. In order to be able to tell quickly if a vertice is taken by a particle I want each vertice to include a pointer to a null element representing the absence of a particle or a pointer into that list. My non-working code looks like:
Definition of my graph:
struct Spot { // acutally I need the vertex_iterator to be defined already // in order to define particle, but this is not yet defined // so I am using the knowledge that it is going to be represented // by a vector<std::size_t>::iterator (at least I hope so) // this assumption is WRONG!! typedef std::list< std::vector<std::size_t>::iterator >::iterator \\
There are two approaches.
1. Use pimpl or incomplete type to postpone defining the property type until you know the iterator type.
struct Spot; typedef boost::adjacency_list<boost::vecS, boost::vecS, \\ boost::undirectedS, Spot* > graph_t;
struct Spot { ............. } ;
2. Don't bother with iterators, store vector<unsigned> inside the Spot class. For VecS/VecS graph, using unsigned to identify vertices should be OK.
BTW, I'm not sure why your code does not work. It should work, maybe after changing size_t to int -- don't remember if vertex_descrption is signed or not.
- Volodya
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeffrey Holle wrote:
Be aware that the vertex which a vertex descriptor references to can change as vertices are removed from the graph. Its just a vector index after all...
...unless you're using something other than vecS as the vertex list type, in which case the vertex descriptor will be a pointer and won't change. Cheers, Meredith L. Patterson (learned this the hard way :)
participants (6)
-
Doug Gregor -
Jeffrey Holle -
Jeremy Siek -
Meredith L. Patterson -
Sebastian Weber -
Vladimir Prus