| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Daniele" |
| Date: |
03 Aug 2004 10:11:09 AM |
| Object: |
Print all possible routes in a graph between two nodes |
Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
Thanks
Dax
.
|
|
| User: "Alf P. Steinbach" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 10:27:14 AM |
|
|
* Daniele:
Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
Hi this is off-topic in [comp.lang.c++] as it isn't C++ related.
Hi try [comp.programming], which I have crossposted this to.
Hi follow-up is also set to [comp.programming].
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.
|
|
|
|
| User: "Victor Bazarov" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 10:22:48 AM |
|
|
Daniele wrote:
Hi there is a way to put in a struct of vectors all the possibles
routes in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
It is possible because C++ is a language that allows recursive calls
to functions (except 'main').
Declare a vector in which you will try to build a single path. Define
a function to which you will pass the vector under construction and
your collection of vectors (the complete list of routes), and the set
of nodes to exclude. Proceed to enumerate all nodes from current one
while checking against the exclusion set. If you reach your destination
node, add the currently built path to the list and return. If you see
no way ahead (dead end), don't add the currently built path, but still
return. Shouldn't be that difficult.
To be fair to the newsgroup, your question is only marginally related
to the subject of comp.lang.c++. Perhaps you should make an attempt to
code what you think the right algorithm is, and if you encounter any
_language_ problem, come back and post a particular _language_ question.
Victor
.
|
|
|
| User: "Daniele" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 11:24:10 AM |
|
|
There is a simple example to test it?
Thanks
Daniele
On Tue, 03 Aug 2004 11:22:48 -0400, Victor Bazarov
<v.Abazarov@comAcast.net> wrote:
Daniele wrote:
Hi there is a way to put in a struct of vectors all the possibles
routes in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
It is possible because C++ is a language that allows recursive calls
to functions (except 'main').
Declare a vector in which you will try to build a single path. Define
a function to which you will pass the vector under construction and
your collection of vectors (the complete list of routes), and the set
of nodes to exclude. Proceed to enumerate all nodes from current one
while checking against the exclusion set. If you reach your destination
node, add the currently built path to the list and return. If you see
no way ahead (dead end), don't add the currently built path, but still
return. Shouldn't be that difficult.
To be fair to the newsgroup, your question is only marginally related
to the subject of comp.lang.c++. Perhaps you should make an attempt to
code what you think the right algorithm is, and if you encounter any
_language_ problem, come back and post a particular _language_ question.
Victor
--
Using Opera's revolutionary e-mail client: http://www.opera.com/m2/
.
|
|
|
| User: "Victor Bazarov" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 11:40:44 AM |
|
|
Daniele wrote:
There is a simple example to test it?
To test what?
And don't top-post please.
Thanks
Daniele
On Tue, 03 Aug 2004 11:22:48 -0400, Victor Bazarov
<v.Abazarov@comAcast.net> wrote:
Daniele wrote:
Hi there is a way to put in a struct of vectors all the possibles
routes in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
It is possible because C++ is a language that allows recursive calls
to functions (except 'main').
Declare a vector in which you will try to build a single path. Define
a function to which you will pass the vector under construction and
your collection of vectors (the complete list of routes), and the set
of nodes to exclude. Proceed to enumerate all nodes from current one
while checking against the exclusion set. If you reach your destination
node, add the currently built path to the list and return. If you see
no way ahead (dead end), don't add the currently built path, but still
return. Shouldn't be that difficult.
To be fair to the newsgroup, your question is only marginally related
to the subject of comp.lang.c++. Perhaps you should make an attempt to
code what you think the right algorithm is, and if you encounter any
_language_ problem, come back and post a particular _language_ question.
Victor
--
Please remove capital As from my address when replying by mail
.
|
|
|
| User: "Daniele" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 12:17:04 PM |
|
|
There is a simple example to test it?
To test what?
Do you have a sample in c++ of this algorithm to discover all the paths
from two nodes?
And don't top-post please.
Sorry But I was in late...
But Now I respect the netiquette
Thanks
Daniele
.
|
|
|
| User: "Victor Bazarov" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 01:28:27 PM |
|
|
Daniele wrote:
There is a simple example to test it?
To test what?
Do you have a sample in c++ of this algorithm to discover all the paths
from two nodes?
Nope. And I think I've described the algorithm well enough for
anybody who's interested to implement it. Not the best of them,
I am certain, but can be made working (like the bubble sort for
sorting). Besides, I am sure that after a few minutes you could
find an implementation of something like it on the Web. Try to
use Google or any other search engine.
BTW, this newsgroup doesn't usually do anybody's homework. Not
that I can say for sure that it's your homework, but just FYI.
V
.
|
|
|
|
|
|
|
|
| User: "tom_usenet" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 12:17:32 PM |
|
|
On Tue, 03 Aug 2004 17:11:09 +0200, Daniele
<se_lachiedi@te_la_dico.it> wrote:
Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.
Use boost's powerful graph library:
http://www.boost.org/libs/graph/doc/table_of_contents.html
I don't think Dijkstra will do it, and you'll have to decide on your
definition of a "possible route" (i.e. a vertex can be visited only
once in each route, etc.). Working out the actual algorithm is a
question for a maths group.
Tom
.
|
|
|
| User: "Daniele" |
|
| Title: Re: Print all possible routes in a graph between two nodes |
03 Aug 2004 12:38:50 PM |
|
|
Yes I've seen... and now I try to use it...
Dax
.
|
|
|
|
|
|
Related Articles |
|
|
