私は、すべてのエッジをカバーするグラフ上のパスを取得しようとしています。 これは、奇数のノードが接続された2つの「終了」ポイントしか存在しないことを意味します。これらのエンドポイントは、1つの接続エッジを有するか、またはループの一部であり、3つの接続を有する。グラフ上のすべてのエッジのパスを見つける
:私はこの順序1-2-3-4-5(又は5-4-3-2-1)内のノードを通過する必要が下に単純なケースでそう
パス以下でより複雑な場合は、1-2-3-4-2(又は1-2-4-3-2)であろうにおいて:以下
2で、また有効グラフです。終点:1-2-4-3-2-5
は、私はこれを解決するためのアルゴリズムの名前を見つけることを試み、それが「中国のポストマン問題」だと思ったが、この私が期待される結果を提供しなかったhttps://github.com/rkistner/chinese-postman/blob/master/postman.pyのコードに基づいて実施してきました。
オイラーパスはほとんど必要になりますが、networkx implementationは閉ループ(ループ)ネットワークでのみ機能します。
私もHamiltonian Pathを見て、networkx algorithmを試しましたが、グラフの種類がサポートされていませんでした。
理想的には、これを実装するにはPythonとnetworkxを使いたいのですが、すでにライブラリの一部である単純な解決策があるかもしれませんが、見つけられないようです。
に交換しなければなりませんHamiltonian Pathはすべての頂点をカバーしているので、エッジをカバーする[Eulerian Path](https://en.wikipedia.org/wiki/Eulerian_path)をチェックするとよいでしょう。 GeeksForGeeksには[Python](http://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/)の実装例があるようです。 – niemmi
@niemmi - ありがとう!オイラーのtrai(サーキットではなく)が私が探している用語です。アルゴリズムを見て、それが既存のnetworkxメソッドを使用して簡略化できるかどうかを見ていきます。 – geographika
@niemmi適切なリンクを追加することで、それを答えにすることもできます。 –