Question 88845 in PostgreSQL Question posted in
The official documentation can be found here.

Cycle detection using directed graph with Apache-AGE and PostgreSQL

I am trying to detect cycles in a graph created on postgreSQl and Apache AGE.

The schema for the graph is as follows:



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)
);

and the sample data is given by

-- 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);

Can someone guide me what the cypher query would be to detect cycles within the graph and also the nodes involved in the cycle.

Tags:

3

Answers


  1. 0

    The code for that would be something like:

    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()
    Login or Signup to reply.
  2. 0

    You can try to experiment with the following query to detect cycles per your defined schema:

    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;
    Login or Signup to reply.
  3. 0

    You can try working out with "WITH RECURSIVE" statement. Here is the official documentation of it.

    Other possible way is to proceed with a custom function. Here is how you can create a custom function.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search