Looking for an algorithm in vb.net or C #, but I don’t know its name!

Question

I will do my best to explain what the algorithm should do:

There is a class 'Recipe'. Each Recipe may include other Recipes, but may not include itself or any other Recipe that includes it.

So, a simple example: we have only two recipes A and B.

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

More complex example:

A, B, C

(1) Recipe C adds B
(2) Recipe B adds A (3) Recipe A tries to add C, but cannot because of the relationship. C - B - A.

I can do it myself, I'm just wondering if this was a standard algorithm, and I could find the optimal solution.

thank

Answer 1

. " Directed Acyclic Graph" - , .

, , . , A B, A B . , .

( ), fooobar.com/questions/4423/... .

:
= , ( , - ).
= . , "A" "B", "A" "B" .

Answer 2

/ ? ( , .)

- , .

Answer 3

, , , , - DAG.

, , node , , , .

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));

    }
}

:

True
True
False
True

Answer 4

.