Finding loops in directed graphs using SQL

Question

There are already several questions on finding loops, but I have not found a solution in SQL (preferably MSSQL).

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

What will be the efficient loop search performance in a directed graph?

Answer 1

The solution turned out to be quite simple and understandable, but a little longer:

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

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

From this list of “final” edges, we restore all paths with loops based on the calculation of the previous two steps.

I posted the complete solution in TSQL on my blog.

Answer 2

This is a great resource: Kendall Willes' SQL Graphics Algorithms

Answer 3

You cannot do this in pure SQL. Your request will always have a limited number of JOINs. How big you make the number of JOINs, you can always build a loop in which there are more edges, which makes the request unreasonable.

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