jgrapht-developers — A discussion list for JGraphT developers.

[jgrapht-developers] upcoming releases

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

Here's an update on the plan for upcoming releases. If you are a JGraphT 
user and have feedback on this plan, now is the time to speak up.

JGraphT 0.6.0. This will be the first (and possibly last) release 
requiring JDK/JVM 1.4. Instead of naming it 0.5.4, we will name it 0.6.0 
to emphasize incompatibility with older JVM's. The target timeframe for 
this release is July.

JGraphT 0.7.0. Christian Hammer has contributed a port of the core 
JGraphT classes to JDK 1.5 with generics. No more typecasting vertices 
and edges when you access a graph! After 0.6.0 has been released, 
Christian will check his changes into CVS, and we will start requiring 
JDK 1.5 to build JGraphT.

If you are unable to upgrade to 1.5, fear not. We have tested 
Christian's port with the Retroweaver project, and we have an automated 
solution for producing a 1.4-compatible type-erased backport without 
needing to maintain both codelines. Releases starting with 0.7.0 will 
include two jars (one for use with JDK/JVM 1.4, and one for use with 
JDK/JVM 1.5).

The timeframe for the 0.7.0 release has not yet been determined. If you 
would like to volunteer with porting remaining portions of JGraphT to 
JDK 1.5, please respond to this message.

JVS

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

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

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

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] Adding multiple edges and loops

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

> > for a similar reason, if the user tries to "forcibly" add multiple ed=
ges
> to
> > graph that forbids multiple edges (this can be done by abusing the
> > addEdge(Edge e) method) then an exception should be thrown -- the gra=
ph
> > needs to defend its consistency. if this is not currently the case, i=
t
> > should be fixed.
>=20
> This is currently not the case. addEdge(e) behaves exactly like=20
> addEdge(e.getSource(), e.getTarget()). It throws exception on forbidden
> loops and silently ignores forbidden multiple edges.=20

hmm, my goof then.. i think it should be corrected
(http://sourceforge.net/tracker/?func=3Ddetail&atid=3D579687&aid=3D103311=
1&group_id=3D86459)

> >
> > However, if the user attempts to add an edge which is already existin=
g
> > using addEdge(v1,v2), then it is not a mistake. he or she wants to in=
clude
> > the specified edge in the edge set. if the edge already in the edge s=
et,
> > there is nothing to do. if it is not, it is included.  in other words=
, the
> > call can satisfy the user wish, without violating any graph consisten=
cy
> > criteria and therefore there is no reason to throw an exception.
> >
> > is my reasoning making sense?
>=20
> Partly. I think it is more reasonible to let addEdge(e) behave exactly=20
> like addEdge(v1, v2), because on graphs with multiple edges allowed
> your argumentation would fail. What does the user want when calling
> addEdge(v1,v2) when such an edge is already present. Add another=20
> one or just ensure that an edge is present? I think a user calling=20
> addEdge really wants to add an Edge and following your reasoning
> both versions of addEdge should always throw an exception when the=20
> two vertices are already connected and multiedges are forbidden.

On graphs with multiple edges allowed the argumentation indeed becomes we=
aker,
or at least question raising. As a user i would want addEdge(v1,v2) to al=
ways
add a new edge if multiple edges are allowed. If multiple edges are forbi=
den, i
would want it to add a new edge only if no edge exists between v1 and v2.=
 Such
behavior is (almost:) consistent with the fact that the edge set is, well=
, a
Set. As such, it behaves differently when multiple edges are allowed --pa=
rallel
edges are equal in the non-multiple case, but aren't in the multiple case=
.

Not sure if it's the best solution, but i suppose it's better than a sile=
nt
ignoring. What do you think? Other ideas? John?

barak

Re: [jgrapht-developers] jalopy

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

jalopy has a problem that it sometimes alternates between two formattings=
. that
is unfortunate because it creates "artificial changes" in unchanged files=
.

however, i'm not aware of a better free alternative to jalopy. Eclips' so=
urce
formatter is getting better, but is not there yet.=20

