On Mon, 4 Jan 2010, gast128 wrote:

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 think this is right. I put a few notes in it.

I use the graph from the BGL book as example (figure 13.3).

void TestgraphDijkstra() { typedef boost::adjacency_list Graph;

I know about your note about not using properties for everything possible, but using an old-style vertex_index property would make some things like color maps much easier. However, your way (an external property) works well also.

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);

An easier way is to just loop over the vertices and assign indices sequentially, making index assignment independent from the actual graph structure. You can use the (currently undocumented) header for that: { int i = 0; BGL_FORALL_VERTICES(v, graph, Graph) { boost::put(pmVertexIndex, v, i++); }

//note: color map not needed, because of index map?

That is correct. For the color map, the following three possibilities are tried (in order) by the algorithm: 1. An explicitly specified color map. 2. Creating a new color map using an explicitly specified vertex index map. 3. Creating a new color map using a named vertex_index property in the graph.

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; } }

-- Jeremiah Willcock