How to avoid infinite loop while creating a scheduler

Question

Intro to problem:

I am given recipes how to craft items. Recipe is in format : {element that is being crafter}: {list of elements, that is needed}. Before I can craft element x, I need to know how to craft elements it's made of. So I want to find in what order do I have to learn recipes.

For valid input, like following everything works:

// Input:
{ 
    "F1: F2 F3 F4", "F5: F6 F4", "F6: F7 F8 F4", "F2: F3 F8 F4", "F8: F4",
    "F9: F4", "F7: F4", "F10: F7 F4", "F11: F4", "F4:", "F3: F6"
}
// Output:
[F4, F7, F8, F6, F3, F2, F1, F5, F9, F10, F11]

The problem is, that task is more complex. Time to time I have some recipes missing or thy are invalid. Example of invalid input: { "F1: F2", "F2: F1" }.

Code example:

mp contains recipe name as key and elements as value, labels are unique mp keys and result will contain answer. I'm looking for a way to return empty result if infinite loop is met.

private void getArray(HashMap<String, ArrayList<String>> mp,
        ArrayList<String> result, ArrayList<String> labels) {
    for (String a : labels) {
        if (mp.get(a) != null)
            for (String label : mp.get(a))
                getArray(mp, result, label);
        if (!result.contains(a))
            result.add(a);
    }
}

private void getArray(HashMap<String, ArrayList<String>> mp,
        ArrayList<String> result, String label) {
    if (result.contains(label))
        return;
    if (mp.get(label) == null) {
        result.add(label);
        return;
    }
    for (String l : mp.get(label))
        getArray(mp, result, l);
    if (!result.contains(label))
        result.add(label);
}

Edit

Problem solved.

For any Google's that stumble up this, this is what I came up with:

/** <p>
 * <b>Topological sort</b> solves a problem of - finding a linear ordering
 * of the vertices of <i>V</i> such that for each edge <i>(i, j) ∈ E</i>,
 * vertex <i>i</i> is to the left of vertex <i>j</i>. (Skiena 2008, p. 481)
 * </p>
 * 
 * <p>
 * Method is derived from of <a
 * href="http://en.wikipedia.org/wiki/Topological_sort#Algorithms" > Kahn's
 * pseudo code</a> and traverses over vertices as they are returned by input
 * map. Leaf nodes can have null or empty values. This method assumes, that
 * input is valid DAG, so if cyclic dependency is detected, error is thrown.
 * tSortFix is a fix to remove self dependencies and add missing leaf nodes.
 * </p>
 * 
 * <pre>
 * // For input with elements:
 * { F1=[F2, F3, F4], F10=[F7, F4], F11=[F4], F2=[F3, F8, F4], F3=[F6], 
 *   F4=null, F5=[F6, F4], F6=[F7, F8, F4], F7=[F4], F8=[F4], F9=[F4]}
 *   
 * // Output based on input map type: 
 * HashMap: [F4, F11, F8, F9, F7, F10, F6, F5, F3, F2, F1]
 * TreeMap: [F4, F11, F7, F8, F9, F10, F6, F3, F5, F2, F1]
 * </pre>
 * 
 * @param g
 *            <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph"
 *            > Directed Acyclic Graph</a>, where vertices are stored as
 *            {@link java.util.HashMap HashMap} elements.
 * 
 * @return Linear ordering of input nodes.
 * @throws Exception
 *             Thrown when cyclic dependency is detected, error message also
 *             contains elements in cycle.
 * 
 */
public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g)
        throws Exception
/**
 * @param L
 *            Answer.
 * @param S
 *            Not visited leaf vertices.
 * @param V
 *            Visited vertices.
 * @param P
 *            Defined vertices.
 * @param n
 *            Current element.
 */
{
    java.util.ArrayList<T> L = new ArrayList<T>(g.size());
    java.util.Queue<T> S = new java.util.concurrent.LinkedBlockingDeque<T>();
    java.util.HashSet<T> V = new java.util.HashSet<T>(), 
    P = new java.util.HashSet<T>();
    P.addAll(g.keySet());
    T n;

    // Find leaf nodes.
    for (T t : P)
        if (g.get(t) == null || g.get(t).isEmpty())
            S.add(t);

    // Visit all leaf nodes. Build result from vertices, that are visited
    // for the first time. Add vertices to not visited leaf vertices S, if
    // it contains current element n an all of it's values are visited.
    while (!S.isEmpty()) {
        if (V.add(n = S.poll()))
            L.add(n);
        for (T t : g.keySet())
            if (g.get(t) != null && !g.get(t).isEmpty() && !V.contains(t)
                    && V.containsAll(g.get(t)))
                S.add(t);
    }

    // Return result.
    if (L.containsAll(P))
        return L;

    // Throw exception.
    StringBuilder sb = new StringBuilder(
            "\nInvalid DAG: a cyclic dependency detected :\n");
    for (T t : P)
        if (!L.contains(t))
            sb.append(t).append(" ");
    throw new Exception(sb.append("\n").toString());
}

/**
 * Method removes self dependencies and adds missing leaf nodes.
 * 
 * @param g
 *            <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph"
 *            > Directed Acyclic Graph</a>, where vertices are stored as
 *            {@link java.util.HashMap HashMap} elements.
 */
public static <T> void tSortFix(java.util.Map<T, ArrayList<T>> g) {
    java.util.ArrayList<T> tmp;
    java.util.HashSet<T> P = new java.util.HashSet<T>();
    P.addAll(g.keySet());

    for (T t : P)
        if (g.get(t) != null || !g.get(t).isEmpty()) {
            (tmp = g.get(t)).remove(t);
            for (T m : tmp)
                if (!P.contains(m))
                    g.put(m, new ArrayList<T>(0));
        }
}

Answer 1

The problem you are solving is known as topological sort. Kahn's algorithm solves the problem while also detecting invalid input (that is, containing cycles).

Answer 2

The quick way to do this is to remember the set of items that you've already seen, and simply throw an exception if you're about to work out the requirements for an item already in that list. This will definitely indicate some kind of circularity which we can probably assume is a bad thing.

A more advanced solution, if loops in the object graph are allowable, would be to not just store the items, but also map them to their solution. Since you're in the process of calculating the solutions, this would perhaps need to be a Future that you pop in the map to indicate that the evaluation may not be complete yet. Then you can add the "solution placeholders" in the map as soon as you visit a given item. Consequently infinite loops work fine (looking at your trivial invalid case):

1. Visit F1. Put a Future for this in the map. Recurse to work out F2.
2. Visit F2. Put a Future for this in the map. See that F1 has already been "solved", and record the concrete solution for F2 as simply creating an F1.

This of course represents a loop in the solution's object model, but that's actually a legitimate representation of the input. If you were displaying this graphically, perhaps as a tree that gets expanded one level at a time, this would render appropriately too ("How do I create an F1? You need to make an F2. How do I create that? You need to make an F1", and so on for as many levels as the user expanded the tree).

(Note that while this sounds silly it can actually reflect some valid scenarios; e.g. in Fallout: New Vegas, several crafting recipes convert between different energy ammo types. Thus to make a Microfusion Cell you need three Small Energy Cells. And to make three Small Energy Cells you need a Microfusion Cell. This would create a loop in the graph, but in this case is actually valid input. I'm just pointing this out in case you're assuming that loops are always wrong input.)

If it is possible for a recipe to have alternatives, perhaps somewhere between these two approaches is the best bet. Follow all of the alternative paths, but if you get into an infinite loop, stop following that one and go with the others.