[BGL] dijkstra_shortest_paths with listS
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<boost::listS, boost::listS, boost::bidirectionalS, std::string> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor; typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor; typedef int Weight; typedef std::map<EdgeDescriptor, Weight> WeightMap; typedef std::map<VertexDescriptor, size_t> VertexIndexMap; typedef std::map<VertexDescriptor, Weight> DistanceMap; typedef std::map<VertexDescriptor, VertexDescriptor> 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; } }
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<boost::listS, boost::listS, boost::bidirectionalS, std::string> 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<EdgeDescriptor, Weight> WeightMap; typedef std::map<VertexDescriptor, size_t> VertexIndexMap; typedef std::map<VertexDescriptor, Weight> DistanceMap; typedef std::map<VertexDescriptor, VertexDescriptor> 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 <boost/graph/iteration_macros.hpp> 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
Thx for the answer. <snip>
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.
This is putting a property in the graph? A reason for me not to do that is that indices (as color maps) are just temporary properties; they are needed for graph algorithms to work. When vertices are added or removed, the index map should be adjusted as well. This management can be postponed if it is kept external and build the index map only just in time. So I like to put in the graph only data which conceptual belongs to the graph. The weight of an edge is probably also a candidate to put in the graph instead of keeping it external. That is the next challenge.
On Wed, 6 Jan 2010, gast128 wrote:
Thx for the answer.
<snip>
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.
This is putting a property in the graph? A reason for me not to do that is that indices (as color maps) are just temporary properties; they are needed for graph algorithms to work. When vertices are added or removed, the index map should be adjusted as well. This management can be postponed if it is kept external and build the index map only just in time.
OK. If you are mutating the graph often the approach you suggested makes sense. Vertex/edge indices are not really temporary, though, since they can be reused for different property maps (color, distance, ...) as long as the graph does not change. If you are only using them to satisfy algorithm requirements for particular temporary property maps, though, the index maps should be treated as temporary as well.
So I like to put in the graph only data which conceptual belongs to the graph. The weight of an edge is probably also a candidate to put in the graph instead of keeping it external. That is the next challenge.
What do you mean by that? What is the challenge you are having? -- Jeremiah Willcock
The weight of an edge is probably also a candidate to put in the graph instead of keeping it external. That is the next challenge.
What do you mean by that? What is the challenge you are having?
I haven't spend time on it yet, but I was thinking using bundled properties to put weight for edges, and somehow one must use an adaptor for the dijkstra_shortest_path algorithm.
On Thu, 7 Jan 2010, gast128 wrote:
The weight of an edge is probably also a candidate to put in the graph instead of keeping it external. That is the next challenge.
What do you mean by that? What is the challenge you are having?
I haven't spend time on it yet, but I was thinking using bundled properties to put weight for edges, and somehow one must use an adaptor for the dijkstra_shortest_path algorithm.
I don't think you need an adaptor. You can have the edge weight as a member in the property bundle and then use boost::get(&EdgeProps::weight, g) to get a property map for it. Is there something else you might need to adapt? -- Jeremiah Willcock
I don't think you need an adaptor. You can have the edge weight as a member in the property bundle and then use boost::get(&EdgeProps::weight, g) to get a property map for it. Is there something else you might need to adapt?
Yes this is what I call 'adapt'. If the edge type was only weight, e.g.: typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, std::string, int> Graph; then Dijkstra becomes something like: boost::dijkstra_shortest_paths(graph, vA, boost::weight_map(boost::get (boost::edge_bundle, graph)).vertex_index_map(pmVertexIndex).distance_map (pmDistance).predecessor_map(pmPredecessor));
participants (2)
-
gast128 -
Jeremiah Willcock