Skip to Main Content
  • Questions

  • how to find routes between two sites based on table data in oracle?

Breadcrumb

Question and Answer

Chris Saxon

Thanks for the question, Arifullah.

Asked: August 17, 2023 - 4:44 am UTC

Last updated: August 21, 2023 - 12:53 pm UTC

Version: 19c

Viewed 1000+ times

You Asked

I want to store sites and sites connections for example Site A is connected to site B and C. B is connected to E. C is connected to D. D is connected to G and F. F is connected to E. E is connected to J and H. how to find all the possible routes between two sites for example When I want to find the routes between two sites for example from site A to J so It must show me all the possible routes from site A to J for example there is only two routes the first is A-B-E-J and the second is A-C-D-F-E-J. I have created two tables PRACTICE_SITES table (site_id, site_name) and PRACTICE_CONNECTIONS table (connection_id pk, site_id fk(practice_sites.site_id), CONNECTED_SITE_ID fk(practice_sites.site_id)). I have got the following queries from chatgpt but it did not work.

1.First query:

SELECT 
  CONNECT_BY_ROOT s1.SITE_NAME AS site_1,
  s2.SITE_NAME AS site_2,
  SYS_CONNECT_BY_PATH(s2.SITE_NAME, '-') AS route
FROM 
  PRACTICE_SITES s1
JOIN 
  PRACTICE_CONNECTIONS c ON s1.site_id = c.site_id
JOIN 
  PRACTICE_SITES s2 ON c.connected_site_id = s2.site_id
WHERE 
  s1.SITE_NAME ='A'
  AND s2.SITE_NAME ='J'
START WITH 
  s1.SITE_NAME ='A'
CONNECT BY 
  NOCYCLE PRIOR s2.site_id = c.site_id


2.Second query:

WITH RECURSIVE possible_routes(site_1, site_2, route, level) AS (
  SELECT 
    s.site_name AS site_1, 
    s2.site_name AS site_2, 
    s.site_name || '-' || s2.site_name AS route, 
    1 AS level
  FROM 
    practice_sites s
  JOIN 
    PRACTICE_CONNECTIONS c ON s.site_id = c.site_id
  JOIN 
    practice_sites s2 ON c.CONNECTED_SITE_ID = s2.site_id
  WHERE 
    s.site_name = 'A'
    AND s2.site_name = 'J'
    
  UNION ALL
  
  SELECT 
    pr.site_1,
    s.site_name AS site_2,
    pr.route || '-' || s.site_name AS route,
    pr.level + 1 AS level
  FROM 
    possible_routes pr
  JOIN 
    PRACTICE_CONNECTIONS c ON pr.site_2 = c.site_id
  JOIN 
    practice_sites s ON c.CONNECTED_SITE_ID = s.site_id
  WHERE 
    pr.level < 5 -- Limit the number of levels to avoid infinite recursion
)
SELECT 
  site_1, site_2, route
FROM 
  possible_routes;

and Chris said...

To find all the paths, you need to build all the routes from A, then filter to those that end in J. Those queries are finding the direct connections from A-J with no steps in between.

Here's an example using CONNECT BY. The WHERE clause is applied after building the tree. So this builds all the paths from A and filters down to those that end in J:

create table connections (
  site_id char(1), connected_site_id char(1),
  primary key ( site_id, connected_site_id )
);

insert into connections values ( 'A', 'B' );
insert into connections values ( 'A', 'C' );
insert into connections values ( 'B', 'E' );
insert into connections values ( 'C', 'D' );
insert into connections values ( 'D', 'G' );
insert into connections values ( 'D', 'F' );
insert into connections values ( 'F', 'E' );
insert into connections values ( 'E', 'J' );
insert into connections values ( 'E', 'H' );
       
select ltrim ( sys_connect_by_path ( site_id, ',' ), ',' ) || ',' || connected_site_id paths
from   connections
where  connected_site_id = 'J'
start  with site_id = 'A'
connect by prior connected_site_id = site_id;

