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 回答