2

This SQLFiddle example describes 2 tables and their relationship:

  1. Primary Routes: A direct route between 2 places. Indirect primary routes are for relationship purposes with the secondary routes table

  2. Secondary Routes: A route between 2 places where no direct primary route exists

Now, a user wants to go from one place to another. So, for this example, a user selects the following points:

  1. London->Harlow:

A direct route exists. The SQL is simple:

SELECT * 
FROM primary_routes 
WHERE 
    (
        (point1 = 'London' AND point2 = 'Harlow') 
        OR (point1 = 'Harlow' AND point2 = 'London')
    ) 
    AND direct = 1

A route is only entered once in the DB, however a route goes both ways.

  1. Stanmore->Waltham:

No direct route exists, however both these points lie on the same route. The SQL is:

SELECT DISTINCT primary_id 
FROM secondary_routes 
WHERE point IN ( 'Stanmore', 'Waltham')

Now, the complexity will increase because there might be other kinds of connections, for example:

  1. London-Sheering: No route from 1 and 2 above fits. However, routes exist between London->Harlow and Harlow-Sheering.

  2. Wembley-Shenley: No route from 1, 2, or 3 fits. However, routes exist between Wembley->London->Watford->Shenley, or Wembley->London->Harlow->Shenley

Is it possible to build a (not so complex) SQL statement that will return the routes for 3 and 4, and furthermore, for each route found (including in 2), the distance between the 2 points must be calculated and be part of the route.

abatishchev
  • 98,240
  • 88
  • 296
  • 433
Ivan-Mark Debono
  • 15,500
  • 29
  • 132
  • 263
  • The only way to do this with a single SQL statement would be a [recursive CTE](http://www.sqlite.org/lang_with.html), which is not available in all Android versions. You have to implement the graph search manually. – CL. Jun 16 '15 at 06:55
  • @CL I'm targeting API 22 and the minimum will be 19. Is the SQLite with recurive CTE available in this API? – Ivan-Mark Debono Jun 16 '15 at 07:39
  • You'd need SQLite 3.8.3 or later; see [Version of SQLite used in Android?](http://stackoverflow.com/questions/2421189/version-of-sqlite-used-in-android) – CL. Jun 16 '15 at 07:40
  • I'll need to check the version. However, how might such a graph search look like with using recursive cte? – Ivan-Mark Debono Jun 16 '15 at 07:50

2 Answers2

0

In a word, no, there is no simple SQL query given your data structure that would easily find those routes.

You would probably be better off pre-calculating those routes and distances and populating those into a third table. e.g. StartPoint, EndPoint, TransferPoint, ToTransfer_Primary_id, FromTransfer_PrimaryID2, Distance.

You would have to build it up in stages.

For example for London -> Harlow you can use the primary routes

select firstroute.point1 as startpoint, firstroute.id as ToTransfer_Primary_id, firstroute.point2 as transferpoint, secondroute.id as FromTransfer_Primary_id , secondroute.point2 as endpoint
from primary_routes as firstroute
inner join primary_routes as secondroute on secondroute.point1 = firstroute.point2
WHERE firstroute.point1 = 'London'
AND secondroute.point2 = 'Harlow'

Which gives you

startpoint  ToTransfer_Primary_id   transferpoint   FromTransfer_Primary_id endpoint
London      2                       Watford         4                       Harlow

Then you would have to write a query to test for a transfer point at one of the secondary routes.

Dijkgraaf
  • 11,049
  • 17
  • 42
  • 54
0

I didn't see the direct route distance in the link you posted (which you would need to calculate total distance), but you can compare points in two copies of the table which join wherever a.point1 is what you'd like as well as b.point2 and the two have a common point a.point2=b.point1

select 
   a.point1 as startpoint,
   b.point2 as endpoint, 
   a.point2 as midpoint,
from primary_routes a
join primary_routes as b on b.point1=a.point2   
where a.point1 like '%London%'
    and
    b.point2 like '%Harlow%'
Patrick Williams
  • 21
  • 7