
Multiple query
I have a table like this:<BR>Start(End) End(Start)<BR>A B<BR>B C<BR>A C<BR>D C<BR>D B<BR>E D<BR>A F <BR><BR>My responsibitity is to display all posible paths from A to B<BR>AB<BR>ACB<BR>ACDB<BR>ACDEB<BR>Any help would be really appreciated<BR><BR><BR>

Won't do it with a DB query...
This kind of problem is *not* what SQL queries were designed for. You *might* be able to get it to work, but it would be a brute force approach where you'd first search for paths of length 1, then a separate search for paths of length 2, then length 3, etc. And how will you know how many queries to do? In theory, a path might involve every pair in your table, so you'd have to make as many queries are there are records in the table, yes? SHUDDER! The performance would be incredibly bad.<BR><BR>This is surely better done with a simple inmemory recursive descent probe into the data, with the data represented as a simple 2D array.<BR><BR>

RE: Won't do it with a DB query...
Thanks for your prompt response. Yeah, the table is huge with thousands records. I know, I have tried it with 1length path, and it took like 1 min. It's not good ):. Can you be more specific on "simple inmemory recursive descent probe into the data, with the data represented as a simple 2D array." I appreciate<BR>

RE: Won't do it with a DB query...
Okay...a "hack" at it...<BR><BR>The big problem I see is that you might have data such as this:<BR><BR>A  B<BR>B  C<BR>C  B<BR>C  D<BR><BR>And so one path from A to D is simply ABCD, but another path is ABCBCBCBCD, etc., etc. Naturally, the "loop" could actually be many, many subpaths long rather than only two steps as in this dirt simple example.<BR><BR>So what's the goal, here? Are you given both the starting point and the ending point and you must determine all (nonlooping???) paths from one to the other? <BR><BR>Or are you supposed to find all paths from every possible starting point to every possible ending point? If you have thousands of subpaths, that could easily take hours and hours to find all solutions. No matter what methodology you employ.<BR><BR>But if you give me the start and end points, I think it's not overwhelmingly difficult.<BR><BR>I'd just build a function that, given a starting point, scans the entire array looking for subpaths that start with the point. For each subpath, the function first checks to see if the endpoint is the desired one. If so, it outputs the path to that point. If not, then it calls itself (passing the path so far) using the new endpoint as the starting point for the next level (but retaining the same target endpoint, of course). If no matching start point is found, the function is done. Regardless of success or failure, at each level the function continues scanning the array from the point it left off at.<BR><BR>To avoid loops, you'd have to "look back" in the path traversed so far. If you find the same node has already been visited, you call this an infinite loop and exit as not found.<BR><BR>But oh, man, with thousands of elements in the array...and any loops at all...well, I sure wouldn't want to run this as an ASP page. I can almost guarantee that it would time out.<BR><BR><BR>

Something like this...
<HTML><BODY><BR><BR><%<BR>pa ths = Array( _<BR> Array( 1, 2 ), _<BR> Array( 1, 3 ), _<BR> Array( 1, 4 ), _<BR> Array( 2, 1 ), _<BR> Array( 2, 3 ), _<BR> Array( 2, 5 ), _<BR> Array( 3, 4 ), _<BR> Array( 4, 5 ), _<BR> Array( 4, 1 ), _<BR> Array( 5, 2 ) _<BR> )<BR><BR>Sub FindPath( byVal soFar, byVal nstart, byVal nstop )<BR> Dim ix<BR> soFar = soFar & "" & nstart & ""<BR> For ix = 0 To UBound( paths )<BR> &nb sp;path = paths(ix)<BR> & nbsp; If path(0) = nstart Then<BR> If path(1) = nstop Then<BR> &n bsp;Response.Write "FOUND: " & soFar & "" & nstop & "<BR>" & vbNewLine<BR> & nbsp; Else<BR> & nbsp; &nb sp; If InStr( soFar, "" & path(1) & "" ) = 0 Then<BR> &n bsp; Call FindPath( soFar, path(1), nstop )<BR> &nb sp;   ;End If<BR> &n bsp; End If<BR> &n bsp;End If<BR> Next<BR>End Sub<BR>%><BR><HR><BR>FindPath( "", 1, 2 ) gives: <br><BR><% FindPath "", 1, 2 %><BR><BR><HR><BR>FindPath( "", 1, 5 ) gives: <br><BR><% FindPath "", 1, 5 %><BR><BR><HR><BR>FindPath( "", 2, 1 ) gives: <br><BR><% FindPath "", 2, 1 %><BR><BR></BODY></HTML><BR><BR>(See, I said it was simple. But it isn't necessarily fast.)<BR><BR><BR>

RE: Won't do it with a DB query...
Thanks a lot. You're genius!
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

