2

私は、networkxのバージョンに基づいて、Pythonですべて単純なパスアルゴリズムに取り組んできました。現時点で私が行おうとしている唯一の変更は、O(n^2) 二重ループ内で実行せずに、すべてのノードのすべてのパスを取得することです。

メインのアルゴリズムはソートされていると思いますが、Python のリスト構造の可変性に慣れていないため、アルゴリズムがめちゃくちゃになっていると思います。

私はJavaで同様のプログラムを書いたので、テストグラフにいくつのパスがあるべきかを知っていますが、数字を合理的に近づけることさえできないようです.

def _all_simple_paths_graph(DG, cutoff):
    uniquePaths = []
    nlist = DG.nodes()
    for source in nlist:
        uniqueTreePaths = []
        if cutoff < 1:
            return
        visited = [source]
        stack = [iter(DG[source])]
        while stack:
            children = stack[-1]
            child = next(children, None)
            if child is None:
                stack.pop()
                visited.pop()
            elif len(visited) < cutoff:
                if child not in visited:
                    visited.append(child)
                    stack.append(iter(DG[child]))
                    if visited not in uniqueTreePaths:
                        yield visited
                        uniqueTreePaths.append(visited)
            else: #len(visited) == cutoff:
                if visited not in uniqueTreePaths:
                    yield visited + [child]
                    uniqueTreePaths.append(visited)
                stack.pop()
                visited.pop()
    uniquePaths.extend(uniqueTreePaths)

どこが間違っているのか誰か教えてもらえますか? 私はそれvisitedが可変であるべき場所とそうでない場所に関係していると信じています。ただし、基本的な機能が間違っている可能性もあります。私はPythonにかなり慣れていません!

4

1 に答える 1

1

どのような症状かは明記されていません。得られたものは間違っていますか、それともuniquePaths間違っていますか? 関数は正しいパスを生成するように見えますが、関数の最後にはuniquePaths必要なパスよりもはるかに少ないパスがあり、それらはすべて空です。

十分なパスがない理由はuniquePaths.extend(uniqueTreePaths)、正しいインデントにないためです。

あなたがここにいる問題は、それvisitedが可変リストであることです。Python では、すべてのリストが変更可能です。実際、それがこのアルゴリズムが機能する理由です。visitedパスであるスタックのように扱われます。visited複数回追加するuniqueTreePathsと、実際には同じオブジェクトが何度も追加されます。を変更するvisitedと、それらすべてが変更されます。

この問題を解決するには、リストのコピーを追加する必要があります。これはメモリ的にかなりコストがかかりますが、グラフ内のすべての一意のパスが必要だったので、すでにそのことを認識しているはずです。uniqueTreePaths.append(list(visited))から新しいlistオブジェクトを作成するために使用できますvisited。私は実際にそれからタプルを作成して、変更できないようにします: uniqueTreePaths.append(tuple(visited)).

于 2013-07-04T22:19:41.750 に答える