[Freeciv-Dev] Re: Warmap

[Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx>]

On Tue, 13 Aug 2002, Gregory Berkolaiko wrote:

> On Mon, 12 Aug 2002, Vasco Alexandre Da Silva Costa wrote:
>
> > Regarding warmap speedups:
> >
> > If anyone feels up to implementing them, there are some algorithms which
> > promise to solve the single-source problem:
> > <http://www.boost.org/libs/graph/doc/graph_theory_review.html>
> >
> > in linear time for undirected planar graphs:
> > <http://mathworld.wolfram.com/PlanarGraph.html>.
> >
> > IIRC Dijkstra takes quadratic time in our implementation.
>
> Yes I did some research on it previously, in particular read the papers by
> Thorup and Goldberg that you are referring to below.  Some of the
> algorithms you mention are not applicable to our case which is non-planar
> graph with non-negative (rather than strictly positive) weights.

Argh... silly me, only now that you mentioned it i noticed the graph has
edges that cross. I had noticed that Thorup's paper was only for positive
weights, i put it mostly as reference, hence why i placed the link to the
planar graph algorithm first (which seemingly doesn't apply here either,
doh!).

> Besides AFAIU the current implementation _is_ linear, at least in the
> sense that Thorup's algorithm is linear (his discovery was that you can
> pile nodes into a bucket list even though your weights are not integers --
> this is already done in the current warmap).  My own empirical discovery
> was that if in our case you go for priority queue (log(n) time) rather
> than for bucket list (constant time) you get a speed-up: the bucket list
> is too expensive to set up for the small $n$ we usually get.

Hmmm... Ok. So on your optimization you use a heap instead? (log(n) time
suggests some tree structure).

Did you benchmark it after several runs? Glancing at it it seems to me
that it only does those nasty mallocs() once, afterwards memory is fetched
from a pool.

---
Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa