BGL - Adjusting edge weights via a ucs_visitor

From: aalness_at_[hidden]
Date: 2001-01-25 16:10:25

Hello,

I've started experimenting with the BGL visitor pattern and am scratching
my head. I am doing a dijkstra search on a graph and pass it an internal
property map of ints for the weight map (I call it edge_manual_weight_t).
I have a visitor who's event filter is on_examine_edge(). When the visitor gets
called it searches an external weight map and if it finds a value in that for
the edge it does a put(edge_manual_weights, e, i->second) (i->second being the
weight it looked up), otherwise it uses the weight in the default edge_weight
property map. When I set weights in the external map I get odd results.
Say my search yields 1, 2, 3, 4 under normal circumstances (no manual
weighting). If I increase the weight of the edge between 1 and 2 the
search will yield 1, 2, 3, 4, 4, 4, 4.  When I add edges I make sure I
put(edge_weights, e, <a positive integer>). My understanding is that the
search should yield a less-costly result or 1, 1, 1, 1, 2, 3, 4, this
udnerstanding may be flawed :)

Am I not getting something here or possily making a dumb mistake?

Here's my example code:

The search:

(namespace soni is #defined as std)

int
ProximityGraph::getDistance(BGP::ASN src, BGP::ASN dst, BGP::ASNList *path)
{
    Vertex root, leaf;
    ASNVertexMap::iterator i;

    if ((i = iMap.find(dst)) != iMap.end())
        root = i->second;
    else
        return -1;
    if ((i = iMap.find(src)) != iMap.end())
        leaf = i->second;
    else
        return -1;

    soni::vector<int> distance( num_vertices(iGraph) );
    soni::vector<default_color_type> color( num_vertices(iGraph) );
    soni::vector<Vertex> predecessor( num_vertices(iGraph) );

    predecessor[root] = root;
    dijkstra_shortest_paths(iGraph, root, &distance[0], get(edge_manual_weight_t(), iGraph),
                            &color[0], get(vertex_index, iGraph),
                           make_ucs_visitor(soni::make_pair(record_predecessors(&predecessor[0],
                           on_edge_relaxed()), WeightVisitor(iWeights))));

    if (color[leaf] != black_color)
        return -1;

    if (path) {
        property_map<Graph, vertex_name_t>::type asns = get(vertex_name, iGraph);
        Vertex parent = predecessor[leaf];

        path->push_back(src);
        for (int i = 0; i < distance[leaf]; i++) {
            path->push_back(get(asns, parent));
            parent = predecessor[parent];
        }
    }

    return distance[leaf];
}

The visitor:

In the .h for the visitor: typedef boost::on_examine_edge event_filter;

void
ProximityGraph::WeightVisitor::operator()(Edge e, Graph &g)
{
    property_map<Graph, edge_weight_t>::type givenWeights = get(edge_weight, g);
    property_map<Graph, edge_manual_weight_t>::type manualWeights
        = get(edge_manual_weight_t(), g);

    EdgeWeightMap::iterator i = weights.find(e);
    // if no manual weight, use BGP given weight
    if (i == weights.end())
        put(manualWeights, e, get(givenWeights, e));
    // Else use the manual weight in the map
    else
        put(manualWeights, e, i->second);

    return;
}

Thanks in advance!

-Andy

----------------------
Andrew Alness
Software Engineer
Sonicity, Inc.
aalness_at_[hidden]

"I want my two dollars." -kid on bike