Мне дают рецепты, как создавать предметы. Рецепт имеет формат: {обрабатываемый элемент}: {список необходимых элементов}
. Прежде чем я смогу создать элемент x
, мне нужно знать, как создавать элементы, из которых он сделан. Поэтому я хочу выяснить, в каком порядке мне нужно изучать рецепты.
Для правильного ввода, вроде все работает:
// 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]
Проблема в том, что это более сложная задача. Время от времени у меня отсутствуют рецепты или они недействительны. Пример неверного ввода: {"F1: F2", "F2: F1"}
.
mp
содержит имя рецепта как ключ и элементы как значение, метки
являются уникальными mp
ключами, а результат
будет содержать ответ. Я ищу способ вернуть пустой
результат, если встречается бесконечный цикл.
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);
}
Проблема решена.
Для любого Google, который споткнулся об этом, это то, что я придумал с:
/** <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));
}
}