Boost Graph Lib > A*
Dear all,
First Hello.
Then does anybody knows how the a star search works for implicit graph?
There is little information on the Internet.
I found a pdf:
A* Graph Search Within the BGL Framework
http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
But I wasn't able to run the implicit graph example because I am missing:
#include
On Fri, 11 Dec 2009, Damien Maupu wrote:
Dear all,
First Hello. Then does anybody knows how the a star search works for implicit graph? There is little information on the Internet.
I found a pdf: A* Graph Search Within the BGL Framework http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
But I wasn't able to run the implicit graph example because I am missing: #include
and #include "test-astar-visitors.hpp" #include "test-astar-accept.hpp" In the online doc: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html It is said to use astar_search_no_init but I don't know how.
Any clues?
There is an example of A* search at
URL:http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp
but it uses the version with initialization. Does your graph have an
infinite or unknown number of vertices? If so, use the _no_init version
by swapping the color and index_map arguments and providing your own color
map. You can use
boost::make_constant_property
Jeremiah Willcock a écrit :
On Fri, 11 Dec 2009, Damien Maupu wrote:
Dear all,
First Hello. Then does anybody knows how the a star search works for implicit graph? There is little information on the Internet.
I found a pdf: A* Graph Search Within the BGL Framework http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
But I wasn't able to run the implicit graph example because I am missing: #include
and #include "test-astar-visitors.hpp" #include "test-astar-accept.hpp" In the online doc: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html It is said to use astar_search_no_init but I don't know how.
Any clues?
There is an example of A* search at URL:http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp but it uses the version with initialization. Does your graph have an infinite or unknown number of vertices? If so, use the _no_init version by swapping the color and index_map arguments and providing your own color map. You can use boost::make_constant_property
(boost::white_color) (where vertex_t is your graph's vertex type, with includes of and ) as the property map if you don't mind having the same vertex visited multiple times (for example, for a tree-like graph). If you are having performance problems with multiple visits of the same vertices, you will need to use a boost::associative_property_map (from ) with a less-then-comparable vertex type instead. -- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi, My graph is growing as the search progress so it is an implicit graph and I understand I have to use the _no_init version (because the doc say so). Why can I just the version with the init? Because if I use the no_init version I need to init the properties map somehow. I guess the moment the make the graph grows is while visitor does examine_vertex. I understand how I can add vertex to the graph, but how should I proceed for the properties map? Should I destroy and recreate new one (with the correct size) each time? Anybody have a working example of the a* working on a implicit graph? Thank you Damien
On Mon, 11 Jan 2010, Damien Maupu wrote:
Jeremiah Willcock a écrit :
On Fri, 11 Dec 2009, Damien Maupu wrote:
Dear all,
First Hello. Then does anybody knows how the a star search works for implicit graph? There is little information on the Internet.
I found a pdf: A* Graph Search Within the BGL Framework http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
But I wasn't able to run the implicit graph example because I am missing: #include
and #include "test-astar-visitors.hpp" #include "test-astar-accept.hpp" In the online doc: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html It is said to use astar_search_no_init but I don't know how.
Any clues?
There is an example of A* search at URL:http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp but it uses the version with initialization. Does your graph have an infinite or unknown number of vertices? If so, use the _no_init version by swapping the color and index_map arguments and providing your own color map. You can use boost::make_constant_property
(boost::white_color) (where vertex_t is your graph's vertex type, with includes of and ) as the property map if you don't mind having the same vertex visited multiple times (for example, for a tree-like graph). If you are having performance problems with multiple visits of the same vertices, you will need to use a boost::associative_property_map (from ) with a less-then-comparable vertex type instead. -- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi,
My graph is growing as the search progress so it is an implicit graph and I understand I have to use the _no_init version (because the doc say so). Why can I just the version with the init? Because if I use the no_init version I need to init the properties map somehow.
I guess the moment the make the graph grows is while visitor does examine_vertex. I understand how I can add vertex to the graph, but how should I proceed for the properties map? Should I destroy and recreate new one (with the correct size) each time?
Anybody have a working example of the a* working on a implicit graph?
I do not have an example of implicit A*. What property do you need other than the color? If you only need the color map and are able to accept visiting the same vertex multiple times, just use a fake property map that always returns "white" no matter what vertex is given. There is a constant_property_map for that. -- Jeremiah Willcock
Hi Jeremiah, Thank for your help. I succeed in doing what I wanted. My implicit graph's vertex have as internal properties all features needed by Astar instead of using external property map. I know it make sense but it wasn't for me at the beginning. I am using bundle properties and calling them with the proper mechanism while loading property map. Thank Damien Jeremiah Willcock a écrit :
On Mon, 11 Jan 2010, Damien Maupu wrote:
Jeremiah Willcock a écrit :
On Fri, 11 Dec 2009, Damien Maupu wrote:
Dear all,
First Hello. Then does anybody knows how the a star search works for implicit graph? There is little information on the Internet.
I found a pdf: A* Graph Search Within the BGL Framework http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
But I wasn't able to run the implicit graph example because I am missing: #include
and #include "test-astar-visitors.hpp" #include "test-astar-accept.hpp" In the online doc: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html It is said to use astar_search_no_init but I don't know how.
Any clues?
There is an example of A* search at URL:http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp but it uses the version with initialization. Does your graph have an infinite or unknown number of vertices? If so, use the _no_init version by swapping the color and index_map arguments and providing your own color map. You can use boost::make_constant_property
(boost::white_color) (where vertex_t is your graph's vertex type, with includes of and ) as the property map if you don't mind having the same vertex visited multiple times (for example, for a tree-like graph). If you are having performance problems with multiple visits of the same vertices, you will need to use a boost::associative_property_map (from ) with a less-then-comparable vertex type instead. -- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi,
My graph is growing as the search progress so it is an implicit graph and I understand I have to use the _no_init version (because the doc say so). Why can I just the version with the init? Because if I use the no_init version I need to init the properties map somehow.
I guess the moment the make the graph grows is while visitor does examine_vertex. I understand how I can add vertex to the graph, but how should I proceed for the properties map? Should I destroy and recreate new one (with the correct size) each time?
Anybody have a working example of the a* working on a implicit graph?
I do not have an example of implicit A*. What property do you need other than the color? If you only need the color map and are able to accept visiting the same vertex multiple times, just use a fake property map that always returns "white" no matter what vertex is given. There is a constant_property_map for that.
-- Jeremiah Willcock
participants (2)
-
Damien Maupu -
Jeremiah Willcock