Oracle /相互路径

Question

我有一个查询，可以在两个点之间获得路径：

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'               
connect by nocycle prior node_2 = node_1
               and prior node_1 is not null
start with node_1 = 'A'         

它可以正常工作，因此，如果我需要从A到C的路径，它给出：

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

我需要的是要拥有互惠的路径，这意味着从A到C相同，但在上述查询中并不是这样，就好像我要求从C到A的路径它不返回数据。

您能帮我调整查询以满足我的需求吗？

Answer 1

如果您有双向图，则使用UNION ALL在查询中同时包含node_1, node_2和反向node_2, node_1：

with 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 SUBSTR(sys_connect_by_path(node_2, '->'), 3) as path,
       level -1 as hops
from   ( SELECT node_1, node_2 FROM connected_nodes
         UNION ALL
         SELECT node_2, node_1 FROM connected_nodes
         UNION ALL
         SELECT null, 'C' FROM DUAL -- Fake connection to start vertex which
                                    -- prevents C being revisited with the
                                    -- NOCYCLE keyword.
       )
where node_2 = 'A'
start with node_1 IS null
connect by nocycle prior node_2 = node_1;

输出：

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

Answer 2

要获得相反的路径，您需要以另一种方式行走树；我认为您不能在不引入一些奇怪的转移的情况下在一个层次的查询中做到这一点。

您可以将两个搜索说明结合在一起：

with 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 connected_nodes
where node_1 = 'C'               
connect by nocycle prior node_2 = node_1
               and prior node_1 is not null
start with node_1 = 'A'
union all
select ltrim(sys_connect_by_path(node_1, '->'), '->') as path,
       level -1 as hops
from connected_nodes
where node_1 = 'C'
connect by nocycle prior node_1 = node_2
               and prior node_2 is not null
start with node_1 = 'A'
/

在您的初始条件下仍然获得相同的结果：

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

，但所有参考A和C反转的情况都得到了反向路径：

with 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 connected_nodes
where node_1 = 'A'               
connect by nocycle prior node_2 = node_1
               and prior node_1 is not null
start with node_1 = 'C'
union all
select ltrim(sys_connect_by_path(node_1, '->'), '->') as path,
       level -1 as hops
from connected_nodes
where node_1 = 'A'
connect by nocycle prior node_1 = node_2
               and prior node_2 is not null
start with node_1 = 'C'
/
PATH                                                     HOPS
-------------------------------------------------- ----------
C->A                                                        1
C->B->A                                                     2
C->D->A                                                     2
C->D->B->A                                                  3

您不需要内联视图，或者至少在示例数据中直接参考node表。联盟的第一个分支在一个方向上进行了分层查询。第二个分支朝另一个方向划分，在prior和not null检查中交换了引用。一个分支总是没有排，另一个分支获得了您想要的路径。开始/结束条件确定哪个分支得到哪个。