基于Apache-AGE和PostgreSQL的有向图环检测Cypher查询指导

To detect cycles in your module dependency graph built with PostgreSQL and Apache-AGE, follow these steps and use the provided Cypher query.

Prerequisite: Set Up the AGE Graph (if not done already) #

First, map your relational data to an AGE graph:

1. Create the graph:

SELECT create_graph('module_deps');

2. Create node and edge labels:

SELECT create_vlabel('module_deps', 'modules');
SELECT create_elabel('module_deps', 'dependencies');

3. Import nodes from the modules table:

INSERT INTO module_deps.modules (id, name, version)
SELECT id, name, version FROM modules;

4. Import edges from the dependencies table:

SELECT * FROM cypher('module_deps', $$
    MATCH (source:modules {id: row.module_id}), (target:modules {id: row.dependency_id})
    CREATE (source)-[:dependencies]->(target)
$$) AS (result agtype);

Cypher Query to Detect Cycles #

This query finds all simple cycles (no repeated nodes except the start/end) and returns unique cycles to avoid duplicates from rotated paths:

MATCH cycle = (start:modules)-[:dependencies*1..]->(start)
WITH cycle, nodes(cycle) AS nodesList
// Filter to only keep simple cycles (no repeated intermediate nodes)
WHERE ALL(n IN nodesList[1..-1] WHERE single(x IN nodesList[1..-1] WHERE x.id = n.id))
// Normalize cycles to avoid duplicate entries from rotated paths
WITH cycle, nodesList, 
     reduce(str = '', n IN nodesList[1..-1] | str + toString(n.id) + ',') AS nodeIdSequence
WITH DISTINCT nodeIdSequence, cycle
RETURN 
  // Return cycle nodes without duplicating the start/end node
  [n IN nodesList[0..-1] | {id: n.id, name: n.name, version: n.version}] AS cycle_nodes,
  length(cycle) AS cycle_length
ORDER BY cycle_length;

Execute the Query in PostgreSQL #

Run the query using Apache-AGE's cypher function:

SELECT * FROM cypher('module_deps', $$
    MATCH cycle = (start:modules)-[:dependencies*1..]->(start)
    WITH cycle, nodes(cycle) AS nodesList
    WHERE ALL(n IN nodesList[1..-1] WHERE single(x IN nodesList[1..-1] WHERE x.id = n.id))
    WITH cycle, nodesList, 
         reduce(str = '', n IN nodesList[1..-1] | str + toString(n.id) + ',') AS nodeIdSequence
    WITH DISTINCT nodeIdSequence, cycle
    RETURN 
      [n IN nodesList[0..-1] | {id: n.id, name: n.name, version: n.version}] AS cycle_nodes,
      length(cycle) AS cycle_length
    ORDER BY cycle_length;
$$) AS (cycle_nodes agtype, cycle_length integer);

Explanation of the Query #

• MATCH cycle = (start:modules)-[:dependencies*1..]->(start): Finds all directed paths that start and end at the same module node, with one or more dependency edges.
• Filter for Simple Cycles: The WHERE clause ensures no intermediate nodes are repeated, eliminating non-simple cycles (paths that loop through the same node multiple times before returning to the start).
• Normalization: Generates a string of intermediate node IDs to identify duplicate cycles that are just rotations of each other (e.g., A→B→C→A and B→C→A→B are treated as the same cycle).
• Return Results: Outputs the list of nodes in each cycle (without repeating the start node at the end) and the cycle length, sorted by length.

Sample Output #

For your provided data, the query will return two cycles:

1. Cycle of length 4: Module A → Module C → Module D → Module E
2. Cycle of length 5: Module A → Module B → Module C → Module D → Module E

内容的提问来源于stack exchange，提问作者Muhammad Awais Bin Adil