i suggest running jalopy on individual files rather than globally on all =
source
files. then to pick one of the two alternative that you like best and che=
ck it
in. If the file already in CVS, try to minimize the number of changes -- =
to
stay consistent to the formatting of previous version.

i know it's not a great "solution", but have found it a reasonable way to=
 use
jalopy, and take advantage of it's benefits.

barak


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

> It seems to be unpredictable, or maybe it's based on what it thinks has=
=20
> changed after a cvs update.  Kind of annoying.
>=20
> The current approach is to make individual developers responsible for=20
> running jalopy on each checkin.  An alternative would be to defer it,=20
> and make Barak responsible for running it as the first step in preparin=
g=20
> a release.  So the latest code in CVS would typically contain a mixture=
=20
> of styles, but the released code would always be uniform.
>=20
> JVS
>=20
> Michael Behrisch wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >=20
> > I just ran 'ant jalopy' and it modified all source files (although
> apparently
> > according to the jalopy-settings in etc), but I dont think that this
> > was intended, bacause a lot of files should already adhere to
> > the jalopy standards, shouldn't they?. Did I do something wrong?
> >=20
> > Michael
> > -----BEGIN PGP SIGNATURE-----
> > Version: GnuPG v1.2.4 (GNU/Linux)
> >=20
> > iD8DBQFBTsqAZDyR4hR8HnQRAlQUAJ9g2WMvl2Oi04s6Kwxauow72O2BswCg0nhm
> > aHpBz6gmlqu1y1NTUfHUfMk=3D
> > =3Dol+S
> > -----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] jalopy

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

jalopy has a problem that it sometimes alternates between two formattings=
. that
is unfortunate because it creates "artificial changes" in unchanged files=
.

however, i'm not aware of a better free alternative to jalopy. Eclips' so=
urce
formatter is getting better, but is not there yet.=20

i suggest running jalopy on individual files rather than globally on all =
source
files. then to pick one of the two alternative that you like best and che=
ck it
in. If the file already in CVS, try to minimize the number of changes -- =
to
stay consistent to the formatting of previous version.

i know it's not a great "solution", but have found it a reasonable way to=
 use
jalopy, and take advantage of it's benefits.

barak


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

> It seems to be unpredictable, or maybe it's based on what it thinks has=
=20
> changed after a cvs update.  Kind of annoying.
>=20
> The current approach is to make individual developers responsible for=20
> running jalopy on each checkin.  An alternative would be to defer it,=20
> and make Barak responsible for running it as the first step in preparin=
g=20
> a release.  So the latest code in CVS would typically contain a mixture=
=20
> of styles, but the released code would always be uniform.
>=20
> JVS
>=20
> Michael Behrisch wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >=20
> > I just ran 'ant jalopy' and it modified all source files (although
> apparently
> > according to the jalopy-settings in etc), but I dont think that this
> > was intended, bacause a lot of files should already adhere to
> > the jalopy standards, shouldn't they?. Did I do something wrong?
> >=20
> > Michael
> > -----BEGIN PGP SIGNATURE-----
> > Version: GnuPG v1.2.4 (GNU/Linux)
> >=20
> > iD8DBQFBTsqAZDyR4hR8HnQRAlQUAJ9g2WMvl2Oi04s6Kwxauow72O2BswCg0nhm
> > aHpBz6gmlqu1y1NTUfHUfMk=3D
> > =3Dol+S
> > -----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

[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] jalopy

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

It seems to be unpredictable, or maybe it's based on what it thinks has 
changed after a cvs update.  Kind of annoying.

The current approach is to make individual developers responsible for 
running jalopy on each checkin.  An alternative would be to defer it, 
and make Barak responsible for running it as the first step in preparing 
a release.  So the latest code in CVS would typically contain a mixture 
of styles, but the released code would always be uniform.

JVS

Michael Behrisch wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> I just ran 'ant jalopy' and it modified all source files (although apparently
> according to the jalopy-settings in etc), but I dont think that this
> was intended, bacause a lot of files should already adhere to
> the jalopy standards, shouldn't they?. Did I do something wrong?
> 
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
> 
> iD8DBQFBTsqAZDyR4hR8HnQRAlQUAJ9g2WMvl2Oi04s6Kwxauow72O2BswCg0nhm
> aHpBz6gmlqu1y1NTUfHUfMk=
> =ol+S
> -----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
> 

