Postgres recursive function unique values

Question

I have a graph structure

Node(pid integer)
Neighbor(pid integer, pidn integer)

Node is trivial, and I should say that Neighbor stores for every node its list of Neighbors. This is the graph I am testing (contents of the Neighbor relation):

PID | PIDN
==========
1   | 2
1   | 3
2   | 1
2   | 3
2   | 4
2   | 5
3   | 1
3   | 2
4   | 2
4   | 6
5   | 2
6   | 4

I want to get the set of all neighbors of a node, with degree less than a fixed number, so I execute the following query:

WITH RECURSIVE search_graph(root, depth) AS (
        SELECT n.pidn, 1
        FROM node p, neighbor n
        WHERE p.pid = n.pid
        AND p.pid = 1
      UNION
        SELECT nxt.pidn, sg.depth + 1
        FROM neighbor nxt, search_graph sg
        WHERE sg.root = nxt.PID
        AND sg.depth < 3
)
SELECT * FROM search_graph s;

The starting node is 1, and the maximal depth is 3 (in case you missed them). I get the following result:

Node | Depth
============
2    | 1
3    | 1
1    | 2
3    | 2
4    | 2
5    | 2
2    | 2
2    | 3
3    | 3
1    | 3
4    | 3
5    | 3
6    | 3

because it expands all the children of each node, including visited children:

0                               1
1               2                               3
2       1    3    4    5                    1       2
3      2 3  1 2  2 6   2                   2 3   1 3 4 5

While it I want to exclude visited children, producing:

Node | Depth
============
2    | 1
3    | 1
4    | 2
5    | 2
6    | 3

I need a method to add results to search_graph ONLY IF the node was not visited.

Answer 1

Have you read the Postgresql documentation about WITH RECURISVE?

There are some examples with graphs and one of them looks like a solution of your problem:

This query will loop if the link relationships contain cycles. Because we require a "depth" output, just changing UNION ALL to UNION would not eliminate the looping. Instead we need to recognize whether we have reached the same row again while following a particular path of >links. We add two columns path and cycle to the loop-prone query:

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
    SELECT g.id, g.link, g.data, 1,
      ARRAY[g.id],
      false
    FROM graph g
  UNION ALL
    SELECT g.id, g.link, g.data, sg.depth + 1,
      path || g.id,
      g.id = ANY(path)
    FROM graph g, search_graph sg
    WHERE g.id = sg.link AND NOT cycle
)
SELECT * FROM search_graph;