From: Tony Cebzanov <tonyceb@andrew.cmu.edu>
To: pgsql-sql@postgresql.org
Subject: Avoiding cycles in a directed graph
Date: Tue, 16 Mar 2010 15:45:34 -0400
Message-ID: <4B9FDFDE.5030005@andrew.cmu.edu> (raw)
I'm using the following table to represent an acyclic directed graph:
CREATE TABLE edge(
id SERIAL PRIMARY KEY,
child INTEGER NOT NULL,
parent INTEGER,
UNIQUE (child, parent)
);
I see there is an example in the online docs for detecting cycles in
recursive queries, and I've adapted the example query to the table above:
WITH RECURSIVE search_graph(parent, child, id, depth, path, cycle)
AS (
SELECT e.parent, e.child, e.id, 1,
ARRAY[e.id],
false
FROM edge e
UNION ALL
SELECT e.parent, e.child, e.id, sg.depth + 1,
path || e.id,
e.id = ANY(path)
FROM edge e, search_graph sg
WHERE e.parent = sg.child AND NOT cycle
)
SELECT * FROM search_graph;
That's great to avoid looping forever on queries, but what about
preventing anyone from inserting edges that would create cycles in the
first place? I reckon I'll need a trigger of some sort, but nothing
I've tried has enabled me to do the cycle check as part of the trigger
to avoid inserting an edge that would create a cycle. I tried having
the non-recursive SELECT use NEW.parent, NEW.child, etc. but that isn't
working. Is there any way to do this, or do I have to just insert the
edge, check if it cycles, and delete it if it does?
Thanks.
-Tony
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: tonyceb@andrew.cmu.edu
Subject: Re: Avoiding cycles in a directed graph
In-Reply-To: <4B9FDFDE.5030005@andrew.cmu.edu>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox