Hello all,
BGL supports a lot of graph algorithms, and lots of stuff get default filled
in when using vecS as container type of vertices. However things become pretty
ugly when not using this container. Below I used a listS for both edges and
vertices. Maybe it can help other people (and maybe somebody can cross check
me). Note that some constructs could be bundled, but for clearity I explicitly
wrote all things out.
I use the graph from the BGL book as example (figure 13.3).
void TestgraphDijkstra()
{
typedef boost::adjacency_list Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;
typedef int Weight;
typedef std::map WeightMap;
typedef std::map VertexIndexMap;
typedef std::map DistanceMap;
typedef std::map PredecessorMap;
Graph graph;
WeightMap mapWeigth;
VertexIndexMap mapVertexIndex;
DistanceMap mapDistance;
PredecessorMap mapPredecessor;
boost::associative_property_map<WeightMap> pmWeigth(mapWeigth);
boost::associative_property_map<VertexIndexMap> pmVertexIndex
(mapVertexIndex);
boost::associative_property_map<DistanceMap> pmDistance(mapDistance);
boost::associative_property_map<PredecessorMap> pmPredecessor
(mapPredecessor);
//build a graph according to figure 13.3
//add vertices
const VertexDescriptor vA = boost::add_vertex(graph);
const VertexDescriptor vB = boost::add_vertex(graph);
const VertexDescriptor vC = boost::add_vertex(graph);
const VertexDescriptor vD = boost::add_vertex(graph);
const VertexDescriptor vE = boost::add_vertex(graph);
//set vertex names
graph[vA] = "A";
graph[vB] = "B";
graph[vC] = "C";
graph[vD] = "D";
graph[vE] = "E";
//add edges
const EdgeDescriptor eAC = boost::add_edge(vA, vC, graph).first;
const EdgeDescriptor eBB = boost::add_edge(vB, vB, graph).first;
const EdgeDescriptor eBD = boost::add_edge(vB, vD, graph).first;
const EdgeDescriptor eBE = boost::add_edge(vB, vE, graph).first;
const EdgeDescriptor eCB = boost::add_edge(vC, vB, graph).first;
const EdgeDescriptor eCD = boost::add_edge(vC, vD, graph).first;
const EdgeDescriptor eDE = boost::add_edge(vD, vE, graph).first;
const EdgeDescriptor eEB = boost::add_edge(vE, vB, graph).first;
const EdgeDescriptor eEA = boost::add_edge(vE, vA, graph).first;
//set edge weights
boost::put(pmWeigth, eAC, 1);
boost::put(pmWeigth, eBB, 2);
boost::put(pmWeigth, eBD, 1);
boost::put(pmWeigth, eBE, 2);
boost::put(pmWeigth, eCB, 7);
boost::put(pmWeigth, eCD, 3);
boost::put(pmWeigth, eDE, 1);
boost::put(pmWeigth, eEB, 1);
boost::put(pmWeigth, eEA, 1);
//build index map
boost::put(pmVertexIndex, vA, 0);
boost::put(pmVertexIndex, vB, 1);
boost::put(pmVertexIndex, vC, 2);
boost::put(pmVertexIndex, vD, 3);
boost::put(pmVertexIndex, vE, 4);
//note: color map not needed, because of index map?
boost::dijkstra_shortest_paths(graph, vA, boost::weight_map
(pmWeigth).vertex_index_map(pmVertexIndex).distance_map
(pmDistance).predecessor_map(pmPredecessor));
for (DistanceMap::const_iterator itDist = mapDistance.begin(); itDist !=
mapDistance.end(); ++itDist)
{
//dump
const VertexDescriptor v = itDist->first;
const VertexDescriptor vPrev = mapPredecessor[v];
std::cout << "Distance(" << graph[v] << ") = " << itDist->second
<< ", "
<< "Parent(" << graph[v] << ") = " << graph[vPrev]
<< std::endl;
}
}