[jgrapht-developers] jalopy

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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I just ran 'ant jalopy' and it modified all source files (although apparently
according to the jalopy-settings in etc), but I dont think that this
was intended, bacause a lot of files should already adhere to
the jalopy standards, shouldn't they?. Did I do something wrong?

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

iD8DBQFBTsqAZDyR4hR8HnQRAlQUAJ9g2WMvl2Oi04s6Kwxauow72O2BswCg0nhm
aHpBz6gmlqu1y1NTUfHUfMk=
=ol+S
-----END PGP SIGNATURE-----

Re: [jgrapht-developers] Adding multiple edges and loops

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

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

Am Montag, 20. September 2004 03:39 schrieb Barak Naveh:
> i think it is consistent and fine.
>
> here is my resoning:
>
> adding a forbidden loop is a mistake that violates the graph consistency
> (if it forbid such loops). the graph should then throw an exception to
> "defend" itself from begin corrupted.
>
> for a similar reason, if the user tries to "forcibly" add multiple edges =
to
> graph that forbids multiple edges (this can be done by abusing the
> addEdge(Edge e) method) then an exception should be thrown -- the graph
> needs to defend its consistency. if this is not currently the case, it
> should be fixed.

This is currently not the case. addEdge(e) behaves exactly like=20
addEdge(e.getSource(), e.getTarget()). It throws exception on forbidden
loops and silently ignores forbidden multiple edges.=20

>
> However, if the user attempts to add an edge which is already existing
> using addEdge(v1,v2), then it is not a mistake. he or she wants to include
> the specified edge in the edge set. if the edge already in the edge set,
> there is nothing to do. if it is not, it is included.  in other words, the
> call can satisfy the user wish, without violating any graph consistency
> criteria and therefore there is no reason to throw an exception.
>
> is my reasoning making sense?

Partly. I think it is more reasonible to let addEdge(e) behave exactly=20
like addEdge(v1, v2), because on graphs with multiple edges allowed
your argumentation would fail. What does the user want when calling
addEdge(v1,v2) when such an edge is already present. Add another=20
one or just ensure that an edge is present? I think a user calling=20
addEdge really wants to add an Edge and following your reasoning
both versions of addEdge should always throw an exception when the=20
two vertices are already connected and multiedges are forbidden.

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

iD8DBQFBTsm2ZDyR4hR8HnQRAnnAAKDeSkYacrhMzdUwUR6b/WYUfvz8tACgm4KR
imbIcMfgyBhuEl46zacCn1A=3D
=3D/grz
=2D----END PGP SIGNATURE-----

Re: [jgrapht-developers] Adding multiple edges and loops

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

i think it is consistent and fine.=20

here is my resoning:

adding a forbidden loop is a mistake that violates the graph consistency =
(if it
forbid such loops). the graph should then throw an exception to "defend" =
itself
from begin corrupted.

for a similar reason, if the user tries to "forcibly" add multiple edges =
to
graph that forbids multiple edges (this can be done by abusing the addEdg=
e(Edge
e) method) then an exception should be thrown -- the graph needs to defen=
d its
consistency. if this is not currently the case, it should be fixed.

However, if the user attempts to add an edge which is already existing us=
ing
addEdge(v1,v2), then it is not a mistake. he or she wants to include the
specified edge in the edge set. if the edge already in the edge set, ther=
e is
nothing to do. if it is not, it is included.  in other words, the call ca=
n
satisfy the user wish, without violating any graph consistency criteria a=
nd
therefore there is no reason to throw an exception.

is my reasoning making sense?

barak

--
ps: again, expect slow response until mid-october.



Quoting Michael Behrisch <beh...@in...>:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>=20
> Hello,
> don't you think it is inconsistent behavior to throw an exception
> when trying to add a forbidden loop but simply returning null
> when trying to add a multiple edge? Since the loop behavior
> is not documented I think it is save to change this to returning=20
> null as well. It would very much ease the creation of random=20
> graphs I am currently working at.
>=20
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>=20
> iD8DBQFBSWnDZDyR4hR8HnQRAmQWAKCCbiSLbYUhxdlSw3GSTltJxsMmoQCfVZ7N
> NlgRX8aP5mmbZN3yvcEEA5E=3D
> =3DEv96
> -----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

