jgrapht-developers

[jgrapht-developers] Fibonacci Heaps

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

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

Hello,
at the moment there are two FibonacciHeap implementations
(one in util, one in experimental.heap) and I would like to know,
whether we want to decide to use only one of them or join them.

I would (of course) prefer my implementation (perhaps after=20
adding the union method) because it provides an interface to
use other heaps as well, can handle arbitrary elements and=20
orderings using Comparators and can do min and max heaps.

If you agree I would move the files and adapt the=20
ClosestFirstIterator (anything else?)

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

iD8DBQFBSW9AZDyR4hR8HnQRAvRSAJ9Af8326zq9e4lPAUFifcWpgZvXbgCfVos4
a+DylInk6a34I5KumO8CRp0=3D
=3DA3MR
=2D----END PGP SIGNATURE-----

Re: [jgrapht-developers] Fibonacci Heaps

[John V. S. <js...@ya...>]

Heh...it's been almost exactly one year since the last post on this 
topic.  Barak, we never heard back from you on this?  How would you like 
to consolidate?

My opinion is that

- we should use factories and/or strategies for flexibility

- we should provide specialized versions wherever they can provide extra 
efficiency (in last year's post Michael pointed out that the decision on 
Fibonacci vs. binary heap isn't clear-cut, and the representation I used 
when writing ClosestFirstIterator allowed me to combine the heap node 
with the queue entry to avoid extra lookups)

There's a related thread over in the users forum (topic 
"Vertex-indexation CPU-improves algorithms").

Michael, I noticed that your files under experimental all have GPL 
headers.  Anything that moves from the experimental packages into the 
non-experimental packages needs to change to LGPL with Barak's 
boilerplate headers.

JVS

Michael Behrisch wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Hello,
> at the moment there are two FibonacciHeap implementations
> (one in util, one in experimental.heap) and I would like to know,
> whether we want to decide to use only one of them or join them.
> 
> I would (of course) prefer my implementation (perhaps after 
> adding the union method) because it provides an interface to
> use other heaps as well, can handle arbitrary elements and 
> orderings using Comparators and can do min and max heaps.
> 
> If you agree I would move the files and adapt the 
> ClosestFirstIterator (anything else?)
> 
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
> 
> iD8DBQFBSW9AZDyR4hR8HnQRAvRSAJ9Af8326zq9e4lPAUFifcWpgZvXbgCfVos4
> a+DylInk6a34I5KumO8CRp0=
> =A3MR
> -----END PGP SIGNATURE-----
> 
> 
> -------------------------------------------------------
> This SF.Net email is sponsored by: YOU BE THE JUDGE. Be one of 170
> Project Admins to receive an Apple iPod Mini FREE for your judgement on
> who ports your project to Linux PPC the best. Sponsored by IBM.
> Deadline: Sept. 24. Go here: http://sf.net/ppc_contest.php
> _______________________________________________
> jgrapht-developers mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-developers
> 

Re: [jgrapht-developers] Fibonacci Heaps

[Barak N. <ba...@3p...>]

first, appologies for my slow response -- just stepped out of the Ecuador=
ian
jungle into an internet cafe to briefly review my mail...

indeed, i never got around to "absorb" quite a few pieces of code others =
have
suggested. partly because code required some adjustments to fit into the
JGraphT coding style. it can significantly reduce the adjustment work if =
the
code is "jalopy"-ed and "checkstyle"-ed. i know the style might not be to=
 the
linking of everyone, but i believe style should be consistant.
=20
as for the fibonacci heap, if think the factory/strategy approach John su=
ggested
is the appropriate solution. however, a default factory/strategy should b=
e
provided so that a beginner could use the library without having to speci=
fy
them.=20

Michael, i will be away until mid-october and i dont want to bottleneck y=
our
developments. You can discuss with John and whatever he decides is fine w=
ith me
(John, is it ok with you?). just CC me on your descussions so that i can =
catch
up quicker upon my return.=20

barak

Quoting "John V. Sichi" <js...@ya...>:

