0

私は、一度に 1 つの頂点を実行するのではなく、OpenMP を使用して複数のスレッド間で計算を分割し、特定のグラフ内のすべての頂点の最短パスを計算する小さなプログラムに取り組んできました。私の現在の実装は機能していますが、グラフがプログラムにハードコーディングされないように、「頂点1頂点2ウェイト」形式のファイルからグラフデータを読み取ることができるようにしたいと考えています。

ソースはこちら: http://pastebin.com/bkR7QysB

次のようにコンパイルされます。

g++ -fopenmp GraphTest.cpp WeightedGraph.cpp -o dijkstra

次のデータを入力として使用します。

foo derp 50
narf balls 30
foo balls 20
balls derp 60
derp narf 40
derp cox 30
foo narf 50
narf pie 99
cox pie 15
cox narf 10

私の出力は次のとおりです。

Enter filename: lol.out
Printing all edges currently in graph: 
(foo, derp) : cost 50
(narf, balls) : cost 30
(foo, balls) : cost 20
(balls, derp) : cost 60
(derp, narf) : cost 40
(derp, cox) : cost 30
(foo, narf) : cost 50
(narf, pie) : cost 99
(cox, pie) : cost 15
(cox, narf) : cost 10

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost.
(balls, balls : cost 0)
(balls, derp : cost 60)

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost.
(cox, cox : cost 0)
(cox, narf : cost 10)

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost.
(derp, derp : cost 0)
(derp, cox : cost 30)

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost.
(foo, foo : cost 0)
(foo, narf : cost 50)

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost.
(narf, narf : cost 0)
(narf, cox : cost 10)

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost.
(pie, pie : cost 0)
(pie, cox : cost 15)

これは明らかに間違っています。頂点からグラフ内の他のすべての頂点への最短パスを出力することになっていますが、ここでは、それ自体への最短パス (常に 0) と、直接隣接する頂点の 1 つだけへのパスのみを出力しています。隣人。グラフをまったくトラバースしていません。ただし、最も奇妙な部分は、GraphTest.cpp の末尾近くにある巨大なブロックのコメントを外し、ファイル処理コードをコメント アウトして、グラフ データがプログラムにハードコードされるようにすると、すべて正常に動作することです。

Printing all edges currently in graph: 
(foo, derp) : cost 50
(narf, balls) : cost 30
(foo, balls) : cost 20
(balls, derp) : cost 60
(derp, narf) : cost 40
(derp, cox) : cost 30
(foo, narf) : cost 50
(narf, pie) : cost 99
(cox, pie) : cost 15
(cox, narf) : cost 10

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost.
(balls, balls : cost 0)
(balls, foo : cost 20)
(balls, narf : cost 30)
(balls, cox : cost 40)
(balls, pie : cost 55)
(balls, derp : cost 60)

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost.
(cox, cox : cost 0)
(cox, narf : cost 10)
(cox, pie : cost 15)
(cox, derp : cost 30)
(cox, balls : cost 40)
(cox, foo : cost 60)

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost.
(derp, derp : cost 0)
(derp, cox : cost 30)
(derp, narf : cost 40)
(derp, pie : cost 45)
(derp, foo : cost 50)
(derp, balls : cost 60)

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost.
(foo, foo : cost 0)
(foo, balls : cost 20)
(foo, derp : cost 50)
(foo, narf : cost 50)
(foo, cox : cost 60)
(foo, pie : cost 75)

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost.
(narf, narf : cost 0)
(narf, cox : cost 10)
(narf, pie : cost 25)
(narf, balls : cost 30)
(narf, derp : cost 40)
(narf, foo : cost 50)

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost.
(pie, pie : cost 0)
(pie, cox : cost 15)
(pie, narf : cost 25)
(pie, derp : cost 45)
(pie, balls : cost 55)
(pie, foo : cost 75)

正直なところ、ここで何が起こっているのかわかりません。私が考えることができる唯一のことは、どこかがあまりにも早く範囲外になり、グラフオブジェクトの動作が奇妙になるということですが、それが本当なら、両方の出力が間違っているはずです...私より賢い人が実行できることを願っていますこれで、何が悪かったのかを理解するのに役立ちます。

4

1 に答える 1

0

コードを読んでいるときに見たいくつかの問題について言及します。

  1. エッジ マップはペアでインデックス付けされていることに注意してください。したがって、ここで実装したものは有向グラフでなければなりません。( vi, vj ) でインデックスを付けているため、エッジ ( v0, v1 ) と ( v1, v0 ) は区別され、異なる値になります (存在しない場合もあります)。エッジの検索が順序に依存しないように、エッジを管理する方法を考える必要があります。

  2. 標準テンプレート ライブラリに大きく依存するコードで char*s を使用している理由がわかりません。ストリングスはあなたの友達です！

さて、問題は頂点を再挿入していることだと思います。コードでは、追加する頂点がグラフにまだ存在しないことを確認するチェックを行いません。代わりに、新しい頂点を割り当てて頂点マップに配置するだけです。その名前の頂点が既に存在する場合、マップ内で上書きされ、そのデータへの唯一の参照が失われます。したがって、置き換えられた頂点が削除されないため、メモリ リークが発生します。

したがって、入力ファイルが次の場合:

narf ボール 50 foo narf 10

コードは、両方の行に narf 頂点を作成して追加します。これは、これまでに確認した唯一の違いですが、重要であり、メモリ リークだけでなく、かなりコストのかかるバグを引き起こします。

余談ですが、エッジ オブジェクトを持つことに必ずしも価値があるとは思いません。各 vertices _neighbors リストにエッジのすべての情報を簡単に保存できます。そのリストをマップにし、隣接する頂点の名前をキーにし、コストを値にします。

_neighborMap[ v0.name() ] = コスト;

エッジ タイプを使用すると、多くの不要な参照と複雑さが追加されるようです。ちょっとした考え...

あなたのコードをさらに見ていくと、実際には Vertex オブジェクトや Edge オブジェクトを削除していないことがわかります。動的メモリ割り当てを使用したくない場合は、Graph でポインタの代わりに Vertex のインスタンスを使用するようにします。これらは非常に小さなオブジェクトであるため、次のような単純な操作を行うだけで、コピーインによる追加の命令に関して多くの費用がかかることはありません。

_internalVertexMap[ "v0" ] = Vertex( "v0" );
于 2011-05-11T01:02:43.060 に答える