BGL: return all available paths between two vertices
Hello everyone. This is a Boost Graph library question. Is there an algorithm in the library that can return all available paths between two vertices? If not, which algorithm from the library is best to use as a bases, to define a custom visitor for it? (assuming that is the preferred approach) regards, Ioannis
Connected components would work. -----Original Message----- From: Ioannis Nousias [mailto:s0238762@sms.ed.ac.uk] Sent: Wednesday, January 30, 2008 8:09 AM To: boost-users@lists.boost.org Subject: [Boost-users] BGL: return all available paths between two vertices Hello everyone. This is a Boost Graph library question. Is there an algorithm in the library that can return all available paths between two vertices? If not, which algorithm from the library is best to use as a bases, to define a custom visitor for it? (assuming that is the preferred approach) regards, Ioannis
I have a subquestion... Is there an algorithm that will return all shortest paths between two vertices? (I.e. like Djikstra's algorithm but returning all, not just one, shortest path should such a condition exist). Regards. On 30 Jan 2008, at 16:08, Ioannis Nousias wrote:
Hello everyone.
This is a Boost Graph library question. Is there an algorithm in the library that can return all available paths between two vertices? If not, which algorithm from the library is best to use as a bases, to define a custom visitor for it? (assuming that is the preferred approach)
regards, Ioannis
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Jan 30, 2008 11:25 AM, James Jackson <james.jackson@cern.ch> wrote:
I have a subquestion... Is there an algorithm that will return all shortest paths between two vertices? (I.e. like Djikstra's algorithm but returning all, not just one, shortest path should such a condition exist).
Hi James, See this message from the boost users list a few years ago: http://lists.boost.org/boost-users/2005/09/13987.php Regards, Aaron
OK, thanks. I have implemented (although not with the BGL for simplicity) a modified Dijkstra's algorithm which returns all shortest paths (a rather simpler problem that that of the K shortest paths, as suggested in the link). I will try and find time to port this as a BLG algorithm and make it available. Regards, James. On 31 Jan 2008, at 12:36, Aaron Windsor wrote:
On Jan 30, 2008 11:25 AM, James Jackson <james.jackson@cern.ch> wrote:
I have a subquestion... Is there an algorithm that will return all shortest paths between two vertices? (I.e. like Djikstra's algorithm but returning all, not just one, shortest path should such a condition exist).
Hi James,
See this message from the boost users list a few years ago:
http://lists.boost.org/boost-users/2005/09/13987.php
Regards, Aaron _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Thanks James. That would be nice cheers, Ioannis James Jackson wrote:
OK, thanks. I have implemented (although not with the BGL for simplicity) a modified Dijkstra's algorithm which returns all shortest paths (a rather simpler problem that that of the K shortest paths, as suggested in the link). I will try and find time to port this as a BLG algorithm and make it available.
Regards, James.
On 31 Jan 2008, at 12:36, Aaron Windsor wrote:
On Jan 30, 2008 11:25 AM, James Jackson <james.jackson@cern.ch> wrote:
I have a subquestion... Is there an algorithm that will return all shortest paths between two vertices? (I.e. like Djikstra's algorithm but returning all, not just one, shortest path should such a condition exist).
Hi James,
See this message from the boost users list a few years ago:
http://lists.boost.org/boost-users/2005/09/13987.php
Regards, Aaron _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
Aaron Windsor -
Ferng, Andrew D -
Ioannis Nousias -
James Jackson