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

Topological ordering/loop detection? (The algorithm of topological sorting stops if a loop is detected.)

This should be something close to what you are doing.

Answer 2

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.

Answer 3

Look at cycle detection.

Answer 4

You can find closure's of every object. it means that you find any accessible node for every node and if any of them does have itself then the graph does have a loop. It's name could anything like that: circular dependency detection or other mentioned by previous answers in more academic contexts

Answer 5

Given your conditions I think the structure you will end up with is DAG.

So we can find out if adding new node creates cycle if yes then we don't add it otherwise we add it.

class Foo
{
    public List<Foo> Reachables { get; set; }

    public Foo()
    {
        this.Reachables = new List<Foo>();
    }

    public bool Add(Foo other)
    {
        this.Reachables.Add(other); // add it 

        if(other.IsReachable(this)) // then see if it create a cycle
        {
            this.Reachables.Remove(other); // if yes remove it
            return false;
        }
        else
        {
            return true; // else keep it 
        }
    }

    private bool IsReachable(Foo goal) 
    {
        // BFS 

        Queue<Foo> nextQueue = new Queue<Foo>();
        List<Foo> traversed = new List<Foo>();

        bool found = false;

        nextQueue.Enqueue(this);

        while (!found) {

            Foo node = null;

            try { node = nextQueue.Dequeue(); }
            catch { break; }

            traversed.Add(node);

            if (node.Equals(goal)) {
                found = true;
                break;
            } 
            else 
            {
                foreach (Foo neighbor in node.Reachables)
                    if (!traversed.Contains(neighbor) && !nextQueue.Contains(neighbor)) 
                        nextQueue.Enqueue(neighbor);
            }
        }
        return found;
    }

}

class Program
{
    static void Main(string[] args)
    {
        Foo A = new Foo();
        Foo B = new Foo();
        Foo C = new Foo();

        Console.WriteLine(C.Add(B));
        Console.WriteLine(B.Add(A));
        Console.WriteLine(A.Add(C));
        Console.WriteLine(C.Add(A));

    }
}

Output:

True
True
False
True