使用 PostgreSQL 确定网络中的节点

Question

我有一个表，其中每个条目都是一个节点，该表包含每个节点到其他节点的直接连接。我希望为每个节点创建一个包含链中所有节点的列的视图，而不仅仅是节点本身所连接的节点。

一个示例是从下表的前两列生成链中的节点列：

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

这是实际问题的一个小型简化版本。如果我能解决这个例子，全表应该没问题。

该表的数据可以通过以下方式进行可视化：

我研究了几种不同的方法来解决这个问题。我已经研究了递归 CTE，但我还没有设法让它们工作。

每个节点都连接到当前在数据库中的自身。如果有必要，在数据库中删除与自身的连接不是问题。

可能不必要的问题背景：

这个问题的根源来自于试图识别交通中的车辆。原始数据库包含给定区域内每个时间步长 t 的车辆位置和速度。目标是确定在红绿灯处花费的时间。为了解决这个问题，确定了交通灯的停车区域。该区域内速度低于特定阈值的每辆车都被认为正在等待红绿灯。由于排队时间较长，车辆可能会在该区域外排队。因此，一条交通线（“节点链”）由彼此相距一定距离内的所有车辆组成，并且在其下方具有低速。从识别的排队区域内的车辆出发。这个问题是飞机滑行时间科学研究的一部分。

我首先使用 Python 和 Pandas 执行计算以识别区域内的车辆。然而，该代码的运行时间要长 10 倍，这使得它对项目望而却步。代码非常简单，没有手动引入循环，因此无法加速（我相信）。我还将比较在 Python 和 PostgreSQL 中执行排队算法的速​​度。

Answer 1

方法一：

乍一看，我似乎可以应用一个基本的解决方案，因为根据您的示例数据，每个连接都包含在另一个连接中。

SELECT 
    e1.node, 
    e1.connections, 
    COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
    example e1
LEFT JOIN 
    example e2
    ON e2.node <> e1.node
    AND e1.connections <@ e2.connections;

节点 | 连接 | 链中节点
:--- | :---------- | :-------------
| {a,b} | {A B C D}     
乙 | {a,b,c,d} | {A B C D}     
| | {b,c} | {A B C D}     
d | {b,d} | {A B C D}     
电子 | {e,f} | {e,f}         
f | {e,f} | {e,f}         

方法二：

但是，正如@ypercube指出的那样，如果连续有 3 个或更多线性点，则此解决方案不起作用。

例如：e -> f -> g -> h

作为解决这个问题的参考，我使用了另一个相关问题中的答案：

• 在 Postgres 中的多列中的任何一列上分组

它使用一种称为传递闭包的方法来解决这个问题。

传递闭包

在数学中，集合 X 上的二元关系 R 的传递闭包是 X 上包含 R 且具有传递性的最小关系。

例如，如果 X 是一组机场并且 xRy 表示“有从机场 x 到机场 y 的直飞航班”（对于 X 中的 x 和 y），则 R 在 X 上的传递闭包是关系 R+ 使得 x R+ y 表示“可以在一次或多次飞行中从 x 飞到 y”。非正式地，传递闭包为您提供了从任何起点可以到达的所有地点的集合。

首先让我通过添加 4 个节点的线性连接来更改您的示例数据。

DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'],     null),
('g', ARRAY['f','g','h'],     null),
('h', ARRAY['g','h'],         null);

现在应用数学：

WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
  SELECT e1.node, e2.node
  FROM   example e1
  JOIN   example e2
         ON e1.node = any(e2.connections)   
), tc (dst, src) AS
   (
     SELECT dst, src FROM al -- transitive closure
     UNION
     SELECT a1.dst, a2.src
     FROM   al as a1 
     JOIN   tc as a2 
            ON a1.src = a2.dst
   )
   SELECT   src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
   FROM     tc
   GROUP BY src;

给我们这个结果：

src | nodes_in_chain
:-- | :-------------
a   | {a,b,c,d}     
b   | {a,b,c,d}     
c   | {a,b,c,d}     
d   | {a,b,c,d}     
e   | {e,f,g,h}     
f   | {e,f,g,h}     
g   | {e,f,g,h}     
h   | {e,f,g,h}     

db<>在这里摆弄

注意：原始关系只有直接连接，可以将其视为长度为 1 的路径（每个路径 2 个节点）。方法 1 找到所有长度为 2（3 个节点）的路径，因为它应用了一次连接的方法。要找到长度为 N 的路径，您必须应用 N-1 次方法。要找到任意长度的所有路径（即传递闭包），您需要递归解决方案或 while 循环。它不能用简单的 SQL 来完成。（即：一个没有 CTE 的查询。）

_@ypercube