1
現在、私はブーストグラフライブラリを使っています。 私のグラフは、カスタム頂点と辺のプロパティで構成されていますブースト：最短パスからグラフを作成
typedef boost::labeled_graph<boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, Vertex, Edge>, int> Graph; Graph g;
私は最短経路（ダイクストラ）を算出する機能を必要とすることにより、ユーザは、1つまたは複数の開始と終了ノードを選択する必要があります。ノードを選択し、すべての開始ノードと終了ノードの間の最短パスを計算した後、新しいグラフを作成する必要があります。最後に、新しいグラフには、すべての最短経路上にあるすべての頂点/辺が含まれている必要があります。
私の考えでした：
1：私はタイプ
typedef std::vector< VertexDescriptor> Path;
2の計算最短パスのバックトラッキングを実行します。頂点はすでに新しいグラフに含まれている場合、私は確認してください。 （私はその1つを処理する方法は分かりません）、もし私が新しいグラフに頂点をコピーするならば。
3：新しいグラフにエッジが既に含まれているかどうかをチェックします。エッジが新しいグラフにコピーされているかどうかを確認します。
Graph graphPaths;
Path::reverse_iterator rit;
VertexDescriptor lastNode = *path.rbegin();
for (rit = path.rbegin(); rit != path.rend(); ++rit) {
// Vertex v =
// check if vertices already exist in new GraphPath
if (graphPaths[indexMap[*rit]] == NULL) {
Vertex v = g[indexMap[*rit]];
VertexDescriptor vd = boost::add_vertex(indexMap[*rit], graphPaths);
graphPaths[indexMap[*rit]] = v;
}
// check if edge is already included in new Graph
if (!boost::edge(lastNode, *rit, graphPaths).second) {
Graph::edge_descriptor ep = boost::edge(lastNode, *rit, g).first;
boost::add_edge_by_label(indexMap[lastNode], indexMap[*rit], g[ep],
graphPaths);
}
}
lastNode = *rit;
}
グラフ内の頂点の存在を確認する方法を教えてください。プロセスを改善したり、問題を解決するための他のアイデアがありますか？
おかげ マイケル