Page 1 of 2 12 LastLast
Results 1 to 15 of 21
  1. #1
    Join Date
    Jun 2007
    Posts
    6

    Unanswered: Find range by hops

    I am trying to figure out what the most effecient way of calculating hops is.

    Here's the idea. There are locations that are linked,
    Site 1 connects to site 2, 3, and 6
    Site 2 connects to site 1, 3, and 4
    Site 3 connects to site 1, and 2
    Site 4 connects to site 2, and 5
    Site 5 connects to site 4, and 7
    Site 6 connects to site 1, 7, and 8
    Etc...

    This type of connection goes on for a few hundred sites. I want to make a query in Access that will list all locations 2 hops from site 1. So, the query would need to return sites 2,3, and 6 (all one hop) and sites 4, 7, and 8 (two hops).

    I have a table with all the locations as primary keys and that is linked in a one-to-many relationship with a table that has all the links. So now I just need some help figuring out how to get the query that will go multiple hops in.

    Any help would be greatly appreciated!

  2. #2
    Join Date
    May 2005
    Location
    Nevada, USA
    Posts
    2,888
    Provided Answers: 6
    I think what you're looking for is "recursive", if you want to search on that. Not sure if it can be done in a query alone, but it can certainly be done with some VBA. I've never needed it, but I did dream up a function for someone a while back.
    Paul

  3. #3
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Ok - I'm not great on my hierarchies and recursion but....
    if we are talking about a one-to-many relationship between two tables and we only ever need two (or less) "hops" then we don't need recursion right? Recursion is required if we need to go for n or all hops... (this isn't a rhetorical question - just seeing what you think Paul).

    I'm thinking a left outer join from site to hop_sites then a further left outer to site and again left outer to hop_sites. All in SQL.
    Testimonial:
    pootle flump
    ur codings are working excelent.

  4. #4
    Join Date
    May 2005
    Location
    Nevada, USA
    Posts
    2,888
    Provided Answers: 6
    You could well be right. I'm not strong in that area either, and I would need the tables in front of me to play with (poor visualization skills). In my head was the memory of the example I put together for someone, and it was the classic manager/employee situation with an unknown number of levels. I recall being rather proud of that code though.
    Paul

  5. #5
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Quote Originally Posted by pbaldy
    In my head was the memory of the example I put together for someone, and it was the classic manager/employee situation with an unknown number of levels. I recall being rather proud of that code though.
    Lol -so you should be. Recursion is a pain in Access.
    EDIT - fancy popping it in the code bank? We don't have any recursion code in there (although I have been a bit lax checking up on the recent additions... )

    dkelcher - if the suggestions are not enough for you please let us know and we can try to put something more concrete together. If they are sufficient please post your code for others to learn
    Testimonial:
    pootle flump
    ur codings are working excelent.

  6. #6
    Join Date
    May 2005
    Location
    Nevada, USA
    Posts
    2,888
    Provided Answers: 6
    Quote Originally Posted by pootle flump
    fancy popping it in the code bank? We don't have any recursion code in there (although I have been a bit lax checking up on the recent additions... )
    If I can find it. It's not on this PC, but I just got it recently. It's probably still on my old one, which is sitting around here somewhere.
    Paul

  7. #7
    Join Date
    Jun 2007
    Posts
    6
    Since the database I am working with is huge I just threw some random data together.

    As you can see from the links table, site one directly connects to three sites. From there those sites link in an additional four sites. Then from there those sites link in the other three.

    I'd like a query that I imput the number of hops to travel and the starting location and it finds all possible destinations (where hops travelled are equal to or less than specified).

    With the database I used city names for sites, so imagine you are a jet setter and you want to know what cities you can get to with only X number of change overs. For the purposes I will be using this for the max number of hops anything will take is 5, so it won't be going on forever. There will be about 100 sites and about 300 links. In the table I made two records for every link, basically I listed all the links then reversed them since they are bidirectional. I doubt they actually need to be there, but just in case...

    Again, thanks for the help!
    Attached Files Attached Files
    Last edited by dkelcher; 06-07-07 at 23:36.

  8. #8
    Join Date
    Apr 2004
    Location
    Derbyshire, UK
    Posts
    789
    Provided Answers: 1
    Hi

    Unfortunately I cannot download the DB/files (IT policy) but the first thought of the top of my head would be some form of self join (on the link table ?) !!

    Is that totally mad or does it have any merit ??


    MTB
    MTB

  9. #9
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Self joins certainly sound like the way to go imo.
    The code below might help (written for SQL Server).
    Single-ier self join?
    Code:
    SELECT	 e.known_as_and_surname 
    		AS 'Employee'
    	,CASE WHEN m.known_as_and_surname IS NULL THEN '--' ELSE m.known_as_and_surname END
    		AS 'Manager'
    FROM	        employee AS e
    LEFT OUTER JOIN employee AS m
    	ON m.Employee_number = e.manager_number
    George
    Home | Blog

  10. #10
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Quote Originally Posted by MikeTheBike
    Is that totally mad or does it have any merit ??
    No not mad & has utter merit. Better than my solution. I had an extra table in there You only need the base table in once.

    George - I think your solution will not work - it is over simplified. Remember there are two tables involved here
    Testimonial:
    pootle flump
    ur codings are working excelent.

  11. #11
    Join Date
    Nov 2003
    Posts
    16
    Not finished but one way...
    Hope it helps

    something like this... (yesterday i was slleping while posting...)


    dim strSql as string



    Private Function Site(ByVal S As Integer) As String
    Dim exp As Variant
    Dim siteField As String
    Dim SiteN, SiteT As Integer

    For SiteN = 1 To 2 'or more
    siteField = "Site" & SiteN
    exp = DLookup(siteField, "Links", "ID = " & S)
    SiteT = CInt(exp)
    If strSql = "" Then
    strSql = "(Sites.[Site Number])= " & SiteT
    Site (SiteT) ' recursively
    Else
    strSql = strSql & " Or (Sites.[Site Number])= " & SiteT
    If SiteIDTest(SiteT) = False Then ' Test if Site was already slected
    Site (SiteT) ' recursively
    End If
    End If
    Next SiteN
    Site = strSql
    End Function




    sql = "SELECT Sites.[Site Number], Sites.[Site Name] FROM Sites WHERE (" & Site(Me.SiteNumbertoTest) & ");"
    Last edited by PAFF; 06-10-07 at 07:20.

  12. #12
    Join Date
    May 2007
    Posts
    38
    as ive typed this i realise it rambles a bit, but hopefully you will find it helpful

    you may be able to do this recursively, and it would NOT take long to see if it does work - that the benefit of recursion - the code is relatively simple to write

    ------------
    firstly - what are you trying to do with the "hops", as this may affect how you do it


    ------------
    a recursive solution normally is good for things like tree traversal

    although
    1) it may be more difficult to do search a structure like this recursively in any language that doesnt let you use pointers and
    2) if you have too many nodes the stacks overfill and it get slow

    ---------------------
    eg try doing fibonacci numbers in access - after a few recursive iterations it really slow downs

    its easy code - i thonk this is right from memory, but i havent tested it - its great when it works though, as its really elegant

    function fibonacci(a as long) as long
    if a=0 or a=1 then
    fibonnacci = 1
    else
    fibonacci = fibonacci(a-1)+fibonacci(a-2)
    end if

    end function


    sub tryit
    msgbox(fibonacci(10))
    end sub

    should work without testing it, but it takes a long while once you get up to as little as fibnoacci(30) say


    -------------------
    one other problem you will have in any scenario is that

    assuming your hops are bi-directional, you will get problems as you have to stop continuous loops in the processing

    ie node 1 ----> 2 ------> 3 ------> 1,
    in tree traversal you only get back to your start node from underneath as it were, so you wont start to reprocess it.

    In an un-hierarchical structure its perhaps a bit different
    1 - 2 - 3 - back to 1 has to be prevented in some way,

    but 2 - 3- 1 is allowable

    ------------------
    the algorithm for a recursive traversal is something like

    function traversenode(x as variant)
    if endofnode then exit function else
    processnode 'you have to process the node somewhere in the loop
    traverse(leftnode)
    traverse(intermediatenode)
    ----
    ----
    traverse(rightnode)
    end function

    - its the end of node that stops the iteration. as i noted you need to find a way of avoiding this - so you would have to mark each node in some way as you visited it to prevent a further iteration starting.

    ---------------

    just one further thought - if you are trying to find the most effecient way of traversing a network, then you have a real problem - i dont think these issues are resolved - and these theories have real applications in some very expensive industries

    sorry about the rambling thoughts - hope this helps
    Last edited by gemma-the-husky; 06-10-07 at 21:21.

  13. #13
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Couple of queries based on your posted db:

    Code:
    SELECT l_a.Site1 AS origin_site, l_a.Site2 AS single_hop, l_b.site2 AS double_hop
    FROM Links AS l_a LEFT JOIN (SELECT site1, site2 FROM Links WHERE site2 <> 1) AS l_b ON l_a.Site2 = l_b.site1
    WHERE l_a.Site1=1
    Code:
    SELECT Links.Site1 AS origin_site, Links.Site2 AS single_double_hop
    FROM Links
    WHERE Links.Site1=1
    UNION SELECT l_a.Site1 AS origin_site,l_b.site2 AS double_hop
    FROM Links AS l_a LEFT JOIN (SELECT site1, site2 FROM Links WHERE site2 <> 1) AS l_b ON l_a.Site2 = l_b.site1
    WHERE l_a.Site1=1
    Testimonial:
    pootle flump
    ur codings are working excelent.

  14. #14
    Join Date
    May 2007
    Posts
    38
    my pure maths is really old, and i may have the wrong word, but i think this is a connected graph

    i think to do this you realy do need a language that supports pointers (VB may not? Delphi? C?), and then you produce a data structure that uses a datatype to represent a node, and adds new nodes, and connects it using pointers.

    Bearing in mind that if you say have 200 nodes, and each node connects 10 ten others, at siz ply depth you will have 200million possible routes, and will probably be very short of memory!

    Again I dont know, but i think many graphing techniques are intended to produce optimised least cost routes, and such like - there is probably no way to be sure that the optimum has been reached, so the techniques iterate the graph to find improved solutions in a finite time -

    perhaps others here have more knowledge of this stuff

    but, depending on what you want to achieve, i am not sure that access is the best tool at all


    starts from a given node data type, and adds connected nodes, using pointers to refer to the address

  15. #15
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Hi Gemma the husky

    Partly in response to your pm - if you reread the requirements I think recursion turned out to be a wild goose chase. Unless the OP comes back with refined requirements then it should be unnecessary (because of the "two and only two" hops specification). You are quite right though - at n hops things could quickly get out of control.

    I think we need the OP to let us know how we have got on
    Testimonial:
    pootle flump
    ur codings are working excelent.

Posting Permissions

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