Christopher Browne wrote:
> "Florian G. Pflug" <fgp at phlo.org> writes:
>>Christopher Browne wrote:
>>>Christopher Browne wrote
>>>>I whiteboarded a couple of attempts at algorithms for this, this
>>>>afternoon.  It needs a bit more thought, I think, to come up with
>>>>something final...
>>
>>>Here's what I have at this point...
>>>The notion that seems to make sense, here, is to construct all of the
>>>possible maximum-length paths from each origin.  Note that this is a
>>>loose mix of C-like and pl/pgsql-like code; I'm not yet expecting it to
>>>be exactly right...
>>
>><snipped algorithm>
>>
>>>That gives us a list of all the longest possible traversals.
>>
>>Hm.. I don't really understand that algorithm (But, then, maybe
>>if've just been up for too long now.. ;-) ). Where is that
>>quantity-value coming from, and what does it do?
> 
> The quantity is counting whether, for a given traversal, we have found:
>  0 extensions to it (e.g. - we're at the end of the road)
>  1 extension to it (e.g. - lengthen it by one)
>  more than one extension to it (which means we have found a fork in the
>   road).
Ah.. ok.. I get that now. Thanks.

>>In the meantime I've coded up something myself. My first attempt was
>>to generate all traversals (not just the ones with maximum length),
>>and store them in a table (I used an array-valued field instead of a
>>second table vpath, but thats just a detail). This seems to work,
>>basically, but performance was horrible (For a fully-meshed graph
>>with 10 nodes, it would need to generate 10! (10 faktorial =
>>10*9*...*1) entries... :-(
>
> I try to extend them as much as possible, so that means you need
> rather fewer of them.
Hm.. but not actually much fewer I believe. First, my calculation
is a bit flawed I think - for 10 fully-meshed nodes you'd have 10*9
path entries. For every pair of nodes a and b, there is one way
from a to b with length 1 (a -> b), 8 ways with length 2 (a -> x -> b),
8*7 ways with length 3 (a -> x -> y -> b), ...

So, for every pair of nodes I'd have to generate 1! + 2! + 3! + 4! + 5! + 6! + 7! + 8!
traversals. Since there are 10*9 (ordered) pairs of nodes, that makes
10*9*(1!+2!+3!+4!+5!+6!+7!+8!) traversals. = 4160970 traversals

For you algorithm, only traversals of maximal length are generated - those
are 8! for every pair of nodes. That gives 10*9*8! = 10! traversals = 3628800 traversals

3,628,800 is still a lot of traversals... :-(

greetings, Florian Pflug