Построение алгоритма всех путей для DAG

Здесь есть реализация, основанная на алгоритме BFS. Я обозначу путь как последовательность вершин l = (v, v', v'', ...) и выполню над ним следующие две операции:

• extend(l, v): помещает вершину v в конец списка l;
• v = back(l): получает последнюю вершину в списке l.

FindPaths(G, v) {
  // The first path is, simply, the starting node.
  // It should be the first vertex in topological order.
  pending_paths = {(v)};
  while (pending_paths is not empty) {
    l = pending_paths.remove_first(); // pop the first pending path
    output(l); // output it (or save it in a list to be returned, if you prefer)
    v = back(l); // Get the last vertex of the path
    foreach(edge (v, v') in G) { // For each edge outgoing from v'...
      // extend l with v' and put into the list of paths to be examined.
      pending_paths.push_back(extend(l, v'));
    } 
  }
}

Вот простой рекурсивный алгоритм, выраженный в псевдокоде, чтобы избежать затуманивания проблемы большим количеством манипуляций со списками Java:

AllPaths(currentNode):
  result = EmptyList()
  foreach child in children(node):
    subpaths = AllPaths(child)
    foreach subpath in subpaths:
      Append(result, currentNode + subpath)
  return result

Вызов AllPaths на корневом узле даст вам то, что вам нужно, и вы можете улучшить время выполнения нетривиальных DAG, кэшируя результат AllPaths на каждом узле, поэтому вам нужно вычислить его только один раз, а не один раз для отдельного пути, который его включает. .

Итак, хотя псевдоним @akappa был хорошим началом, мне потребовалось некоторое время, чтобы понять, как заставить его работать, если кто-то еще наткнется на этот пост, вот как я это сделал:

public ArrayList<ArrayList<Node>> searchAll() {
    try {
        BufferedWriter out = new BufferedWriter(new FileWriter("output.txt"));
        //Gets Nodes from Hashmap and puts them into Queue
        for (Node key : paths.adjacencies.keySet()) {
            queue.addToQueue(new QueueItem(key.chemName, new ArrayList<Node>()));
        }
        while (queue.getSize() > 0) {
            QueueItem queueItem = queue.getFromQueue();
            Node node = paths.getNodeFromGraph(queueItem.getNodeId());
            if (node != null) {
                findRelationAll(node, queueItem, out);
            }
        }
        System.out.println("Cycle complete: Number of Edges: [" + resultHistoryAll.size() + "]");
        out.close();
    } catch (IOException e) {
    }
    return resultHistoryAll;

}

public void findRelationAll(Node node, QueueItem queueItem, BufferedWriter out) {
    if (!foundRelation) {
        StringTokenizer st = new StringTokenizer(paths.getAdjacentString(node), ",");
        while (st.hasMoreTokens()) {
            String child = st.nextToken();
            ArrayList<Node> history = new ArrayList<Node>();
            //Gets previous Nodes
            history.addAll(queueItem.getHistoryPath());
            //Makes sure path is unique
            if (history.contains(node)) {
                System.out.println("[" + counter2 + "]: Cyclic");
                counter2++;
                continue;
            }
            history.add(node);
            resultHistory = history;
            queue.addToQueue(new QueueItem(child, history));
            if (!(inList(resultHistory, resultHistoryAll))) {
                resultHistoryAll.add(resultHistory);
                try {
                    out.write("[" + counter + "]: " + resultHistory.toString());
                    out.newLine();
                    out.newLine();
                } catch (IOException e) {
                }
                System.out.println("[" + counter + "]: " + resultHistory.toString());
                counter++;
            } else {
                System.out.println("[" + counter3 + "]: InList");
                counter3++;
            }

        }
    }
}
//This checks path isn't in List already
public boolean inList(ArrayList<Node> resultHistory, ArrayList<ArrayList<Node>> allPaths) {
    for (int i = 0; i < allPaths.size(); i++) {
        if (allPaths.get(i).equals(resultHistory)) {
            return true;
        }
    }
    return false;
}

}

Приведенный выше код делает несколько дополнительных вещей, которые вам могут не понадобиться:

• Он записывает пути в текстовый файл в виде списка узлов + значение счетчика.
• Гарантирует, что путь не пересекает один и тот же узел дважды
• Следит за тем, чтобы в окончательном списке не было двух одинаковых путей (в обычных обстоятельствах это ненужная работа)

Объект QueueItem — это просто способ хранения ранее посещенных узлов. Это часть кода nemanja, который мой код был основан на.

Совет ему, akappa (за наиболее эффективный ответ) и jacobm (за поиск решения, подобного моему исходному коду, и объяснение его ограничений).

В случае, если кто-то действительно заинтересован в работе; В настоящее время я обрабатываю более 5 миллионов путей, из которых 60 000 являются уникальными путями между 900 химическими веществами. И это всего лишь 1,2,3 или 4 химических пути... Биология сложная штука.

РЕДАКТИРОВАТЬ и Предупреждение: ЕСЛИ кто-то обрабатывает огромные объемы данных, как я, Windows 7 - или, по крайней мере, моя машина - бросает дерьмо и закрывает программу после того, как ArrayList > 63 000 объектов, независимо от того, как вы упорядочиваете указатели. Решение, с которого я начал, было после 60 000 объектов, перезапуск списка при добавлении всего в CSV. Это привело к некоторым дубликатам между итерациями списка, и в конечном итоге это должно быть превзойдено моим завтрашним переходом на Linux!