Looking for an algorithm in vb.net or c# but I don't know it's name!

Question

I'll do my best to explain what the algorithm is supposed to do:

There's a class 'Recipe'. Each Recipe can include other Recipes but cannot include itself or any other Recipe that includes it.

So, a simple example is we have just two Recipes A & B.

If A adds B first, then later on B cannot add A because it will cause a loop.

A more complicated example is:

A,B,C

(1) Recipe C Adds B
(2) Recipe B Adds A
(3) Recipe A attempts to add C, but can't because of the relationship. C - B - A.

I can do this myself, I just wondered if this was a standard named algorithm and I could grab the optimal solution.

Thanks

Answer 1

In the Maths/Computer science jargon your structure is called a directed graph. You want a "Directed Acyclic Graph" - that is one with no cycles in it.

To find out if there are cycles in a graph you can use an algorithm called Topological sorting. It tries to rearrange a graph so that if A refers to B then A always occurs before B in order. It stops if the graph has cycles.

If you want to find all cycles in the graph (which is helpful for error messages) then this stackoverflow question and answer gives lots of help.

As background:
Graph = anything with nodes linked by edges (in your case nodes are recipes and references are edges).
Directed = the edges have directions. In your case this is true because 'A' refers to 'B', not 'A' and 'B' to each other.