1

I have a data structure that is in the form of a list of nodes 

 [ID: 1, Name: "Node 1"],
 [ID: 2, Name: "Node 2"],
 [ID: 3, Name: "Node 3"],
 [ID: 4, Name: "Node 4"]

and edges, of the form 

 [StartNode: 1, EndNode: 2],
 [StartNode: 2, EndNode: 3]

and so on.

This data is stored in SQL and processed with C# and Angular. Nodes can be multiply connected, but the one thing that breaks the interface is a circular reference. I cannot have Node 1 -> Node 2 -> Node 3 -> Node 1.

Somehow a circular reference has crept into our database, but I can't figure out where it is. It's probably a 'small' circle, of three nodes that are connected together when they shouldn't, but I can't be sure.

How can I write some sort of recursive algorithm to find out where the circular reference is? Can I do this through a series of joins in SQL?

RamblerToning
  • 926
  • 2
  • 13
  • 28
  • 1
    Take a look at this [SO question](http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph) – Gordon Allocman Apr 01 '16 at 16:58
  • @GordonAllocman The "in SQL" bit is important. SQL is not designed to be a general purpose language, and sometimes it can be hard to figure out how to implement a given algorithm in SQL. – btilly Apr 01 '16 at 17:20
  • @btilly I wasn't trying to mark it as a duplicate or anything, just giving him a possible reference, as you mentioned is one way to do it in your answer – Gordon Allocman Apr 01 '16 at 17:23

1 Answers1

0

I assume you're using SQL server. In that case https://dba.stackexchange.com/questions/45158/how-to-write-a-query-which-finds-all-circular-references-when-a-table-references shows how to write a recursive query to find circular references inside of the database.

Alternately you would have to pull all of the data out of the database to use a standard graph algorithm.

Community
  • 1
  • 1
btilly
  • 43,296
  • 3
  • 59
  • 88