[Freeciv-Dev] Re: Warmap

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Aug 15, 2002 at 10:17:41AM +0100, Gregory Berkolaiko wrote:
> On Wed, 14 Aug 2002, Raimar Falke wrote:
> 
> > On Tue, Aug 13, 2002 at 10:16:28PM +0100, Vasco Alexandre Da Silva Costa 
> > wrote:
> > > 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.
> > 
> > Since Dresden got flooded yesterday and I lost the internet I have
> > also done some research. Results are: most of the algorithms derive
> > from Dijkstra's algorithm and differ in the way the unfinished-nodes
> > are managed. You can use:
> > 
> > n - number of nodes = number of tiles
> > m - number of edges (roughly 4*n)
> > c - largest cost of edge (2^8-1 in server/gotohand.c, planned to be
> >     2^32-1 in the new path finding)
> > 
> >  - a list which you search for the minimum: gives O(n^2) = 4000k
> >  - a bucket list (current server/gotohand.c) also known as Dial's
> >  algorithm: O(m+n*c) = 518k
> >  - a 2-heap: as in path_finding13.diff: gives O(m*ldn+2*n*ldn) = 132k
> >  - a radix heap: O(m+n*ld(n*c)) = 46k
> >  - a fibonacci heap: O(m+n*logn) = 23k
> > 
> > All of these should be taken with a grain of salt since out n is at
> > most 2000 and so the (unknown) constant factors may be more important.
> > 
> > Profiling the server/gotohand.c shows that <10% of the time is spend
> > in add_to_mapqueue and get_from_mapqueue. It is even less for
> > path_finding13.diff. Most of the time is used not for the path finding
> > per se but the information gathering: can a unit move to this tile
> > (zoc, attack enemy, ground_unit_transporter_capacity), how much would
> > this move cost (map_get_terrain,...) and misc (like can I see the
> > target tile). So more can be achieved by caching these values like
> > ptile->move_cost does.
> > 
> > I haven't looked at non-Dijkstra algorithms like Thorup's. But even if
> > this algorithm can be applied on our problem the big question is the
> > constant factor.
> 
> But Thorup is Dijkstra!  His algorithm is essentially on how to split 
> costs into bucket AFAIR.

From http://citeseer.nj.nec.com/meyer01singlesource.html:

  Nearly all of these algorithms are based on Dijkstra's algorithm and
  improve the priority queue data structure. Thorup has given the
  first ... His approac applies label-setting but significantly
  deviates from Dijkstra's algorithm in that it does not visit the
  nodes in order of increasing distance from ....

        Raimar
-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Any sufficiently advanced technology is indistinguishable from magic."
    -- Arthur C. Clarke