Re: [jgrapht-developers] Subgraph issues

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

> 1. Why doesn't Subgraph have a toString method (and why doesn't=20
> AbstractGraph simply have the toString method=20
> AbstractBaseGraph has)?

i am traveling for a few weeks, and wont have convenient access to the so=
urce,
but if that=B4s the situation, its a mistake.  toString should move to pa=
rent.
feel free to fix.

> 2. degreeOf returns the degree of the vertex in the base graph=20
> which is not asked for.

i thought i fixed that bug. if fix not in CVS, you can go ahead and fix i=
t. i
believe there are also a similar bugs in inDegreeOf, outDegreeOf. it=B4s =
a chance
to fix them too while there. there should be bug reports related to them =
--
worth checking.

> 3. Subgraph should be able to be created as an induced subgraph
> and keep track of this property. This can be done either by
> changing the class or subclassing it.

i=B4m not sure i perfectly understand what you mean.
i once thought of using the filter pattern to provide a subgraph that fol=
lows
the base graph. using a filter with methods acceptEdge(e) and acceptVerte=
x(v)
could be a useful generalization on the existing subgraph. if that is wha=
t
you=B4re having in mind, feel free to go ahead and implement. make sure, =
though,
to keep backward competability. adding another constructor to Sugraph wit=
h the
filter might do the trick.=20

> 4. Subgraph should be listenable as well such that one can create=20
> subgraphs of subgraphs.

i cannot check the source now, but i believe there was a reason for Subgr=
aph
not to be listenable. yuo can go ahead and make it listaneable -- we can =
always
roll-back if need be. However, make sure to do it as a separate and last
change, so if roll-back is required, the rest of your changes will not be
affected.

barak.

--
ps: will be back from my travel mid-october.=20

Re: [jgrapht-developers] target for experimental

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

yep, its fine, provided it is not included in the "user targets".=20

The experimental stuff is not included in the distribution, so expbuild s=
hould
first check if the experimental folder exists. If it does not, it should =
say
something like "Experimental source files are missing. They are not inclu=
ded in
standard distributions and can only be obtained from CVS".

ps: sorry for slow response -- traveling..

barak


Quoting Michael Behrisch <beh...@in...>:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>=20
> Hello,
> is it ok to include an ant target for the experimental files
> which compiles into a new directory called expbuild?
>=20
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>=20
> iD8DBQFBSY7mZDyR4hR8HnQRAg1kAKCMGguMcbpAdJj4WKwBjYIfFQ44tQCfQQZl
> Mp/QA3TPcZmDjp2v4pmhY/E=3D
> =3DLq/i
> -----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

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
> 

[jgrapht-developers] target for experimental

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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,
is it ok to include an ant target for the experimental files
which compiles into a new directory called expbuild?

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

iD8DBQFBSY7mZDyR4hR8HnQRAg1kAKCMGguMcbpAdJj4WKwBjYIfFQ44tQCfQQZl
Mp/QA3TPcZmDjp2v4pmhY/E=
=Lq/i
-----END PGP SIGNATURE-----

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

[jgrapht-developers] Adding multiple edges and loops

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

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

Hello,
don't you think it is inconsistent behavior to throw an exception
when trying to add a forbidden loop but simply returning null
when trying to add a multiple edge? Since the loop behavior
is not documented I think it is save to change this to returning=20
null as well. It would very much ease the creation of random=20
graphs I am currently working at.

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

iD8DBQFBSWnDZDyR4hR8HnQRAmQWAKCCbiSLbYUhxdlSw3GSTltJxsMmoQCfVZ7N
NlgRX8aP5mmbZN3yvcEEA5E=3D
=3DEv96
=2D----END PGP SIGNATURE-----

[jgrapht-developers] Subgraph issues

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

Hello,
 I have some issues concerning the Subgraph class:
