I got stuck on cycles to get the path of a sql directed graph

I've got a table where I keep couples of numbers, to indicate arcs of a directed Graph, where every node is identified by an integer value:

CREATE TABLE graph (    
n2 INTEGER NOT NULL,    
n1 INTEGER NOT NULL,
PRIMARY KEY (id_area_possesso, id_area_utente)
CONSTRAINT CK CHECK (n1 <> n2)
)

Where n1 points n2, and so on; so, for instance, when I will insert

INSERT INTO graph VALUES (3,4)
INSERT INTO graph VALUES (9,3)
INSERT INTO graph VALUES (12,9)

I will obtain this graph: 4->3->9->12.

I use this query to get the list of the arcs (the path) starting from a node:

WITH tmp (n2,n1) AS (
SELECT G.n2 , G.n1 
FROM Graph AS G
WHERE n1=3
UNION ALL

SELECT n2 , n1
FROM Graph AS G JOIN tmp ON (G.n1=tmp.N2)  

)

SELECT * FROM tmp 
GO

As result of this query I would obtain the arcs:

• (9,3)
• (12,9)

This query works fine, but when there are cycles on the graph:

INSERT INTO graph VALUES (0,1)
INSERT INTO graph VALUES (2,0)
INSERT I开发者_开发技巧NTO graph VALUES (1,2)

it goes on an infinite loop, and I get the error message:

The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

I can't use or create other tables in my project, so I will have to do everything on temporary ones. How can I fix my query in order to get the right path, avoiding to get stuck in cycles?

You can build a string with id's as you go and test if the id already is in.

;WITH tmp (n2,n1,nx) AS
(
  SELECT G.n2, 
         G.n1,
         cast('/'+cast(G.n1 as varchar(10))+'/' as varchar(max))
  FROM Graph AS G
  WHERE n1=1
  UNION ALL
  SELECT G.n2, 
         G.n1,
         tmp.nx+cast(G.n1 as varchar(10)) +'/'
  FROM Graph AS G 
    JOIN tmp 
      ON (G.n1=tmp.N2) and
         tmp.nx not like '%/'+cast(G.n1 as varchar(10))+'/%' 
)

SELECT * FROM tmp 

you will need to store each path/arc in a temp table.

then check that temp table on each pass to see if the path has already been saved before proceeding.