From: Greg Link (link_at_[hidden])
Date: 2006-02-14 15:57:00
In my first use of the boost library, I'm using the BGL's
dijkstra_shortest_paths algorithm to try and (obviously) find the
shortest path between two points. I am then iterating along the
shortest path to a given node to find the total path weight along
that path. I compare this value to the path weight along a manhattan
path, and find that the manhattan path is shorter. Rather than claim
this is a problem with boost (yet), I'm at first believing it's my
interpretation of the library. If I've piqued your interest, feel
encouraged to read on.
My graph is a representation of a 2-dimensional mesh, so I've got an
NxN graph, where the vast majority of nodes have out-edges in all
four directions (N,S,E,W), and in-edges in all four directions.
I generate the graph with the following:
typedef adjacency_list < listS, vecS, undirectedS, no_property,
property < edge_weight_t, double > > graph_t;
graph_t gGraph(num_nodes);
then iterating over each node (i) and adding edges as follows:
add_edge(i, easterlydest, easterlyweight, gGraph);
finally, I call:
dijkstra_shortest_paths(gGraph,sourcenum,predecessor_map(&p
[0]).distance_map(&d[0]));
to evaluate the shortest paths. (Note that much of this is a cut-and-
paste from the Dijkstra_shortest_path example found at http://
www.boost.org/libs/graph/example/dijkstra-example.cpp ) Note also
that my understanding of the last argument to dijkstra_shortest_paths
is probably my weakest part of understanding the library.
I then iterate along a given shortest path by using the following
loop structure:
while(node != sourcenum) // iterate from dest to source, summing as
you go
{
int u = p[node];
int v = node;
graph_traits < graph_t >::edge_descriptor e = edge(u,v,graph).first;
double this_weight = get(edge_weight,graph,e);
path_length += this_weight;
node = p[node];
}
This returns a value of 1309.16 as the total path weight.
I then attempt to determine the manhattan path weights as well, to
compare how much of an improvement the shortest path is to the
manhattan paths.
I attempt to traverse the manhattan paths using a similar approach,
with something similar to the following (irrelevant lines omitted):
while(node != destnode) // iterate from source to dest, iterating as
you go
{
int nextnode = get_nextnode(xfirst,node); // gets index of next
node in an x-first y-next manhattan path
int u = node;
int v = nextnode;
graph_traits < graph_t >::edge_descriptor e = edge(u,v,graph).first;
double this_weight = get(edge_weight,graph,e);
xfpath_length += this_weight;
node = nextnode;
}
When this runs, I get a path length of 1299.79, a value more than
0.1% smaller. Either I'm determining the manhattan and shortest path
weights incorrectly, or it's not actually finding the shortest path.
So I did a bit of debugging (as programmers are wont to do). Tracing
the paths themselves, I eventually find that at one point, the
shortest path (hereafter abbreviated DSP) chooses to follow an out-
edge that doesn't have minimum weight. This is perfectly reasonable,
as it's possible (and probable) that this choice made now, will have
greater returns later, allowing an overall shorter path. However, it
never again returns to even equality with the manhattan path - the
manhattan path is shorter along the entire length, to the end.
I've checked my corner cases, and the paths are only being summed
along relevant edges (no off-by-one errors that I can see, at least).
If anyone has any ideas on how I might best debug/change my code, or
a means by which I can perform some other test, I'd love to hear it.
If anyone needs any more information, the code is by no means
confidential (though a bit messy) and I've got both .dot (graphviz)
format and an svg representation of the graph available. My
development platform is currently Mac OS X 10.4.4 PPC using Xcode, if
it matters to anyone.
Thanks, and I hope you don't mind the rather lengthy post!
- Greg Link
---- 20 70 80 95 106