问题描述:

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.

网友答案:

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;
相关阅读:
Top