Aaron (and the rest of the Boost-user's list) -
I've attached a link to a .tar.gz of the source code I'm using,
which currently requires both boost and the matpack library (for
shepard interpolation), however, the only use of the matpack library
is in the function "init_tsmap", where two "if(use_interpolation)"
statements differentiate the code that needs matpack from a non-
matpack codepath that simply instantiates the values in the tsmap to
random values (originally put in to allow debugging the rest of the
code separately from matpack). Hence, if you don't have matpack, you
can just delete/ifdef out the matpack-based codepath.
If you do have matpack, the executable " ./a.out 20 70 80 95 106"
will read in the "input.dat" file, generate a tsmap object, then a
graph, and attempt to find the shortest paths from the node at [20%,
70%] to [80%, 95%], with a graph of 106x106 nodes. Many other calls
(such as the same points at a grid size of 105) return a shortest
path that is, in fact, shorter than the manhattan paths, but if code
fails in one weird case, you can be sure something is wrong
somewhere, so can't really claim it works.
If you don't have matpack, the code initializes a tsmap with random
values, and thus a graph with random weights, so I don't have a case
that will cause it to fail available. I have, however, provided
a .dot (graphviz) format file "dump-00.dot" of the entire graph, with
each edge labeled with the appropriate weight.
As a final statement, please forgive the quality of the source
provided. It's still very much a work-in-progress, and as the
specifications change hourly, so do the data formats, function
interfaces, et cetera. Always embarrassing to have something other
than one's best work on public display.
- Greg
To reduce message size, I've provided download links for all files,
rather than attaching them directly.
Source: http://www.cse.psu.edu/~link/link_dijkstra.cpp.gz
Text files listing the paths: http://www.cse.psu.edu/~link/
path_listings.tar.gz
Graphviz-format output file (takes a lot of memory to render - over
11 thousand edges): http://www.cse.psu.edu/~link/dump-00.dot.gz
SVG-format file demonstrating the problem in a much more useful
visual format (viewable in any cutting-edge browser, such as Firefox,
Nightly Safari WebKit builds, or using the Adobe SVG plugin) : http://
www.cse.psu.edu/~link/svg-00.svg.gz
On Feb 15, 2006, at 6:47 AM, Aaron Windsor wrote:
On 2/14/06, Greg Link
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.
<snip> Greg, Could you zip up your code and the .dot input file and post them, if the file isn't too big? Thanks, Aaron