使用MODEL子句在有向图中查找循环

问题描述 投票:1回答:1

我有一个包含两列U和V的表,其中带有值的行('a','b')表示从顶点'a'到'b'有一条边。

我可以使用分层查询或递归WITH轻松找到图形中的循环,但我无法绕过MODEL子句以及查找使用它的循环。

所以,问题是:

  1. 如何使用MODEL子句在有向图中找到周期?
  2. (OR)如何使用MODEL子句实现类似于分层查询或递归WITH的行为?

对于表格:

   U   |   V      
----------------
   a   |   b
   b   |   c
   c   |   a
   g   |   h
   h   |   g
      ...

结果应如下所示:

CYCLES
------
a->b->c->a
g->h->g
...
sql oracle graph
1个回答
1
投票

模型设计用于类似电子表格的计算,而不是用于遍历图形。

对于您的数据,您可以使用下面的解决方案,它只返回正确的结果,因为有“数据魔术” - 每个孩子都大于其父。

column path format a15
with dag(u, v) as (
select 'a', 'b' from dual union all
select 'b', 'c' from dual union all
select 'b', 'k' from dual union all
select 'c', 'a' from dual union all
select 'g', 'h' from dual union all
select 'h', 'g' from dual)
select u, v, path || '->' || v path, instr(path, v) is_cycle
from (select t.*, case when u in ('a', 'g') then u end path from dag t)
model
dimension by (u, v)
measures (cast(path as varchar2(4000)) path, 0 cycle)
(
  path[any, any] order by u, v =
  nvl(path[cv(u), cv(v)], max(path)[any, cv(u)] || '->' || cv(u))
)
order by 1, 2;

U V PATH              IS_CYCLE
- - --------------- ----------
a b a->b                     0
b c a->b->c                  0
b k a->b->k                  0
c a a->b->c->a               1
g h g->h                     0
h g g->h->g                  1

6 rows selected.

在一般情况下,您可以使用迭代模型来模拟广度优先搜索,并且在每次迭代时,填充前一次迭代中标记的节点的子节点(并且尚未访问过)的路径。

© www.soinside.com 2019 - 2024. All rights reserved.