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に関する他の質問は、やや専門的であるように思われるため、独自のアルゴリズムを構築しようとしました。

誰かがこれを実行するための優れた方法を提案するか、私が間違ったことを教えてもらえますか？アルゴリズムが正しければ、2つのノード間のすべてのパスを撤回するための最良の方法は何でしょうか？

編集：新しいパスが元の子ノードから作成されないことに気付きましたが、どうすれば作成できますか？

4

3 に答える 3

3

ここに、 BFSアルゴリズムに基づく実装があります。パスを一連の頂点として示し、l = (v, v', v'', ...)次の2つの操作を実行します。

  • 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 に答える
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の実行時間を改善できるため、それを含む個別のパスごとに1回ではなく、1回だけ計算する必要があります。

于 2013-02-15T03:27:48.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;
}

}

上記のコードは、あなたが望まないかもしれないいくつかの追加のことをします：

  • ノードのリスト+そのカウンター値としてテキストファイルへのパスウェイを書き込みます。
  • パスが同じノードを2回通過しないことを確認します
  • 最終リストで2つの経路が同じでないことを確認します（通常の状況では、これは不要な作業です）

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 に答える