Message-ID: <4B9FDFDE.5030005@andrew.cmu.edu>
Date: Tue, 16 Mar 2010 15:45:34 -0400
From: Tony Cebzanov <tonyceb@andrew.cmu.edu>
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US;
	rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 Mnenhy/0.7.6.0
MIME-Version: 1.0
To: pgsql-sql@postgresql.org
Subject: Avoiding cycles in a directed graph
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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