1. Why doesn't Subgraph have a toString method (and why doesn't 
AbstractGraph simply have the toString method 
AbstractBaseGraph has)?

2. degreeOf returns the degree of the vertex in the base graph 
which is not asked for.

3. Subgraph should be able to be created as an induced subgraph
and keep track of this property. This can be done either by
changing the class or subclassing it.

4. Subgraph should be listenable as well such that one can create 
subgraphs of subgraphs.

I can do patches for some of the issues above, but wanted your opinions 
before coding.

Michael

RE: [jgrapht-developers] jGABL

[Barak N. <bar...@us...>]

> have You ever heard of jGABL?
> http://www.math.tu-berlin.de/jGABL/

nope, added to bookmarks.

> Does LGPL allow incorporating the source into another
> GPL project without explicit permission?

Although I'd always ask for explicit permission, I think LGPL and GPL don't
require it, as long as headers and copyright notice of source files remain
intact. 

[jgrapht-developers] jGABL

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

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

Hello,
have You ever heard of jGABL?
http://www.math.tu-berlin.de/jGABL/
I think it is a good project, it is LGPL and one could definitely=20
incoporate some of their code? I did already ask the
maintainer twice per mail but got no answer.
Does LGPL allow incorporating the source into another
GPL project without explicit permission?

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

iD8DBQFBPr2dZDyR4hR8HnQRAi00AKCbdphDFqCBtNo/h4x3HZhLInRSaACgsW45
BTIERxaGAT/XlTgGzsV877g=3D
=3DVc21
=2D----END PGP SIGNATURE-----

[jgrapht-developers] FASD project: Online survey launched

[<ben...@id...>]

Dear Open Source developer

I am doing a research project on "Fun and Software Development" in which I kindly invite you to participate.
You will find the online survey under http://fasd.ethz.ch/qsf/. The questionnaire consists of 53 questions and you will need about 15 minutes to complete it.

With the FASD project (Fun and Software Development) we want to define the motivational significance of fun when software developers decide to engage in Open Source projects. What is special about our research project is that a similar survey is planned with software developers in commercial firms. This procedure allows the immediate comparison between the involved individuals and the conditions of production of these two development models. Thus we hope to obtain substantial new insights to the phenomenon of Open Source Development.


With many thanks for your participation,
Benno Luthiger


PS:
The results of the survey will be published under http://www.isu.unizh.ch/fuehrung/blprojects/FASD/.
We have set up the mailing list fa...@we... for this study. Please see http://fasd.ethz.ch/qsf/mailinglist_en.html for registration to this mailing list.

_______________________________________________________________________

Benno Luthiger
Swiss Federal Institute of Technology Zurich
8092 Zurich

Mail: benno.luthiger(at)id.ethz.ch
_______________________________________________________________________

RE: [jgrapht-developers] edge ownership

[Barak N. <bar...@us...>]

> What is the reason for the edge ownership exclusivity?  Allowing edges
> to be aliased in more than one graph is generally useful (especially =
if
> they have some additional information associated with them).  And view
> graphs like SubGraph and AsUndirectedGraph implicitly violate the
> ownership rule.

That indeed useful and works well as long as no one implements an Edge =
that
allows setSource() or setTarget(), that can mess up the graph internals. =
On
the other hand, if total immutability of the edges was required as part =
of
the contract of Edge, then we loose much of the advantage of the =
sharing.=20

In order to protect the graph integrity, I have firstly implemented a =
hard
rule that "only the graph creates its edges" to allow it to promise the
source and target could not be modified (externally). That's why in =
previous
versions of Graph there was no addEdge(Edge) method.=20

That proved to be too restrictive, so I relaxed it a bit later, but I =
still
don't have a complete and coherent solution in mind, what will settle =
all
the (seemingly) contradicting requirements.=20

Any ideas?

Barak=20

RE: [jgrapht-developers] listener list cloning

[Barak N. <bar...@us...>]

> DefaultListenableGraph.clone clones the lists of listeners and
> associates them with the cloned graph.  Is this correct?  If I ask to
> listen to a graph, that doesn't mean I want to listen to its clones that
> I don't even know about.

Sounds very incorrect to me -- opened a bug report.
Other opinions?