In my game, I have an extensive production graph that defines what the player can produce in-game. The edges are processes, the nodes are entity types. A process can have inputs, outputs and require tools, all of which are entity types.

I would like for the player to see next to each entity type, whether it is attainable. To do this, I am using a naive approach with a depth first search for each entity type. The problem is that this won't work when there are loops in the production graph.

Which other algorithm is useful here? Note that I am disregarding the amounts needed, I am just looking to give a hint about what is possible to attain, so any item that is present in greater than 0 amounts will be attainable, and fulfill the next process step.

Ok, then I will take another look at my design.

I have a collection where I store the attainable results for each node. What about nodes that are currently being evaluated? When the search reaches such nodes (again) what should it do? Returning "not attainable" would give the wrong result for the starting node.

Great, I'll try that.

Here is some pseudocode for my current approach which does not work with loops. I would appreciate any help in finishing the code.

ComputeAll()
{
   foreach(EntityType entityType in AllEntityTypes)
   {
       AttainabilityInfo info = GetAttainability(entityType);
       Attainables[entityType] = info; // store it
   }
}


AttainableInfo GetAttainability(EntityType entityType)
{
   AttainableInfo info = Attainables[entityType];
   if (info != null)
   {
      // already computed
      return info;
   }

   if (IsOwned(entityType))
   {
      // we own this
      return new AttainableInfo(true);
   }

   var processes = GetProcessesYieldingOutput(entityType);
             
   foreach(process in processes)
   {
       missingInputs = null;
       missingTools = null;

       foreach (EntityType input in process.InputsByType)
       {
           AttainableInfo inputIsAttainable = GetAttainability(input);

           if (inputIsAttainable.Value == false)
           {
               missingInputs.Add(tool);
           }
       }

       foreach (EntityType tool in process.Tools)
       {
           AttainableInfo toolIsAttainable = GetAttainability(tool);


           if (toolIsAttainable.Value == false)
           {
               missingTools.Add(tool);
           }
        }

        if (missingInputs == null && missingTools == null)
        {
             // we can produce this                       
             return new AttainableInfo(maxDistance);
        }
    }

    return new AttainableInfo(false, missingInputs, missingTools); // we cannot produce this

}   

Any time your traversal moves to an entity where you didn't change the attainability flag of the output(s), stop that branch of the traversal.

Create a queue

Foreach entity you own
  Mark it attainable and put it in the queue

While the queue is not empty
  Dequeue an entity
  Foreach process using this entity as an input
    Foreach output in that process
      If the output entity is not already marked attainable         <- key step to avoid looping forever.
        Mark it attainable
        Foreach process using this output as an input
          Put it in the queue

Store the attainable set

Will it still work if a process may require multiple inputs...? You're not checking the tools either so marking it attainable seems premature after checking just one input.