Query to find circular references

I have two tables

ID  Task
1   1
2   2
3   3
4   4

Col1  depend
2     3
2     4
3     1
4     2

ID and Col1 are related through FK constraint. I want to find out all circular references. Here ID and Col1 is just for combining rows from 2 tables, e.g.:

Task 1 can start anytime.
Task 2 can start only after completion of 3, 4 etc

1 –
2 – 3, 4, 1, 2   -- for 2 there is circular dependency
3 – 1
4 – 2, 3, 4      -- also circular dependency

Case 2:

Col1  depend
2     3
2     4
3     1
4     5
5     2

ID  Task
1   1
2   2
3   3
4   4
5   5

1
2 – 3, 4, 1, 5, 2     -- circular reference
3 – 1
4 – 5, 2, 3, 4        -- circular reference
5 – 2, 3, 4, 5        -- circular reference

Circular references may be available at any recursion level. How to find such circular references?

We have tried a recursive query but we went in infinite loop. How to write recursive query for this?

I adapted the example at http://www.postgresql.org/docs/8.4/static/queries-with.html to your case:

WITH RECURSIVE search_graph(id, depends, depth, path, cycle) AS (
        SELECT g.Col1, g.depends, 1,
          ARRAY[g.Col1],
          false
        FROM deps g
      UNION ALL
        SELECT g.Col1, g.depends, sg.depth + 1,
          path || g.Col1,
          g.Col1 = ANY(path)
        FROM deps g, search_graph sg
        WHERE g.Col1 = sg.depends AND NOT cycle
)
SELECT distinct id FROM search_graph where cycle = true;

results:

ID
 4
 2

for the first example,

ID
 4
 2
 5

for the second

You can find the sql fiddle at http://sqlfiddle.com/#!15/87a96/2

StackExchange Database Administrators Q#64663, answer score: 4