Finding a trail between linked records

[flugh]

I am trying to find a path between zones for delivery. I'm looking at taking 2 zones, and finding the trail of connected zones between them. I'm figuring:

Table: zones
id int
zone varchar(32)

Table: links
id int
zone_a int <- FK zones.id
zone_b int <- FK zones.id

Wondering if there's a JOIN I can do to get a 'trail' betwen the 2. Like if a->b & c, b->d & e, then doing a query(a,e) returns a,b,e.

My frontend is Access 2000, backend is PostgreSQL. I don't think this is a platform/software specific thing though, more of a principle. Any hints greatly appreciated!

----
JBR

 

[alvechurchdata]

If you knew how many steps there would be in the chain then you could join the links table to itself as many time as necessary. For a three-link chain the SQL would be:

Select a.zone_a, d.zone_b 
  from link a, link b, link c, link d 
  where a.zone_a = start And d.zone_b = end And
        a.zone_b = b.zone_a And
        b.zone_b = c.zone_a And
        c.zone_b = d.zone_a

I suppose a real-world solution would be to have multiple queries; one for a one-link chain, one for a two-link chain, one for a three-link chain etc. If you can guarantee that an chain of n links is always cheaper than a chain of n+1 links then the strategy would be to start with the one-link query. If that doesn't find a route then run the two-link query. If that doesn't find a route then run the three-link query. And carrry on until you either find a route or run out of processing time.

Geoff Franklin

http://www.alvechurchdata.co.uk

 

[flugh]

I appreciate the reply. Unfortunately, the depth of recursion is variable and unknown. Areas will have to be added from time to time. Wondering if there may be some trickery to be done with a view or union somehow. Was also thinking of just doing the interface on the webserver, and use php to find the trail.



----
JBR

 

[alvechurchdata]

Unfortunately, the depth of recursion is variable and unknown

There's got to be a limit though. How many zones do you have? There's no point looking for a chain of twenty links if you've only got three zones.

Geoff Franklin

http://www.alvechurchdata.co.uk

 

[flugh]

Right now, I estimate 40. Some I want to link to others. It's not linear at all. I think it's going to end up being a code thing rather than a strictly backend/SQL thing.

I'll boot into Linux later tonight and do a little tinkering. Maybe something will come to me

----
JBR

 

[alvechurchdata]

I think it's going to end up being a code thing/quote]

With 40 zones I think you're right.<g>

This sounds like the classic "Travelling Salesman Problem" which looks for the best way of plotting a salesman's route between customers. It's a famous mathematical conundrum - you might get some inspiration if you try Google for "Travelling Salesman Problem".

Geoff Franklin

http://www.alvechurchdata.co.uk

 

[DanJR]

this looks like graph theory to me, an unweighted directed graph where the nodes of the graph are your zones and the directed vertices link one zone to another.

To store a create in a database, then you could use a table like this:

node_1   node_2
A        B
A        C
B        D
B        E
etc...

ie A links to B, A also links to C, B links to D, B also links to E, etc.

Like if a->b & c, b->d & e, then doing a query(a,e) returns a,b,e.

That assumes a path does actually exist between a and e. Also, what happens if more than one path exists?

My initial thought would be to pull the table into memmory and apply a greedy algorithm approach....e.g. breadth first search.

cheers,
dan.

 

[alvechurchdata]

you could use a table like this

I think JBR's got this already in the links table.

I'd suggest adding a third column to represent the cost of movement between the two zones. Without being able to calculate and compare costs you run the risk of choosing the A-B-C route which looks simple but which costs twice as much as the A-D-E-C route. You'll also have to guard against the computer picking a really stupid backtracking route like A-B-A-B-C.

A lot of people have put a lot of thought into these routing problems. A week's research before you start coding might save you a lot of development effort.

Geoff Franklin

http://www.alvechurchdata.co.uk

 

[flugh]

Thanks for the input. I'll Google up the Traveling Salesman links here after getting my Monday morning out of the way.

I also like the 'weighting' zones deal. Some are preferrable to others. Thinking that there's a hairy recursive function to be done here, where I query Origin and Destination's linked zones, then query each of those linked zone's linked zones, and look for matches. If no matches, take it a step further out. Could get REALLY expensive on a 20-hop route though.

Thanks again for the input!

----
JBR

 

[DanJR]

[qoute]I think JBR's got this already in the links table. [/quote]
oops, your right sorry about that

you don't need to weight to do a search, however weighting is obviously a good idea. The searching algorithm takes care of where you are within the search to ensure to do end up in an infinite loop. e.g. With Dijkstra's algorithm you would use a priority queue.

The only thing you've asked about is traversal of specific path so i'm not sure how the travelling saleman problem will help you.

In terms of time complexity, you could get a traversal in O(E+V log V) where E is edge and V is vertex. However, pulling data across the network may be an issue if you have alot of nodes (zones) and you dont have a very dense graph. if this is the case then other storage structures may prove more efficient - see Joe Celko's book(s).

cheers
dan.

 

[flugh]

I'm definitely going to have to put this on the shelf until next week (doing payroll this week). Way more complicated than I initially thought it would be.

Maybe my desire to be able to drop in new zones with connected-zones links on a whim is the breaking point. Having a job run on say a Saturday night to work out all possible route/linked zones/chains, then put all that into a table. But if there's only 20 zones, and a max of 20 hops, that's 20^20 right? That's alot!

Thinking this little experiment, which probably wouldn't be noticed by anybody, may be more trouble than it's worth

----
JBR

 

[DanJR]

20^20 = wrong!

Why not just (simply) modify Dijkstra's algorithm? The pseudo code is plastered all over the web. I'm not sure how translating pseudo code into a programming language is complicated

cheers.
dan.

 

[alvechurchdata]

20^20 = wrong!

I reckon it's 20 factorial - 2,432,902,008,176,640,000

But is that only the 20-step solutions? Need someone with better math than me.

Geoff Franklin

http://www.alvechurchdata.co.uk