Searching Path

1. giahan Guest

Searching Path

Hi all,<BR><BR>I havve a table like this<BR>Start(End) End(Start)<BR>A B<BR>A C<BR>B C<BR>C D<BR>A D<BR>E D<BR>A E<BR>C F<BR>in my SQL db<BR>I have to implement and find all that possible path from Start to End. For instance, if user enters A as "Start" and B as "End", I have to display all paths like:<BR>AB<BR>ACB<BR>ADCB<BR>AEDCB<BR><BR>Any help or hint would be really appreciated.<BR>

2. Nathan Wenneker Guest

RE: Searching Path

I would create a recursive function to do this.<BR><BR>The plan would be to break all routes from point A to point B<BR>into a series of smaller point to point jumps. Each time you call<BR>the function you&#039;d pass its route so far as an argument to the function.<BR><BR>For example...If ABC is a route -- first the function would find<BR>AB, then it would be called again to find BC (with A as an argument). Once it found that it reached C, it would append BC to the passed route (A) and save it as a complete route. Same idea for ABCD -- first find AB, then find BC (with A passed), then find CD (with AB) passed, and since D was reached, append CD to AB and save it as a complete route.<BR><BR>Assuming A is your start point and B is your end point, you&#039;d call the recursive function the first time with three arguments -<BR>A, B, and blank<BR><BR>The recursive function would then do this:<BR><BR>(1) Bring back all records that start at argument one and end anywhere.<BR><BR>(2) Check to see if the anywhere is the second argument. -- if it is, then this is a complete path - store it somewhere (remember to append to whatever is stored in the third argument)<BR><BR>(3) From within the function, call itself again for each of the unique second points that it found in step (1) with the first argument being the second point and the second argument being the original destination point, and the third argument being the completed route so far (equivalent to appending the current first argument to the current third argument). This would start steps 1 and 2 over again. To check if a point is unique, check to see if it exists in the third argument....this is to prevent a route from A to B such as ACACACACACACACACACB.<BR><BR>There is one downfall to this approach -- and that is processing time. Let&#039;s say you want to find A to D and that ABCD is a route<BR>and that ACD is a route. With the above approach, the program would have to figure out twice that C goes to D -- once for each route. Certainly you could come up with some code to recognize when you got to ABC that AC was already being processed and just wait for AC to finish so you could use the same end routes for both ABC and AC without figuring out the same end routes twice.<BR><BR><BR>Nathan

3. giahan Guest

RE: Searching Path

Processing is my prob. This is a huge db. I try just ACB. It took like 30 sec. The problem here is that when I run a SELECT statement, I have a column, not a row (means I have a set - called &#039;Set1&#039; - of all end point where start point is A) From that list, again I have to search for every single end point where start point is in Set1, for each item i&#039;ll have a nother set,... and keep going, my server crashes ):. I&#039;m looking for a way that make it works ):.

4. Senior Member
Join Date
Dec 1969
Posts
1,912

RE: Searching Path

First of all... Good question!<BR><BR>This won&#039;t reduce the number of permutations that you have to check, but it could speed up the process.<BR><BR>How about before you start the recursive process you hit the DB once to get all the end points for each distinct start point. Then you have an array for each start point and can do your recursion w/ arrays instead of hitting the DB each time.<BR><BR>I guess it depends on your data. If there are too many (?) sets that don&#039;t come into the final path there would be some point where it would be inefficient to collect that info.<BR><BR>I&#039;d post this question on www.sqlTeam.com I bet they could come up with something slick!

5. Nathan Wenneker Guest

RE: Searching Path

How huge is huge?<BR><BR>Perhaps I misunderstood how your data is stored in the table, but regardless of how it is stored, you still have to move through all possible routes until you exhaust all of them. The easiest/fastest way to do this is through the recursive function I described. To increase performance you can write some code that will recognize when a partial route has reached a point from which the rest of the routes branching from it will match the routes branching from another partial route and then consolidate the determination of the rest of the route instead of doing it multiple times. <BR><BR>For example...<BR><BR>If you have to get from A to Z and there are two good routes:<BR><BR>ATUVWXYZ<BR>ABCDEFGHTUVWXYZ<BR><BR> While processing the second route, once you get the partial route ABCDEFGHT -- the code must recognize that it has already determined that T can get to Z and how - that way it doesn&#039;t have to redetermine the TUVWXYZ. This will increase performance greatly.

6. giahan Guest

RE: Searching Path

Thanks for the help. I cannot do that b/c of path continuous - First, I have to search all of the end points that come from the given start point, then I have to pass the path if there is any end point that match the &#039;given end point&#039;, then I search the db again to find all the end points that start from the previous end point set. Umm.. you mean store Start and End values as a 2D-array? It&#039;s a good idear but still I got &#062;30,000 records though. My server will crash ):. Any other idea? I have been thinking like 3 days already ):. I am thinking of JavaServlet as a solution but still debating (:

7. giahan Guest

RE: Searching Path

It&#039;s &#062;30,000 recs. I just need to find the max mid points is 6 (ie from A to Z, the longest path is ACDFGHKZ).

8. giahan Guest

got it

I got it works. Thanks

9. giahan Guest

Got it

I got it works. Thanks.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•