PATHS        
------------
A,B,E,J
A,C,D,F,E,J

Rating

  (3 ratings)

Is this answer out of date? If it is, please let us know via a Comment

Comments

Arifullah Stanikzai, August 18, 2023 - 6:06 pm UTC

Thank you Chris from your answer, but in the same table of structure and data that you provided in the answer there is a problem that I found. The problem is that if I want to find the routes between A and F the query only show one route which is A,C,D,F but, there is also another possible route which is A,B,E,F if we draw the connections between sites. And also if we want to find the routes from B to D so the select query does not return anything, infact there are two possible routes between them. In the last I want to say that if you could create me such a table structure and select query in which I can find the all possible routes between two sites for example from D to B, from G to B and so on. That is huge problem for me that I am stack in it for a couple of days.
Chris Saxon
August 21, 2023 - 12:48 pm UTC

See mathguy's response below.

In general graph traversal algorithms are tricky to write in SQL. The upcoming release - 23c - adds support for Property Graph Query in SQL which makes answering questions like this easier. For more details see

https://blogs.oracle.com/database/post/operational-property-graphs-in-oracle-database-23c-free-developer-release


paths in undirected graph

mathguy, August 20, 2023 - 5:44 am UTC

So, you view your graph (consisting of your sites and connections) as an undirected graph. If you use the data model from Chris's answer, where each connection appears exactly once and in only one direction, the first step will need to be to union (all) the connections table with its "reverse", to get all the connections in both directions.

I also assume that you have no interest in routes that visit the same site more than once (something like A,B,C,A,E,F,J - the trip from A to itself passing through B and C, only to then go to J via E and F, is not needed). So, you must pay attention to cycles - either in the graph itself, or caused by the bi-directional connections. The bi-directional connections can by themselves cause cycles: A,B,A,C,D,E,F,J, even if the undirected graph has no cycles.

In a CONNECT BY query, cycles are detected based on the columns that appear with the operator PRIOR in the CONNECT BY clause. In the query below, we use column CONNECTED_SITE_ID in that way; we will avoid all cycles, except perhaps returning to the origin (since the origin is not a CONNECTED_SITE_ID when we start) - so we need to pay attention to that.

Two modifications to Chris's query are the simpler way to build the paths in SELECT, and the condition PRIOR CONNECTED_SITE_ID != :DESTINATION. The latter is a trivial optimization: we should not continue the depth-first traversal after we already reached the desired destination.

I also show the origin and destination as bind variables.

Be prepared to get horrible performance on anything of non-trivial size; if this is a homework problem, the solution might be accepted, but if you want to use this to find flights from Beijing to Las Vegas in a production environment, your CPU will melt down. What will work is to add a condition on maximum number of stopovers - something like 2 or 3 is probably reasonable.

select  :origin || sys_connect_by_path(connected_site_id, ',') as paths
from    ( select site_id, connected_site_id from connections union all
          select connected_site_id, site_id from connections )
where   connected_site_id = :destination
start   with site_id = :origin
connect by nocycle site_id = prior connected_site_id
               and connected_site_id != :origin
               and prior connected_site_id != :destination
;

Chris Saxon
August 21, 2023 - 12:49 pm UTC

Thanks for explaining this

How to visualize those data in oracle apex 21.2?

Arifullah Stanikzai, August 21, 2023 - 7:26 am UTC

Thank you mathguy for solving my problem. I have achieved what I was looking for. Now If you can tell me that how to visualize the above table data in oracle apex 21.2 which show the relationships between all sites. for example a hierarchy diagram shows all the sites which are connected to each other.
Chris Saxon
August 21, 2023 - 12:53 pm UTC

If you need help with APEX, please ask on the APEX forum: https://forums.oracle.com/ords/apexds/domain/dev-community/category/apex
more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's channel and Chris's channel from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.