Markus Neteler wrote:
Greg,
just FYI: The vector data are here:
http://frida.intevation.org/
Markus
Here are the results of running dgtable (i.e., Directed Graph
implemented with lookup tables) ShortestPath variants on the FRIDA
data. The screen dumps come from a Windows application in which I'm
using dgtable to conflate vector maps. I'm also using dgtable in the
creation of vector maps for handhelds running Palm OS. I believe the
last Shortest Path variant (i.e., points to graph) is equivalent to the
reportedly slow v.net.iso function.
Greg
- - -
shortest path variant: point to point
dgtable function: FindShortestPath
example application: driving directions
screen dump: http://www.eduneer.com/dgtable/sp00.png
execution time: 0.16 seconds
comments: green circle represents starting point
yellow path is shortest path
red circle represents destination
shortest path variant: point to graph
dgtable function: FindShortestPath (with destination argument = 0)
example application: pizza delivery range
screen dump: http://www.eduneer.com/dgtable/sp01.png
execution time: 0.16 seconds
comments: green circle represent starting point
green lines are middle third of cost range
yellow lines are final third of cost range
red lines are not reachable (as defined by the
graph)
shortest path variant: points to point
dgtable function: FindShortestPathMultipleStartingPoints
example application: dispatch closest police car
screen dump: http://www.eduneer.com/dgtable/sp10.png
execution time: 0.44 seconds
comments: green circles represent starting points
yellow path is shortest path
red circle represents destination
shortest path variant: points to graph
dgtable function: FindShortestPathMultipleStartingPoints (with
destination argument = 0)
example application: planning location of distribution warehouses
screen dump: http://www.eduneer.com/dgtable/sp11.png
execution time: 0.44 seconds
comments: green circle represents starting point
green lines are middle third of cost range
yellow lines are final third of cost range
red lines are not reachable (as defined by the
graph)
On Sunday 09 November 2003 23:16, Greg Sepesi wrote:
Here are the results of running dgtable (i.e., Directed Graph
implemented with lookup tables) ShortestPath variants on the FRIDA
data. The screen dumps come from a Windows application in which I'm
using dgtable to conflate vector maps. I'm also using dgtable in the
creation of vector maps for handhelds running Palm OS. I believe the
last Shortest Path variant (i.e., points to graph) is equivalent to the
reportedly slow v.net.iso function.
...
shortest path variant: points to graph
dgtable function: FindShortestPathMultipleStartingPoints (with
destination argument = 0)
example application: planning location of distribution warehouses
screen dump: http://www.eduneer.com/dgtable/sp11.png
execution time: 0.44 seconds
comments: green circle represents starting point
green lines are middle third of cost range
yellow lines are final third of cost range
red lines are not reachable (as defined by the
CPU?
On 1.5GHz processor v.net.iso takes
9m 39.372s for current cvs version and
1.867s if cache is enabled
In this case (this data) the result is the same, but there is a bug in cache,
which may cause bad results in certain cases.
The time includes writing vector and building topology, v.build on the result
takes 0.988s.
I think that 1.867s is not bad, the problem is the bug in cache.
Radim
Radim Blazek wrote:
On Sunday 09 November 2003 23:16, Greg Sepesi wrote:
> Here are the results of running dgtable (i.e., Directed Graph
> implemented with lookup tables) ShortestPath variants on the FRIDA
> data. The screen dumps come from a Windows application in which I'm
> using dgtable to conflate vector maps. I'm also using dgtable in the
> creation of vector maps for handhelds running Palm OS. I believe the
> last Shortest Path variant (i.e., points to graph) is equivalent to the
> reportedly slow v.net.iso function.
...
> shortest path variant: points to graph
> dgtable function: FindShortestPathMultipleStartingPoints (with
> destination argument = 0)
> example application: planning location of distribution warehouses
> screen dump: http://www.eduneer.com/dgtable/sp11.png
> execution time: 0.44 seconds
> comments: green circle represents starting point
> green lines are middle third of cost range
> yellow lines are final third of cost range
> red lines are not reachable (as defined by the
CPU?
On 1.5GHz processor v.net.iso takes
9m 39.372s for current cvs version and
1.867s if cache is enabled
In this case (this data) the result is the same, but there is a bug in cache,
which may cause bad results in certain cases.
The time includes writing vector and building topology, v.build on the result
takes 0.988s.
I think that 1.867s is not bad, the problem is the bug in cache.
Radim
Hi Radim,
I ran the tests on a modestly equipped PC with a 500 MHz Pentium II
processor.
The dglib cache would be helpful, but maybe not enough. Deeply nested
(i.e., frequently called) in the dglib algorithms are calls to avl_find
which has a running time proportional to log V (where V is the number of
vertices in the graph). In dgtable, vertex information is obtained from
a lookup table rather than a balanced tree so the frequent searching is
avoided. It isn't clear to me that the dglib cache (even if it were
fixed) would avoid the frequent searching. The FRIDA dataset is
relatively small. It would be interesting to also perform timing tests
on a dataset that is 100 times larger.
Greg
