Oracle/procedure to find path between two nodes

Question

I'm still new to oracle and I need help with the below:

let's say I have a table containing nodes :

DECLARE @nodes TABLE (node VARCHAR(5))
INSERT INTO @nodes 
VALUES
('A'),
('B'),
('C'),
('D')

and a table containing how these nodes are connected together:

DECLARE @connected_nodes TABLE (node_1 VARCHAR(5),node_2 VARCHAR(5))
INSERT INTO @connected_nodes 
VALUES
('A','B'),
('B','C'),
('A','C'),
('C','D')

I need to write a procedure in oracle that find the path between two nodes , meaning that for example if I want to go from A to C , I have in above case two paths: A-->C A--B-->C so the procedure must return these two paths along with the number of hops (1 for the first path and 2 for the second in this case)

noting that hundreds/thousands of nodes exist.

your help is very appreciated

Answer 1

This might be a way to do it without the hierarchical queries. They give me a headache.

drop table connected_nodes;

create table connected_nodes (node_1 VARCHAR2(5),node_2 VARCHAR2(5));

INSERT INTO connected_nodes VALUES('A','B');
INSERT INTO connected_nodes VALUES('B','A');
INSERT INTO connected_nodes VALUES('B','C');
INSERT INTO connected_nodes VALUES('A','C');
INSERT INTO connected_nodes VALUES('C','D');

commit;

drop table links;

create table links 
(from_node_1 VARCHAR2(5),
 from_node_2 VARCHAR2(5),
 to_node_1 VARCHAR2(5),
 to_node_2 VARCHAR2(5),
 first_node_1 VARCHAR2(5),
 first_node_2 VARCHAR2(5),
 link_num NUMBER);

drop table paths;

create table paths as select * from links;

create or replace procedure get_paths(p_node_1 VARCHAR2,p_node_2 VARCHAR2)
as
prev_num_links number;
num_links number;
begin

-- get first links in paths

insert into links 
select 
NULL,
NULL,
cn.node_1,
cn.node_2,
cn.node_1,
cn.node_2,
1
from 
connected_nodes cn
where 
cn.node_1 = p_node_1;

-- loop until number of path links does not increase

prev_num_links := 0;

loop

select count(*) into num_links from links;

if num_links = prev_num_links then
    exit;
end if;

-- add new links

insert into links 
select 
l.to_node_1,
l.to_node_2,
c.node_1,
c.node_2,
l.first_node_1,
l.first_node_2,
l.link_num+1
from connected_nodes c,links l
where 
l.to_node_2 = c.node_1 and
l.to_node_2 <> p_node_2 and
(l.to_node_1,
l.to_node_2,
c.node_1,
c.node_2) not in
(select 
from_node_1,
from_node_2,
to_node_1,
to_node_2
from links);

commit;

prev_num_links := num_links;

end loop;

-- populate paths table with links that go backward
-- from end node to beginning.

-- add end nodes

insert into paths
select * from links
where to_node_2 = p_node_2;

-- loop until number of paths rows does not increase

prev_num_links := 0;

loop

select count(*) into num_links from paths;

if num_links = prev_num_links then
    exit;
end if;

-- add new links

insert into paths 
select 
*
from links l
where 
(l.to_node_1,
l.to_node_2,
l.first_node_1,
l.first_node_2,
l.link_num+1)
in
(select
from_node_1,
from_node_2,
first_node_1,
first_node_2,
link_num
from paths) and
(l.from_node_1,
l.from_node_2,
l.to_node_1,
l.to_node_2,
l.first_node_1,
l.first_node_2,
l.link_num)
not in
(select * from paths);

commit;

prev_num_links := num_links;

end loop;

end;
/
show errors

execute get_paths('A','C');

select 
to_node_1,to_node_2,link_num,first_node_1,first_node_2
from paths
order by first_node_1,first_node_2,link_num;

The output looks like this:

TO_NO TO_NO   LINK_NUM FIRST FIRST
----- ----- ---------- ----- -----
A     B              1 A     B
B     C              2 A     B
A     C              1 A     C

The columns first_node_1 and first_node_2 define the path and the link_num column is which link it is in the path.

It is super long and messy. Probably are cases I didn't handle. I guess use hierarchical queries unless you can't. This is one attempt to use SQL and PL/SQL without them.

Answer 2

You need a hierarchical query to get the result you need, applying some logic to only get the paths from a given value to another one:

with nodes (node) as (
    select 'A' from dual union all
    select 'B' from dual union all
    select 'C' from dual union all
    select 'D' from dual
),
connected_nodes (node_1,node_2 ) as
(
    select 'A','B' from dual union all
    select 'B','C' from dual union all
    select 'B','D' from dual union all
    select 'A','C' from dual union all
    select 'A','D' from dual union all
    select 'D','C' from dual union all
    select 'C','D' from dual
)
select ltrim(sys_connect_by_path(node_1, '->'), '->') as path,
       level -1 as hops
from
    (
    select node as node_1, node_2
    from nodes
           left join connected_nodes
             on(node = node_1)
    )         
where node_1 = 'C'               /* where to stop */
connect by nocycle prior node_2 = node_1
               and prior node_1 is not null
start with node_1 = 'A'         /* where to start from */;

gives:

PATH             HOPS
---------- ----------
A->B->C             2
A->B->D->C          3
A->C                1
A->D->C             2

Answer 3

Note that you cannot use DECLARE @connected_nodes TABLE in Oracle as in SQL SERVER. You need to create a table and insert records into table.

The output you require to be displayed can be achieved with this hierarchical query.

select LTRIM ( SYS_CONNECT_BY_PATH ( node_1,'->' ) ,'->')as paths 
, LEVEL-1 as number_of_hops
FROM connected_nodes WHERE LEVEL > 1 
CONNECT  BY NOCYCLE PRIOR node_2 = node_1
;

Here is a complete demo of all the steps.

DEMO

EDIT: : If you only need to find path between specific nodes(A->C), use additional conditions.

select LTRIM ( SYS_CONNECT_BY_PATH ( node_1,'->' ) ,'->')as paths 
, LEVEL-1 as number_of_hops
FROM connected_nodes WHERE
node_1 = 'C' 
START WITH node_1 = 'A' 
CONNECT  BY NOCYCLE PRIOR node_2 = node_1
;