v.net.iso calculates costs from each starting point to all network nodes.
Obviously an algorithm implemented in dglib would be much faster,
unfortunately it is not, and dglib is difficult to change.
Radim
Hi Radim,
Upon completion of the shortest path algorithm, each node in the graph
is associated with a cost to get there from the starting point. With K
starting points within a graph with N nodes, v.net.iso consists of
running the shortest path algorithm K times, and for each of the N nodes
calculating the minimum of the K costs. Of course the shortest path
algorithm should be performed within the directed graph library. But it
seems the per node calculation of the minimum cost could be performed
either inside or outside the directed graph library. I didn't put it in
the dgtable library, but it would be easy to do so. Either way, I think
that for small K (e.g., 10) and moderate N (e.g., 10,000), the
calculation of v.net.iso can be virtually instantaneous.
As an aside, I noticed something peculiar in the v.net.iso screen dump
at
http://mpa.itc.it/radim/g51/v.net.iso.png
At the 6th starting point from the top, there are a couple orange paths
completely isolated by blue. Shouldn't they be connected to other
orange?
Greg
Greg Sepesi wrote:
>
> v.net.iso calculates costs from each starting point to all network nodes.
> Obviously an algorithm implemented in dglib would be much faster,
> unfortunately it is not, and dglib is difficult to change.
>
> Radim
>
Hi Radim,
Upon completion of the shortest path algorithm, each node in the graph
is associated with a cost to get there from the starting point. With K
starting points within a graph with N nodes, v.net.iso consists of
running the shortest path algorithm K times, and for each of the N nodes
calculating the minimum of the K costs. Of course the shortest path
algorithm should be performed within the directed graph library. But it
seems the per node calculation of the minimum cost could be performed
either inside or outside the directed graph library. I didn't put it in
the dgtable library, but it would be easy to do so. Either way, I think
that for small K (e.g., 10) and moderate N (e.g., 10,000), the
calculation of v.net.iso can be virtually instantaneous.
As an aside, I noticed something peculiar in the v.net.iso screen dump
at
http://mpa.itc.it/radim/g51/v.net.iso.png
At the 6th starting point from the top, there are a couple orange paths
completely isolated by blue. Shouldn't they be connected to other
orange?
Greg
Oops, my mistake. Orange is higher cost than blue. So orange isolated
in blue is okay. (Blue isolated in orange wouldn't be.)
Greg
On Fri, Oct 31, 2003 at 10:52:31AM -0500, Greg Sepesi wrote:
Greg Sepesi wrote:
>
> >
> > v.net.iso calculates costs from each starting point to all network nodes.
> > Obviously an algorithm implemented in dglib would be much faster,
> > unfortunately it is not, and dglib is difficult to change.
> >
> > Radim
> >
>
> Hi Radim,
>
> Upon completion of the shortest path algorithm, each node in the graph
> is associated with a cost to get there from the starting point. With K
> starting points within a graph with N nodes, v.net.iso consists of
> running the shortest path algorithm K times, and for each of the N nodes
> calculating the minimum of the K costs. Of course the shortest path
> algorithm should be performed within the directed graph library. But it
> seems the per node calculation of the minimum cost could be performed
> either inside or outside the directed graph library. I didn't put it in
> the dgtable library, but it would be easy to do so. Either way, I think
> that for small K (e.g., 10) and moderate N (e.g., 10,000), the
> calculation of v.net.iso can be virtually instantaneous.
>
> As an aside, I noticed something peculiar in the v.net.iso screen dump
> at
>
> http://mpa.itc.it/radim/g51/v.net.iso.png
>
> At the 6th starting point from the top, there are a couple orange paths
> completely isolated by blue. Shouldn't they be connected to other
> orange?
>
> Greg
Oops, my mistake. Orange is higher cost than blue. So orange isolated
in blue is okay. (Blue isolated in orange wouldn't be.)
Greg,
just FYI: The vector data are here:
http://frida.intevation.org/
Markus
Markus Neteler wrote:
Greg,
just FYI: The vector data are here:
http://frida.intevation.org/
Markus
Sometime this week I'll write a variation of dgtable's FindShortestPath
function so that it accepts multiple starting points. I'll run it on
the frida data and report the results.
Greg
