2

doubleBoost Graph Library を使用して、辺の重みとdouble頂点の重みを含む無向グラフを保存しています。私のコードのいくつかの場所で、最短経路を検索するためにダイクストラのアルゴリズムを適用する必要があります。これは、保存されているエッジの重みを自分の重みで一時的にオーバーライドすることを決定するまでは非常にうまく機能します (一時的にのみ、グラフの重みは変更されません)。私のコードは基本的に次のようになります。

  // Initial typedefs

  typedef boost::property<boost::edge_weight_t, double> edge_weight_t;
  typedef boost::property<boost::vertex_discover_time_t, double> vertex_weight_t;
  typedef boost::adjacency_list<boost::vecS,
                                boost::vecS,
                                boost::undirectedS,
                                vertex_weight_t,
                                edge_weight_t> graph_t;

 // In a function, where graph is a const reference of type graph_t

 std::vector<double> pathLengths( boost::num_vertices( graph ) );

 boost::property_map<graph_t, boost::edge_weight_t>::type weightMap;
 boost::graph_traits<graph_t>::edge_iterator e_it, e_it_end;
 for( boost::tie( e_it, e_it_end ) = boost::edges( graph );
      e_it != e_it_end;
      ++e_it )
 {
   weightMap[ *e_it ] = 1.0;
 }

 boost::dijkstra_shortest_paths( graph,
                                 boost::vertex( vertex, graph ),
                                 boost::distance_map( &pathLengths[0] ).weight_map( weightMap ) );

上記のコードでgraphはconst 参照ですが、グラフのエッジの重みは後で変更されます。私は何を間違っていますか？より具体的には、重み付きグラフのエッジの重みを一時的にオーバーライドするにはどうすればよいですか?

もちろん、現在のエッジ ウェイトを単純に保存し、自分のウェイトに置き換えて、後で元に戻すこともできます。しかし、私は自分に問題があると確信しており、この問題を無視したくありません。

4

1 に答える 1

4

私は同じ問題を抱えていたと思います-グラフ自体を永久に変更せずに、一時的に（検索アルゴリズムの特定の実行のために）エッジの重みを変更したかったのです。いくつか検索した後、これを見つけました。これにより、重みの生成に使用されるファンクターを登録できます。これは weight_map パラメーターとして使用されます。

http://www.boost.org/doc/libs/1_51_0/boost/property_map/function_property_map.hpp

于 2012-09-24T05:24:15.257 に答える