> Heh...it's been almost exactly one year since the last post on this=20
> topic.  Barak, we never heard back from you on this?  How would you lik=
e=20
> to consolidate?
>=20
> My opinion is that
>=20
> - we should use factories and/or strategies for flexibility
>=20
> - we should provide specialized versions wherever they can provide extr=
a=20
> efficiency (in last year's post Michael pointed out that the decision o=
n=20
> Fibonacci vs. binary heap isn't clear-cut, and the representation I use=
d=20
> when writing ClosestFirstIterator allowed me to combine the heap node=20
> with the queue entry to avoid extra lookups)
>=20
> There's a related thread over in the users forum (topic=20
> "Vertex-indexation CPU-improves algorithms").
>=20
> Michael, I noticed that your files under experimental all have GPL=20
> headers.  Anything that moves from the experimental packages into the=20
> non-experimental packages needs to change to LGPL with Barak's=20
> boilerplate headers.
>=20
> JVS
>=20
> Michael Behrisch wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >=20
> > Hello,
> > at the moment there are two FibonacciHeap implementations
> > (one in util, one in experimental.heap) and I would like to know,
> > whether we want to decide to use only one of them or join them.
> >=20
> > I would (of course) prefer my implementation (perhaps after=20
> > adding the union method) because it provides an interface to
> > use other heaps as well, can handle arbitrary elements and=20
> > orderings using Comparators and can do min and max heaps.
> >=20
> > If you agree I would move the files and adapt the=20
> > ClosestFirstIterator (anything else?)
> >=20
> > Michael
> > -----BEGIN PGP SIGNATURE-----
> > Version: GnuPG v1.2.4 (GNU/Linux)
> >=20
> > iD8DBQFBSW9AZDyR4hR8HnQRAvRSAJ9Af8326zq9e4lPAUFifcWpgZvXbgCfVos4
> > a+DylInk6a34I5KumO8CRp0=3D
> > =3DA3MR
> > -----END PGP SIGNATURE-----
> >=20
> >=20
> > -------------------------------------------------------
> > This SF.Net email is sponsored by: YOU BE THE JUDGE. Be one of 170
> > Project Admins to receive an Apple iPod Mini FREE for your judgement =
on
> > who ports your project to Linux PPC the best. Sponsored by IBM.
> > Deadline: Sept. 24. Go here: http://sf.net/ppc_contest.php
> > _______________________________________________
> > jgrapht-developers mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-developers
> >=20
>=20
>=20
>=20
>=20
> -------------------------------------------------------
> This SF.Net email is sponsored by: YOU BE THE JUDGE. Be one of 170
> Project Admins to receive an Apple iPod Mini FREE for your judgement on
> who ports your project to Linux PPC the best. Sponsored by IBM.
> Deadline: Sept. 24. Go here: http://sf.net/ppc_contest.php
> _______________________________________________
> jgrapht-developers mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-developers
>=20

Re: [jgrapht-developers] Fibonacci Heaps

[John V. S. <js...@ya...>]

Barak Naveh wrote:
> as for the fibonacci heap, if think the factory/strategy approach John suggested
> is the appropriate solution. however, a default factory/strategy should be
> provided so that a beginner could use the library without having to specify
> them. 
> 
> Michael, i will be away until mid-october and i dont want to bottleneck your
> developments. You can discuss with John and whatever he decides is fine with me
> (John, is it ok with you?). just CC me on your descussions so that i can catch
> up quicker upon my return. 

Sure.  Michael, perhaps you can propose details on how you'd like to see 
the existing components refactored, and then I can give you feedback.

JVS

Re: [jgrapht-developers] Fibonacci Heaps

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

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

> Barak Naveh wrote:
> > as for the fibonacci heap, if think the factory/strategy approach John
> > suggested is the appropriate solution. however, a default
> > factory/strategy should be provided so that a beginner could use the
> > library without having to specify them.
> >
> > Michael, i will be away until mid-october and i dont want to bottleneck
> > your developments. You can discuss with John and whatever he decides is
> > fine with me (John, is it ok with you?). just CC me on your descussions
> > so that i can catch up quicker upon my return.
>
> Sure.  Michael, perhaps you can propose details on how you'd like to see
> the existing components refactored, and then I can give you feedback.

I'd like to have what's already in my heaps ;-) Especially arbitrary=20
Comparators for the order of the elements and the ability to create min-/an=
d=20
max-heaps. I think one could use my heaps and modify the=20
ClosestFirstIterator accordingly. If You want I can do that.

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

iD8DBQFBYS6/ZDyR4hR8HnQRAp0RAJ9QFLJbpdfAihs8Metk4/pt6FpfkACZAaer
9u1uj0zqrIqQZYqj9oVsLZI=3D
=3DJsn2
=2D----END PGP SIGNATURE-----

Re: [jgrapht-developers] Fibonacci Heaps

[John V. S. <js...@ya...>]

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).

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.

JVS

Michael Behrisch wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
>>Barak Naveh wrote:
>>
>>>as for the fibonacci heap, if think the factory/strategy approach John
>>>suggested is the appropriate solution. however, a default
>>>factory/strategy should be provided so that a beginner could use the
>>>library without having to specify them.
>>>
>>>Michael, i will be away until mid-october and i dont want to bottleneck
>>>your developments. You can discuss with John and whatever he decides is
>>>fine with me (John, is it ok with you?). just CC me on your descussions
>>>so that i can catch up quicker upon my return.
>>
>>Sure.  Michael, perhaps you can propose details on how you'd like to see
>>the existing components refactored, and then I can give you feedback.
> 
> 
> I'd like to have what's already in my heaps ;-) Especially arbitrary 
> Comparators for the order of the elements and the ability to create min-/and 
> max-heaps. I think one could use my heaps and modify the 
> ClosestFirstIterator accordingly. If You want I can do that.
> 
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
> 
> iD8DBQFBYS6/ZDyR4hR8HnQRAp0RAJ9QFLJbpdfAihs8Metk4/pt6FpfkACZAaer
> 9u1uj0zqrIqQZYqj9oVsLZI=
> =Jsn2
> -----END PGP SIGNATURE-----
> 

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-----