1
현재 부스트 그래프 라이브러리로 작업 중입니다. 내 그래프는 사용자 정의 정점과 에지 속성으로 구성부스트 : 최단 경로에서 그래프 만들기
typedef boost::labeled_graph<boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, Vertex, Edge>, int> Graph; Graph g;
내가 가장 짧은 경로 (다 익스트라)을 계산하는 기능이 필요하여 사용자는 하나 또는 여러 개의 시작과 끝 노드를 선택해야합니다. 노드를 선택하고 모든 시작 노드와 끝 노드 사이의 최단 경로를 계산 한 후 새 그래프를 만들어야합니다. 결국 새로운 그래프는 모든 최단 경로에있는 모든 꼭지점/가장자리를 포함해야합니다.
내 생각이었다 :
1 : 나는
typedef std::vector< VertexDescriptor> Path;
2 종류
의 계산 된 최단 경로의 역 추적을 수행 정점이 이미 새로운 그래프에 포함되어 있다면 확인. (나는 그 중 하나를 처리하는 방법을 몰라), 그래서 만약 내가 새 그래프로 정점을 복사합니다.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;
}
그래프에서 꼭지점의 존재 여부를 어떻게 확인할 수 있습니까? 프로세스를 개선하거나 문제를 해결할 다른 아이디어가 있습니까?
감사 마이클