2

一直在尝试构建一种通过 DAG 获取所有可能的唯一路径的方法。使用递归，因为它似乎最容易理解。结束了这个：

public class Brutus {
    //the previous nodes visited
    public ArrayList<Node> resultHistory = new ArrayList<Node>();
    //Directed Graph class, contains a HashMap [adjacencies]
    // that has keys for all nodes that contains all edges
    public AdjacencyList paths;
    //A list of all the pathways between nodes represented as a list of nodes
    public ArrayList<ArrayList<Node>> allPaths = new ArrayList<ArrayList<Node>>();

public Brutus(AdjacencyList paths) {
    this.paths = paths;
}

public ArrayList<ArrayList<Node>> findAll() {
    int counter = 1;
    for (Node key : paths.adjacencies.keySet()) {
        System.out.println("[" + counter + "]: " + key.toString());
        StringTokenizer st = new StringTokenizer(
            paths.getAdjacentString(key), ",");
        while (st.hasMoreTokens()) {
            String child = st.nextToken();
            if (paths.getNodeFromGraph(child) != null) {
                resultHistory = new ArrayList<Node>();
                resultHistory.add(key);
                findPath(child, resultHistory);
            }
        }
        counter++;
    }
    return allPaths;
}

public void findPath(String child, ArrayList<Node> resultHistory) {
    if (resultHistory.contains(paths.getNodeFromGraph(child))) {
        return;
    }
    resultHistory.add(paths.getNodeFromGraph(child));
    if(!(inList(resultHistory, allPaths))) {
        allPaths.add(resultHistory);
    }
    StringTokenizer st = new StringTokenizer(
        paths.getAdjacentString(paths.getNodeFromGraph(child)), ",");
    while (st.hasMoreTokens()) {
        child = st.nextToken();
        if (paths.getNodeFromGraph(child) != null) {
            findPath(child, resultHistory);
        }

    }
}

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;
}

问题是，我不认为它适用于所有路径，因为我无法在其中找到某些路径。虽然数据集是 900 个节点，但我找不到模式！Stack 上的其他问题似乎更专业一些，因此我尝试构建自己的算法！

谁能建议一种更好的方法来执行此操作，或者告诉我我做错了什么？如果算法正确，那么撤销两个节点之间所有路径的最佳方法是什么？

编辑：我现在意识到新路径不是从原始的子节点创建的，我将如何做到这一点？

4

3 回答 3

3

这是一个简单的递归算法，用伪代码表示，以避免使用大量 Java 列表操作来混淆问题：

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

调用AllPaths根节点将为您提供所需的内容，并且您可以通过AllPaths在每个节点上缓存结果来提高非平凡 DAG 的运行时间，因此您只需计算一次，而不是每个包含它的不同路径计算一次。

于 2013-02-15T03:27:48.003 回答
3

这里有一个基于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'));
    } 
  }
}
于 2013-02-15T14:05:05.003 回答
2

因此，虽然@akappa 的 Pseudo 是一个好的开始，但我花了一段时间才了解如何让它发挥作用，如果其他人看到这篇文章，我就是这样做的：

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（寻找像我的原始代码这样的解决方案，并解释它的局限性）。

以防有人真正对这项工作感兴趣；我目前正在处理超过 500 万条通路，其中 60,000 条是 900 种化学品之间的独特通路。这只是 1、2、3 或 4 种化学途径……生物学很复杂。

编辑和警告：如果有人像我一样处理大量数据，Windows 7 - 或者至少我的机器 - 会在 ArrayList > 63,000 个对象后抛出一个糟糕的配合并关闭程序，无论你如何安排指针。我开始的解决方案是在 60,000 个对象之后，重新启动列表，同时将所有内容添加到 CSV。这导致了列表迭代之间的一些重复，并且最终应该被我明天转向 linux 所超越！

于 2013-02-18T23:48:36.940 回答