# Thread: Find range by hops

1. Registered User
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. Registered User
Join Date
May 2005
Location
Posts
2,888
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.

3. King of Understatement
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.

4. Registered User
Join Date
May 2005
Location
Posts
2,888
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.

5. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
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

6. Registered User
Join Date
May 2005
Location
Posts
2,888
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.

7. Registered User
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!
Last edited by dkelcher; 06-07-07 at 23:36.

8. Registered User
Join Date
Apr 2004
Location
Derbyshire, UK
Posts
805
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. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
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```

10. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
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

11. Registered User
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. Registered User
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. King of Understatement
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
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```

14. Registered User
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. King of Understatement
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

#### Posting Permissions

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