无向图中的最小 ID
Smallest ID from an Undirected graph
使用 Oracle 11g，我试图在 ID 对的无向图中找到最小的 ID。
使用以下对：
create table unique_pairs ( ID1 INT, ID2 INT );
insert all
into unique_pairs (ID1,ID2) VALUES ( 1, 2 )
into unique_pairs (ID1,ID2) VALUES ( 1, 3 )
into unique_pairs (ID1,ID2) VALUES ( 4, 2 )
into unique_pairs (ID1,ID2) VALUES ( 4, 5 )
into unique_pairs (ID1,ID2) VALUES ( 7, 6 )
into unique_pairs (ID1,ID2) VALUES ( 8, 10 )
into unique_pairs (ID1,ID2) VALUES ( 10, 7 )
select * from dual;
commit;
我正在使用两个连接查询的联合来尝试在地图的两个方向上行驶：
select distinct a.ID1, a.ID2, min(a.ultimate_parent_id ) as ultimate_parent_id
from
(SELECT distinct ID1, ID2,
connect_by_root(ID2) ultimate_parent_id
FROM unique_pairs
CONNECT BY ID2 = prior ID1 AND ID2 != PRIOR ID2
union
SELECT distinct ID1, ID2,
connect_by_root(ID1) ultimate_parent_id
FROM unique_pairs
CONNECT BY ID1 = prior ID2 AND ID1 != PRIOR ID1) a
group by a.ID1, a.ID2
order by 3;
我明白了：
ID1 ID2 ULTIMATE_PARENT_ID
1 2 1
1 3 1
4 2 2
4 5 4
10 7 6
7 6 6
8 10 6
应该是这样的：
ID1 ID2 ULTIMATE_PARENT_ID
1 2 1
1 3 1
4 2 1
4 5 1
10 7 6
7 6 6
8 10 6
我认为我的问题与这样一个事实有关，即当我的数据是非定向的时，按函数连接意味着层次结构。任何帮助都会很棒，谢谢！
概念
您的问题基本上由 3 个步骤组成：
- 识别无向图的连通分量
G
- 用最小id的顶点表示每个连通分量
- 将图的每条边映射到它所属的连通分量的代表。
任务解决者：
- 考虑 'equivalent' 有向图
D_1 基于 G 的顶点 ID 的自然数字排序。
- 通过按
D_1. 表示的顺序抽象出链，将 D_1 减少为包含所有候选 ID 的二分图 B
- 确定
B 中的最小代表性 ID。
- 建立从
G 的边到 B 的边及其弱连通分量 (WCC) 的映射。
详情
G的边集正是unique_pairs的记录给出的对(id1, id2)的集合。 G 的顶点集与 unique_pairs 的 id 列的值集相匹配。由于 G 是无向的，所以用记录 (id1, id2) 或 (id2, id1) 来表示一条边并不重要；从今以后，我们假设 wlog id1 < id2 对 unique_pairs 中的每个记录 (id1, id2) 成立。
我们通过根据从 G 派生的有向图 D_1 构造一个辅助结构来解决这个任务，方法是根据其关联顶点的 id 的数字顺序来定向无向图的每条边.设 D_2 为 D_1，所有边的方向都反转。识别原始图的连通分量相当于识别 D_1 或 D_2 中的 WCC。观察到 D_1 在结构上是非循环的。
辅助辅助结构是 G 中边集到 D_1 中最大链（= 一条路径不包含在另一条路径中）的幂集的映射，使得所有链在边缘 e 的图像中包含 e 并最大化其终端（= 开始和结束顶点）的数字 id 之间的差异。幂集的使用是一种技术性，否则当两个最大链共享相同的终端但遵循 'alternative routes'（通常图像将包含单个元素）时，映射可能无法明确定义。
下一步我们粗化映射：图像将是原始映射图像中任何最大链的终端 ID 对，而不是最大链集。
鉴于此映射，我们构建了一个辅助二分图 B，其边精确地表示终端 ID 的有序对。该图是二分图，因为最大链的结束顶点不能是另一个最大链的起始顶点，反之亦然 - 如果发生这种情况，则所述链不会是最大的。
但是，根据构造，B 构成了 D_1 的传递闭包的一部分。因此，B的WCC的顶点集是D_1的WCC的顶点集的子集。我们最终对后面每个 WCC 中具有最小 id 的顶点感兴趣。由于最大链中包含的终端 ID 不能小于起始顶点 ID，因此所有这些顶点都必须包含在 B 的顶点集中。所以我们必须考虑 B 的 WCC 只取每个的最小终端 ID。连同所有 G 边到 B 边的辅助映射，从而映射到 B 的 WCC，我们解决了原始问题。
SQL实施
在预处理步骤中，G 的边被归一化为其入射顶点的自然顺序。假设边的方向是id1 -> id2，test_unique_pairs也代表D_1。
update test_unique_pairs
set id1 = id2
, id2 = id1
where id1 > id2
;
第一个查询将 D_1 的边映射到 B 的边，即。 D_1 中最大链的终端 ID 对。这些链在构造上是非循环的，将通过 test_unique_pairs 上的分层查询计算，它们将由它们的开始和结束顶点表示，这些对也表示 B 中的边。这种映射以共享两个终端的替代链为模发生 - 如果它们共享两个终端，则不同的最大路径被认为是等效的。 oracle 中的分层查询允许轻松提取最大元素。然而，最小元素是层次结构中父子关系颠倒的最大元素（为了满足这种计算是考虑两个二合字母 D_1、D_2）的原因。
为了简化第二个处理阶段，将查询id包装到一个视图定义中：
create or replace view test_up_chains as
select *
from ( -- collect minimal/maximal reachable id for each edge in G
select distinct
inter.id1
, inter.id2
, min(minelt) chainstart
, max(maxelt) chainend
from ( -- collect minimum/maximum terminal id for chains starting/ending with any of G's edges
select distinct
inter_min.id1
, inter_min.id2
, inter_min.minelt
, inter_max.maxelt
from ( -- hierarchical query for maximal chains in D_1
select distinct
hup.ID1
, hup.ID2
, CONNECT_BY_ROOT hup.id2 maxelt
from test_unique_pairs hup
connect by nocycle prior hup.id1 = hup.id2
start with hup.id2 in (
select ref1.id2
from test_unique_pairs ref1
where not exists (
select 1
from test_unique_pairs ref2
where ref2.id1 = ref1.id2
)
)
) inter_max
join ( -- hierarchical query for maximal chains in D_2 ( = D_1 with reversed edge orientations )
select distinct
hup.ID1
, hup.ID2
, CONNECT_BY_ROOT hup.id1 minelt
from test_unique_pairs hup
connect by nocycle prior hup.id2 = hup.id1
start with hup.id1 in (
select ref1.id1
from test_unique_pairs ref1
where not exists (
select 1
from test_unique_pairs ref2
where ref2.id2 = ref1.id1
)
)
) inter_min
on ( inter_min.id1 = inter_max.id1 AND inter_min.id2 = inter_max.id2 )
) inter
group by grouping sets ( (inter.id1, inter.id2) )
) base
order by base.id1
, base.id2
;
接下来 B 的边被合并到 WCC 中，并提取它们各自的最小 ID。以下分层查询缺少 STARTS WITH 子句，构建完整的传递闭包 wrt 边关联关系，并且对于 B 中的每个边，生成到同一 WCC 中所有其他边的根路径。因此，在给定 G 中的一条边的情况下，最小化所有层次结构“根”的起始顶点可找到 G 中的最小可达 ID。 NOCYCLE 指令禁止循环。
select *
from (
select distinct
id1
, id2
, min(chainlim) chainrep
from (
select distinct
id1
, id2
, connect_by_root chainstart chainlim
from test_up_chains
connect by nocycle ( ( prior chainstart = chainstart and prior chainend != chainend ) OR ( prior chainstart != chainstart and prior chainend = chainend ) )
) base
group by grouping sets ( ( base.id1, base.id2 ) )
)
order by id1
, id2
;
Collapsar 的描述非常冗长，但这里有一个符合您要求的非常简短的解决方案。我离图论时代太远了，无法像他那样解释它，但简单的解释是，由于你的 unique_pairs 表示无向图中的边，它可以在有向图中表示为并集ID1、ID2 与 ID2、ID1 因此是我的第一个常用 table 表达式。使用该有向图，您可以像我的第二个常见 table 表达式一样计算所有连接的节点对。最后你可以加入你原来的 unique_pairs table 到我在 ID1 上的连接对 CTE 并取最小根节点作为你的 ULTIMATE_PARENT_ID:
with dg1 as (
select id1, id2 from unique_pairs
union all
select id2, id1 from unique_pairs
), cp as (
select id1
, CONNECT_BY_ROOT id1 root
from dg1
connect by nocycle prior id1 = id2
)
select dg1.*
, min(root) ULTIMATE_PARENT_ID
from unique_pairs dg1
join cp
on cp.id1 = dg1.id1
group by dg1.id1, dg1.id2
order by 1,2
| ID1 | ID2 | ULTIMATE_PARENT_ID |
|-----|-----|--------------------|
| 1 | 2 | 1 |
| 1 | 3 | 1 |
| 4 | 2 | 1 |
| 4 | 5 | 1 |
| 7 | 6 | 6 |
| 8 | 10 | 6 |
| 10 | 7 | 6 |
使用 Oracle 11g，我试图在 ID 对的无向图中找到最小的 ID。
使用以下对：
create table unique_pairs ( ID1 INT, ID2 INT );
insert all
into unique_pairs (ID1,ID2) VALUES ( 1, 2 )
into unique_pairs (ID1,ID2) VALUES ( 1, 3 )
into unique_pairs (ID1,ID2) VALUES ( 4, 2 )
into unique_pairs (ID1,ID2) VALUES ( 4, 5 )
into unique_pairs (ID1,ID2) VALUES ( 7, 6 )
into unique_pairs (ID1,ID2) VALUES ( 8, 10 )
into unique_pairs (ID1,ID2) VALUES ( 10, 7 )
select * from dual;
commit;
我正在使用两个连接查询的联合来尝试在地图的两个方向上行驶：
select distinct a.ID1, a.ID2, min(a.ultimate_parent_id ) as ultimate_parent_id
from
(SELECT distinct ID1, ID2,
connect_by_root(ID2) ultimate_parent_id
FROM unique_pairs
CONNECT BY ID2 = prior ID1 AND ID2 != PRIOR ID2
union
SELECT distinct ID1, ID2,
connect_by_root(ID1) ultimate_parent_id
FROM unique_pairs
CONNECT BY ID1 = prior ID2 AND ID1 != PRIOR ID1) a
group by a.ID1, a.ID2
order by 3;
我明白了：
ID1 ID2 ULTIMATE_PARENT_ID
1 2 1
1 3 1
4 2 2
4 5 4
10 7 6
7 6 6
8 10 6
应该是这样的：
ID1 ID2 ULTIMATE_PARENT_ID
1 2 1
1 3 1
4 2 1
4 5 1
10 7 6
7 6 6
8 10 6
我认为我的问题与这样一个事实有关，即当我的数据是非定向的时，按函数连接意味着层次结构。任何帮助都会很棒，谢谢！
概念
您的问题基本上由 3 个步骤组成：
- 识别无向图的连通分量
G - 用最小id的顶点表示每个连通分量
- 将图的每条边映射到它所属的连通分量的代表。
任务解决者：
- 考虑 'equivalent' 有向图
D_1基于G的顶点 ID 的自然数字排序。 - 通过按
D_1. 表示的顺序抽象出链，将 - 确定
B中的最小代表性 ID。 - 建立从
G的边到B的边及其弱连通分量 (WCC) 的映射。
D_1 减少为包含所有候选 ID 的二分图 B
详情
G的边集正是unique_pairs的记录给出的对(id1, id2)的集合。 G 的顶点集与 unique_pairs 的 id 列的值集相匹配。由于 G 是无向的，所以用记录 (id1, id2) 或 (id2, id1) 来表示一条边并不重要；从今以后，我们假设 wlog id1 < id2 对 unique_pairs 中的每个记录 (id1, id2) 成立。
我们通过根据从 G 派生的有向图 D_1 构造一个辅助结构来解决这个任务，方法是根据其关联顶点的 id 的数字顺序来定向无向图的每条边.设 D_2 为 D_1，所有边的方向都反转。识别原始图的连通分量相当于识别 D_1 或 D_2 中的 WCC。观察到 D_1 在结构上是非循环的。
辅助辅助结构是 G 中边集到 D_1 中最大链（= 一条路径不包含在另一条路径中）的幂集的映射，使得所有链在边缘 e 的图像中包含 e 并最大化其终端（= 开始和结束顶点）的数字 id 之间的差异。幂集的使用是一种技术性，否则当两个最大链共享相同的终端但遵循 'alternative routes'（通常图像将包含单个元素）时，映射可能无法明确定义。
下一步我们粗化映射：图像将是原始映射图像中任何最大链的终端 ID 对，而不是最大链集。
鉴于此映射，我们构建了一个辅助二分图 B，其边精确地表示终端 ID 的有序对。该图是二分图，因为最大链的结束顶点不能是另一个最大链的起始顶点，反之亦然 - 如果发生这种情况，则所述链不会是最大的。
但是，根据构造，B 构成了 D_1 的传递闭包的一部分。因此，B的WCC的顶点集是D_1的WCC的顶点集的子集。我们最终对后面每个 WCC 中具有最小 id 的顶点感兴趣。由于最大链中包含的终端 ID 不能小于起始顶点 ID，因此所有这些顶点都必须包含在 B 的顶点集中。所以我们必须考虑 B 的 WCC 只取每个的最小终端 ID。连同所有 G 边到 B 边的辅助映射，从而映射到 B 的 WCC，我们解决了原始问题。
SQL实施
在预处理步骤中，G 的边被归一化为其入射顶点的自然顺序。假设边的方向是id1 -> id2，test_unique_pairs也代表D_1。
update test_unique_pairs
set id1 = id2
, id2 = id1
where id1 > id2
;
第一个查询将 D_1 的边映射到 B 的边，即。 D_1 中最大链的终端 ID 对。这些链在构造上是非循环的，将通过 test_unique_pairs 上的分层查询计算，它们将由它们的开始和结束顶点表示，这些对也表示 B 中的边。这种映射以共享两个终端的替代链为模发生 - 如果它们共享两个终端，则不同的最大路径被认为是等效的。 oracle 中的分层查询允许轻松提取最大元素。然而，最小元素是层次结构中父子关系颠倒的最大元素（为了满足这种计算是考虑两个二合字母 D_1、D_2）的原因。
为了简化第二个处理阶段，将查询id包装到一个视图定义中：
create or replace view test_up_chains as
select *
from ( -- collect minimal/maximal reachable id for each edge in G
select distinct
inter.id1
, inter.id2
, min(minelt) chainstart
, max(maxelt) chainend
from ( -- collect minimum/maximum terminal id for chains starting/ending with any of G's edges
select distinct
inter_min.id1
, inter_min.id2
, inter_min.minelt
, inter_max.maxelt
from ( -- hierarchical query for maximal chains in D_1
select distinct
hup.ID1
, hup.ID2
, CONNECT_BY_ROOT hup.id2 maxelt
from test_unique_pairs hup
connect by nocycle prior hup.id1 = hup.id2
start with hup.id2 in (
select ref1.id2
from test_unique_pairs ref1
where not exists (
select 1
from test_unique_pairs ref2
where ref2.id1 = ref1.id2
)
)
) inter_max
join ( -- hierarchical query for maximal chains in D_2 ( = D_1 with reversed edge orientations )
select distinct
hup.ID1
, hup.ID2
, CONNECT_BY_ROOT hup.id1 minelt
from test_unique_pairs hup
connect by nocycle prior hup.id2 = hup.id1
start with hup.id1 in (
select ref1.id1
from test_unique_pairs ref1
where not exists (
select 1
from test_unique_pairs ref2
where ref2.id2 = ref1.id1
)
)
) inter_min
on ( inter_min.id1 = inter_max.id1 AND inter_min.id2 = inter_max.id2 )
) inter
group by grouping sets ( (inter.id1, inter.id2) )
) base
order by base.id1
, base.id2
;
接下来 B 的边被合并到 WCC 中，并提取它们各自的最小 ID。以下分层查询缺少 STARTS WITH 子句，构建完整的传递闭包 wrt 边关联关系，并且对于 B 中的每个边，生成到同一 WCC 中所有其他边的根路径。因此，在给定 G 中的一条边的情况下，最小化所有层次结构“根”的起始顶点可找到 G 中的最小可达 ID。 NOCYCLE 指令禁止循环。
select *
from (
select distinct
id1
, id2
, min(chainlim) chainrep
from (
select distinct
id1
, id2
, connect_by_root chainstart chainlim
from test_up_chains
connect by nocycle ( ( prior chainstart = chainstart and prior chainend != chainend ) OR ( prior chainstart != chainstart and prior chainend = chainend ) )
) base
group by grouping sets ( ( base.id1, base.id2 ) )
)
order by id1
, id2
;
Collapsar 的描述非常冗长，但这里有一个符合您要求的非常简短的解决方案。我离图论时代太远了，无法像他那样解释它，但简单的解释是，由于你的 unique_pairs 表示无向图中的边，它可以在有向图中表示为并集ID1、ID2 与 ID2、ID1 因此是我的第一个常用 table 表达式。使用该有向图，您可以像我的第二个常见 table 表达式一样计算所有连接的节点对。最后你可以加入你原来的 unique_pairs table 到我在 ID1 上的连接对 CTE 并取最小根节点作为你的 ULTIMATE_PARENT_ID:
with dg1 as (
select id1, id2 from unique_pairs
union all
select id2, id1 from unique_pairs
), cp as (
select id1
, CONNECT_BY_ROOT id1 root
from dg1
connect by nocycle prior id1 = id2
)
select dg1.*
, min(root) ULTIMATE_PARENT_ID
from unique_pairs dg1
join cp
on cp.id1 = dg1.id1
group by dg1.id1, dg1.id2
order by 1,2
| ID1 | ID2 | ULTIMATE_PARENT_ID |
|-----|-----|--------------------|
| 1 | 2 | 1 |
| 1 | 3 | 1 |
| 4 | 2 | 1 |
| 4 | 5 | 1 |
| 7 | 6 | 6 |
| 8 | 10 | 6 |
| 10 | 7 | 6 |