Введение в проблему:
Мне даны рецепты изготовления предметов. Рецепт в формате: {element that is being crafter}: {list of elements, that is needed}. Прежде чем я смогу создать элемент 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 содержит имя рецепта в качестве ключа и элементы в качестве значения, labels являются уникальными mp ключами и result будет содержать ответ. Я ищу способ вернуть empty результат, если выполняется бесконечный цикл.
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, который наткнулся на это, вот что я придумал:
<code>/** <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]
*
*
* @param g
*
Направленный ациклический граф , где вершины хранятся как
* {@link java.util.HashMap HashMap} элементы.
*
* @return Линейное упорядочение входных узлов.
* Исключения @throws
* Брошенный, когда циклическая зависимость обнаружена, сообщение об ошибке также
* содержит элементы в цикле.
*
* /
public static ArrayList tSort (java.util.Map > g)
исключение
/ **
* @param L
* Ответ.
* @param S
* Не посещенные вершины листа.
* @param V
* Посещенные вершины.
* @param P
* Определенные вершины.
* @param n
* Текущий элемент.
* /
{
java.util.ArrayList L = новый ArrayList (g.size ());
java.util.Queue S = новый java.util.concurrent.LinkedBlockingDeque ();
java.util.HashSet V = новый java.util.HashSet (),
P = новый java.util.HashSet ();
P.addAll (g.keySet ());
Т н;
// Найти листовые узлы.
для (T t: P)
if (g.get (t) == null || g.get (t) .isEmpty ())
S.add (т);
// Посетить все конечные узлы. Результат построения из вершин, которые посещены
// в первый раз. Добавьте вершины в не посещенные вершины листа S, если
// он содержит текущий элемент n и все его значения посещены.
while (! S.isEmpty ()) {
if (V.add (n = S.poll ()))
L.add (п);
для (T t: g.keySet ())
if (g.get (t)! = null &&! g.get (t) .isEmpty () &&! V.contains (t)
&& V.containsAll (g.get (t)))
S.add (т);
}
// Вернуть результат.
если (L.containsAll (P))
возврат L;
// Бросить исключение.
StringBuilder sb = new StringBuilder (
"\ nНеверный DAG: обнаружена циклическая зависимость: \ n");
для (T t: P)
если (! L.contains (t))
sb.append (t) .append ("");
бросить новое исключение (sb.append ("\ n"). toString ());
}
/ **
* Метод удаляет самостоятельные зависимости и добавляет недостающие конечные узлы.
*
* @param g
*
Направленный ациклический граф , где вершины хранятся как
* {@link java.util.HashMap HashMap} элементы.
* /
public static void tSortFix (java.util.Map > g) {
java.util.ArrayList tmp;
java.util.HashSet P = новый java.util.HashSet ();
P.addAll (g.keySet ());
для (T t: P)
if (g.get (t)! = null ||! g.get (t) .isEmpty ()) {
(tmp = g.get (t)). remove (t);
для (T m: tmp)
если (! P. содержит (м))
g.put (м, новый ArrayList (0));
}
}