Re: [jgrapht-developers] Fibonacci Heaps

[Michael B. <beh...@in...>]

=2D----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am Dienstag, 5. Oktober 2004 04:21 schrieb John V. Sichi:
> Go ahead with replacing mine with yours, Michael.  The one thing you
> might want to preserve from mine is the ability to extend heap nodes
> directly (e.g. ClosestFirstIterator.QueueEntry extends
> FibonacciHeap.Node).  This minimizes overhead for memory allocation and
> garbage collection.  It also avoids any need to hash to get from queue
> entry to corresponding heap node (since they're the same object).

I solved that with interfaces resp. the HeapVertex.

>
> Also, you might want to run some before/after performance comparisons
> with ClosestFirstIterator on large complex graphs to see how much
> overhead the extra genericity (e.g. arbitrary Comparators instead of
> hard-coded doubles) introduces.  If you report your numbers to this
> list, we can review and decide whether further special-casing would be
> worthwhile.
>

I tested with complete undirected graphs on about 500 to 1000 nodes
with more or less random weights
and performance loss was 2-5%. The new iterators are in the experimental=20
package (documentation is not ready yet).

Michael
=2D----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFBgNb7ZDyR4hR8HnQRAtR0AKDXG+APScunB4YAWFWTe5Uct8xL3ACcC/7k
s15KWBrpgF8TTyw/G772r88=3D
=3DYEp0
=2D----END PGP SIGNATURE-----