Cerchi un algoritmo in vb.net o C# ma non so come si chiami!

Question

Farò del mio meglio per spiegare cosa deve fare l'algoritmo:

C'è una classe 'Ricetta'. Ogni Ricetta può includere altre Ricette ma non può includere se stessa o qualsiasi altra Ricetta che la include.

Quindi, un semplice esempio è che abbiamo solo due Ricette Un & B.

Se A aggiunge B prima, poi in seguito B non può aggiungere un perché causerà un loop.

Un esempio più complicato è:

A, B, C

(1) Ricetta C aggiunge B
(2) Ricetta B aggiunge una
(3) ricetta A tenta di aggiungere C , ma non può a causa della relazione. C - B - A.

Posso farlo da solo, mi chiedevo solo se si trattasse di un algoritmo standard denominato e potrei prendere la soluzione ottimale.

Grazie

rilevamento

Answer 1

Topological ordering/ciclo? (L'algoritmo di smistamento topologico si arresta se viene rilevato un loop.)

Questo dovrebbe essere qualcosa di simile a quello che stai facendo.

Answer 2

Nel gergo tecnico/informatico la struttura è denominata directed graph. Si desidera un "Directed Acyclic Graph", ovvero uno senza cicli.

Per scoprire se ci sono cicli in un grafico, è possibile utilizzare un algoritmo chiamato Topological sorting. Cerca di riorganizzare un grafico in modo che se A si riferisce a B allora A si verifica sempre prima di B in ordine. Si ferma se il grafico ha cicli.

Se si desidera trovare tutti i cicli nel grafico (che è utile per i messaggi di errore), quindi this stackoverflow question and answer dà un sacco di aiuto.

Come sfondo:
Grafico = nulla con i nodi collegati da bordi (in caso i nodi sono ricette e riferimenti sono spigoli).
Diretto = i bordi hanno direzioni. Nel tuo caso questo è vero perché "A" si riferisce a "B", non "A" e "B" l'un l'altro.

Answer 3

Vedere cycle detection.

Answer 4

Date le vostre condizioni, penso che la struttura alla quale si andrà a finire sia DAG.

Quindi possiamo scoprire se l'aggiunta di un nuovo nodo crea un ciclo se sì, quindi non lo aggiungiamo altrimenti lo aggiungiamo.

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

    } 
} 

uscita:

True 
True 
False 
True