Re: [Gnu-arch-users] Re: situations where cached revisions are not so good

[Robert Collins]

On Sun, 2003-09-28 at 15:56, Jason McCarty wrote:

> More complicated algorithms could certainly put forth lots more effort
> to follow the graph in the most efficient way, yes. I've chosen a simple
> algorithm to avoid doing complicated graph searches.

Huh? I don't follow. SPF is trivial: you need
a) a priority queue
b) a 'visited' test for each node
c) a path recording structure
d) a cost for traversing a link.

Zing!

Add the nodes adjacent to TARGET to the queue. If a node is already in
the queue with a lower cost, throw away the adjacency being added.
Once you've finished those adjacencies, start popping the front of the
queue off, and adding it's adjacent nodes.

Rinse and repeat until, after finishing a nodes adjacencies you have one
or more successful paths.

The cheapest of those paths is the one to take.

And: it handles:
revlibs
cachedrev
summaries
normal changesets
  - all by virtue of the cost metric.

For a cost metric I suggest something like:
number of links * RTT *(MAGIC1) + total KB * observed|configured
bandwidth *(MAGIC2) + projected local tree copies *(MAGIC3)

where magic 1 2 and 3 are to normalise the metrics.

Rob
-- 
GPG key available at: <http://members.aardvark.net.au/lifeless/keys.txt>.

signature.asc
Description: This is a digitally signed message part