views:

360

answers:

3

There are already a couple of questions on finding cycles, but I did not find a solution in SQL (MSSQL preferred).

The tables would be Node (NodeID INT) and Edge (EdgeID INT, NodeID1 INT, NodeID2 INT)

What would be a well-performing solution to find cycles in a directed graph?

+2  A: 

This is a great resource

DVK
+1  A: 

You can't do it in pure SQL. In your query there will always be limited number of JOINs. How big wouldn you make the amount of JOINs, you can always construct a cycle that has more edges in it, proving the query unsound.

So you should use some kind of loops, implemented either in some SQL dialects, or, for example, in perl or ruby.

Pavel Shved
SQL-2008 specifies "`WITH RECURSIVE`", so this is now possible without odd dialects. Of course, you first have to find a database that supports this part of the new SQL standard...
ephemient
A: 

The solution turned out quite simple and straightforward, but a bit longer:

First the list of all paths through the graph is generated, such that no path contains the same edge more than once.

From this information, we take the list of paths that start and end in the same node.

From this list of "final" edges we reconstruct all paths with cycles based on the calculation of the previous two steps.

I posted the complete solution in TSQL on my blog.

devio
Why not put it here too?
Nifle