Как получить все пути от листа до root в специальном графе

Question

Я пытаюсь реализовать алгоритм в специальной структуре данных в виде графика. Моя цель - получить все пути от листа (целевого элемента) до root. Вот так выглядит график, как показано на рисунке ниже.

Answer 1

Нам нужно запомнить весь путь, который мы прошли, чтобы пройти по всем различным путям на графике, поэтому недостаточно только списка состояний, нам нужен список путей. Для каждого пути мы сделаем его длиннее на один, если у него будет один родитель, и если у него будет два или более, мы продублируем этот список и добавим к каждому из них родитель.

Ну, я не очень хорош в Java и я не могу запустить этот код, поэтому я не могу гарантировать, что он будет работать, но алгоритм в порядке.

public static List<ARGState> getAllErrorStatesReversed(ReachedSet reachedSet) {
  ARGState pIsStart =
      AbstractStates.extractStateByType(reachedSet.getFirstState(), ARGState.class);
  ARGState pEnd = targetStates.get(0);

  List<List<ARGState>> results = new ArrayList<>();
  List<List<ARGState>> paths = new ArrayList<>();

  paths.add(new ArrayList<ARGState>(pEnd));

  // This is assuming from each node there is a way to go to the start
  // Go on until all the paths got the the start
  while (!paths.empty()) {
    // Expand the last path on your list
    List<ARGState> curPath = paths.remove(paths.size() - 1);
    // If there is no more to expand - add this path and continue
    if (curPath.get(curPath.size() - 1) == pIsStart) {
      results.append(curPath);
      continue;
    }

    // Expand the path
    Iterator<ARGState> parents = curPath.get(curPath.size() - 1).getParents().iterator();
    // Add all parents
    while (parentElement.hasNext()) {
      ARGState parentElement = parents.next();
      List<ARGState> tmp = new ArrayList<ARGState>(List.copyOf(curPath));
      tmp.add(parentElement);
      paths.add(tmp);
    }
  }
  return results;
}

Надеюсь, вы понимаете, более чем добро пожаловать.
Удачи