Re: [boost] BGL - Adjusting edge weights via a ucs_visitor

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-01-26 00:15:00

Hi Andy,

I'm not sure I completely understand what you are doing, but a first
glance one thing strikes be as odd. Are you changing the edge weights
*during* the search. This will invalidate the shortest-distance properties
of the search because inside of uniform_cost_search(), vertices are placed
in a priority queue based on distance (and thereby edge weight). If you
change edge weights, this priority queue will no longer be accurate.

On Thu, 25 Jan 2001 aalness_at_[hidden] wrote:

aalnes> 
aalnes> Hello,
aalnes> 
aalnes> I've started experimenting with the BGL visitor pattern and am scratching
aalnes> my head. I am doing a dijkstra search on a graph and pass it an internal
aalnes> property map of ints for the weight map (I call it edge_manual_weight_t).
aalnes> I have a visitor who's event filter is on_examine_edge(). When the visitor gets
aalnes> called it searches an external weight map and if it finds a value in that for
aalnes> the edge it does a put(edge_manual_weights, e, i->second) (i->second being the
aalnes> weight it looked up), otherwise it uses the weight in the default edge_weight
aalnes> property map. When I set weights in the external map I get odd results.
aalnes> Say my search yields 1, 2, 3, 4 under normal circumstances (no manual
aalnes> weighting). If I increase the weight of the edge between 1 and 2 the
aalnes> search will yield 1, 2, 3, 4, 4, 4, 4.  When I add edges I make sure I
aalnes> put(edge_weights, e, <a positive integer>). My understanding is that the
aalnes> search should yield a less-costly result or 1, 1, 1, 1, 2, 3, 4, this
aalnes> udnerstanding may be flawed :)
aalnes> 
aalnes> Am I not getting something here or possily making a dumb mistake?
aalnes> 
aalnes> Here's my example code:
aalnes> 
aalnes> The search:
aalnes> 
aalnes> (namespace soni is #defined as std)
aalnes> 
aalnes> int
aalnes> ProximityGraph::getDistance(BGP::ASN src, BGP::ASN dst, BGP::ASNList *path)
aalnes> {
aalnes>     Vertex root, leaf;
aalnes>     ASNVertexMap::iterator i;
aalnes> 
aalnes>     if ((i = iMap.find(dst)) != iMap.end())
aalnes>         root = i->second;
aalnes>     else
aalnes>         return -1;
aalnes>     if ((i = iMap.find(src)) != iMap.end())
aalnes>         leaf = i->second;
aalnes>     else
aalnes>         return -1;
aalnes> 
aalnes>     soni::vector<int> distance( num_vertices(iGraph) );
aalnes>     soni::vector<default_color_type> color( num_vertices(iGraph) );
aalnes>     soni::vector<Vertex> predecessor( num_vertices(iGraph) );
aalnes> 
aalnes>     predecessor[root] = root;
aalnes>     dijkstra_shortest_paths(iGraph, root, &distance[0], get(edge_manual_weight_t(), iGraph),
aalnes>                             &color[0], get(vertex_index, iGraph),
aalnes> 			   make_ucs_visitor(soni::make_pair(record_predecessors(&predecessor[0],
aalnes>                            on_edge_relaxed()), WeightVisitor(iWeights))));
aalnes> 
aalnes>     if (color[leaf] != black_color)
aalnes>         return -1;
aalnes> 
aalnes>     if (path) {
aalnes>         property_map<Graph, vertex_name_t>::type asns = get(vertex_name, iGraph);
aalnes>         Vertex parent = predecessor[leaf];
aalnes> 
aalnes>         path->push_back(src);
aalnes>         for (int i = 0; i < distance[leaf]; i++) {
aalnes>             path->push_back(get(asns, parent));
aalnes>             parent = predecessor[parent];
aalnes>         }
aalnes>     }
aalnes> 
aalnes>     return distance[leaf];
aalnes> }
aalnes> 
aalnes> The visitor:
aalnes> 
aalnes> In the .h for the visitor: typedef boost::on_examine_edge event_filter;
aalnes> 
aalnes> void
aalnes> ProximityGraph::WeightVisitor::operator()(Edge e, Graph &g)
aalnes> {
aalnes>     property_map<Graph, edge_weight_t>::type givenWeights = get(edge_weight, g);
aalnes>     property_map<Graph, edge_manual_weight_t>::type manualWeights
aalnes>         = get(edge_manual_weight_t(), g);
aalnes> 
aalnes>     EdgeWeightMap::iterator i = weights.find(e);
aalnes>     // if no manual weight, use BGP given weight
aalnes>     if (i == weights.end())
aalnes>         put(manualWeights, e, get(givenWeights, e));
aalnes>     // Else use the manual weight in the map
aalnes>     else
aalnes>         put(manualWeights, e, i->second);
aalnes> 
aalnes>     return;
aalnes> }
aalnes> 
aalnes> Thanks in advance!
aalnes> 
aalnes> -Andy
aalnes> 
aalnes> ----------------------
aalnes> Andrew Alness
aalnes> Software Engineer
aalnes> Sonicity, Inc.
aalnes> aalness_at_[hidden]
aalnes> 
aalnes> "I want my two dollars." -kid on bike
aalnes> 
aalnes> 
aalnes> 
aalnes> 
aalnes> 
aalnes> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------