基于Apache-AGE和PostgreSQL的有向图循环检测

iezvtpos 于 2023-04-29 发布在 PostgreSQL

关注(0)|答案(3)|浏览(119)

我试图在postgreSQl和Apache AGE上创建的图表中检测周期。
图表的模式如下所示：

CREATE TABLE modules (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    version VARCHAR(255) NOT NULL
);

CREATE TABLE dependencies (
    module_id INTEGER REFERENCES modules(id),
    dependency_id INTEGER REFERENCES modules(id),
    PRIMARY KEY (module_id, dependency_id)
);

样本数据由下式给出

-- Modules
INSERT INTO modules (name, version) VALUES
('Module A', '1.0.0'),
('Module B', '1.1.0'),
('Module C', '1.2.0'),
('Module D', '2.0.0'),
('Module E', '2.1.0');

-- Dependencies
INSERT INTO dependencies (module_id, dependency_id) VALUES
(1, 2),
(1, 3),
(2, 3),
(3, 4),
(4, 5),
(5, 1);

谁能告诉我密码查询是什么，以检测图中的循环以及循环中涉及的节点。

postgresql

来源：https://stackoverflow.com/questions/76123049/cycle-detection-using-directed-graph-with-apache-age-and-postgresql

3条答案

按热度按时间

xhv8bpkk1#

你可以尝试使用“WITH RECURSIVE”语句。这是它的官方文件。
另一种可能的方法是继续使用自定义函数。Here是如何创建自定义函数的。

赞(0）回复(0）举报 2023-04-29

pgccezyw2#

您可以尝试使用以下查询来检测每个已定义模式的周期：

WITH RECURSIVE detect_cycles(module_id, path, cycle) AS (
SELECT module_id, ARRAY[module_id], false
FROM dependencies
UNION
SELECT d.module_id, path || d.module_id, d.module_id = ANY(path)
FROM dependencies d, detect_cycles c
WHERE d.dependency_id = c.module_id AND NOT cycle
)
SELECT * FROM detect_cycles WHERE cycle;

赞(0）回复(0）举报 2023-04-29

ozxc1zmp3#

代码如下：

g.V().as('start').
    repeat(out().as('next').
           where('next', neq('start')).
           store('path').by(id)).
    until(out().filter('it', eq('start'))).
    select('path').unfold().dedup().groupCount().unfold().
    filter(select(values).is(gt(1))).
    select(keys).unfold().as('cycle').
    select('cycle', out().where(eq('cycle')).dedup().count().as('cycleSize')).
    filter('cycleSize', gt(1)).
    select('cycle').fold()

赞(0）回复(0）举报 2023-04-29

我来回答

基于Apache-AGE和PostgreSQL的有向图循环检测

3条答案

相关问题

热门标签

最新问答