jgrapht-developers — A discussion list for JGraphT developers.

[jgrapht-developers] RandomGraphGenerator behavior

[Charles F. <cf...@us...>]

It seems to me that the RandomGraphGenerator specification is incorrect.
It currently generates the same graph over and over on subsequent calls
to generateGraph(), and I argue that it should rather produce (probably)
different graphs on each call to generateGraph(). I don't recall any
discussion about the class, but it may have occured before I joined the
group. In any case, I need to extend RandomGraphGenerator, and I would
very much like to see its specification improved. :-)

The closest parallels that I can find in Java itself are Random and
SecureRandom, which generate random numbers as opposed to random graphs.
Their model is to construct a single instance of Random, and then to
generate a (probably) different random number on each subsequent method
invocation. It is possible to reseed the random number generator (or to
seed the constructor) to obtain duplicible results.

I argue that RandomGraphGenerator should do the same. It should be
possible to construct an instance either with or without specifying a
seed, and then to reseed the instance at will. But between reseedings,
succesive calls to generateGraph should create (probably) different
graphs.

I also propose that RandomGraphGenerator be turned into an interface
(following the specification outlined above, which I would be glad to
turn into code), which could then be implemented by the current
generator, as well as the currently experimental
UniformRandomGraphGenerator and PartiteRandomGraphGenerator (shouldn't
that be Bipartite?), in addition to some new RandomGraphGenerators that
I plan to write (RegularRandomGraphGenerator and
MOutRandomGraphGenerator to begin with, though
PreferentialAttachmentRandomGraphGenerator would be nice, if not
verbosely named).

Charles

-- 
My job is
Keeping faces clean
And nobody knows
De stubble
I've seen
Burma-Shave
http://burma-shave.org/jingles/1950/my_job_is

[jgrapht-developers] JGraphT Subversion migration complete

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

All file version history was migrated as well, so the CVS repository has 
been disabled.  Anyone who had commit access to CVS has been given 
commit access to SVN now.  As part of the migration, I also took care of 
renaming package org._3pq.jgrapht to org.jgrapht (per enhancement 
request #1381861).

Here's how to get the code (assuming you've installed the command-line 
svn tool).  First, you probably want to rename your current sandbox 
(e.g. to jgrapht.cvs) so you can start fresh.  Then, from the parent 
directory where you want to create the jgrapht directory:

svn co https://svn.sourceforge.net/svnroot/jgrapht/trunk jgrapht

You may need to tell it to accept an SSL certificate permanently.  Be 
sure to use the full URL (the sf.net abbreviation didn't work when I 
tried it).

When committing for the first time, I had to update my credentials, 
probably because I started in a clean directory.

JVS

[jgrapht-developers] migration from CVS to Subversion in progress

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

I have disabled CVS write access for everyone, and will add write access 
to SVN once the migration completes.

JVS

Re: [jgrapht-developers] 0.7.0

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

Right, I will change the checkin criteria in etc/project-policies.html 
to be more explicit:  it must compile with command-line ant.

Regardless of that, Hartmut, thanks for the checkin!  Once we get the 
build fixed I can start on some of the repackaging work that's been 
planned (including move to org.jgrapht and migration to Subversion).  We 
can keep investigating the generics "warts" in parallel.

JVS

Christian Hammer wrote:
> Hartmut Benz wrote:
> 
>> Hallo,
>>
>> I have just merged the Generics tree into the HEAD version and create two
>> new tags:
>>     vers_0_6_0_1    Immediately before the Merge
>>     vers_0_6_1        The merged version.
>>
>> "Down" to 206 generics-type-cast warnings now:
>> - alg (22 - some usage of equivalence classes untouched)
>> - experimental (35)
>> - ext (11)
>> - graph (18 - almost entirely related to the edge factories)
>> - traverse (1)
>> - util (3)
>> - testsrc (116)
>>
>> This move to generis turned out to be an order of magnitude more work tan
>> expected - even with eclipse helping a lot. As a consequence, I merged my
>> work back into the main stream and I'll ask *all* developers and
>> non-developers to help.
>> I am also no longer working with the project using jgrapht and thus 
>> will be
>> quite limited on the time I can spend working on jgrapht in the coming
>> months.
>>
>> The principle problems with the EdgeFactories remain. I have no immediate
>> solution to either removing the warnings currently there, or making the
>> whole construction with it type safe. Removing the default constructors,
>> which set problematic default factories, entirely is a solution, but that
>> question is probably better answered by large-scale users of jgrapht.
>> Another (drastic) option is to give the current edges the same status as
>> vertices, i.e., make them user objects and move the incidence/adjacency
>> relation into the graph object itself. This would effectively remove the
>> user-visible edge factory altogether.
>>
>> I am curious to hear opinions of others on this subject.
>>
>> Greetings and success
>>     Hartmut
>>
>>  
>>
> Hi,
> 
> Maybe it's not such a good idea to use Eclipse only. I just checked out 
> the most recent version an got about 12 errors using Suns java compiler:
> 
> "ConnectivityInspector.java": a type variable may not be followed by 
> other bounds at line 105, column 35
> "ConnectivityInspector.java": type parameter EE is not within its bound 
> at line 105, column 79
> "AsUndirectedGraph.java": a type variable may not be followed by other 
> bounds at line 97, column 39
> "GraphDelegator.java": incompatible types; found   : 
> java.util.List<capture of ? extends capture of ? extends E>, required: 
> java.util.List<? extends E> at line 203, column 60
> "GraphDelegator.java": incompatible types; found   : 
> java.util.List<capture of ? extends capture of ? extends E>, required: 
> java.util.List<? extends E> at line 219, column 60
> "AsUndirectedGraph.java": type parameter ED is not within its bound at 
> line 97, column 78
> ...
> 
> It seems the Eclipse compiler is not as strict as Suns.
> 
> Another point about the compiler warnings: I am not convinced that one 
> can really eliminate all those because there are definitely some points 
> in the code where the code itself is not 100% secure. Another problem 
> seems to be when one would like to cast e.g. a Graph<V,E> to a 
> DirectedGraph<V,DE> where E extends Edge<V> and DE extends DirEdge<V>. 
> It seems secure as DirectedGraph is defined as extends Graph<V,DE> but 
> I'm not sure if and how one can express it such that the type systems 
> accepts it.
> 
> By the way: there seems to be a solution proposed by Sun how to 
> integrate Factories into generics. I will do some experiments and send 
> you the results.
> 

Re: [jgrapht-developers] 0.7.0

[Christian H. <ha...@fm...>]

Hartmut Benz wrote:

>Hallo,
>
>I have just merged the Generics tree into the HEAD version and create two
>new tags:
>	vers_0_6_0_1	Immediately before the Merge
>	vers_0_6_1		The merged version.
>
>"Down" to 206 generics-type-cast warnings now:
>- alg (22 - some usage of equivalence classes untouched)
>- experimental (35)
>- ext (11)
>- graph (18 - almost entirely related to the edge factories)
>- traverse (1)
>- util (3)
>- testsrc (116)
>
>This move to generis turned out to be an order of magnitude more work tan
>expected - even with eclipse helping a lot. As a consequence, I merged my
>work back into the main stream and I'll ask *all* developers and
>non-developers to help.
>I am also no longer working with the project using jgrapht and thus will be
>quite limited on the time I can spend working on jgrapht in the coming
>months.
>
>The principle problems with the EdgeFactories remain. I have no immediate
>solution to either removing the warnings currently there, or making the
>whole construction with it type safe. Removing the default constructors,
>which set problematic default factories, entirely is a solution, but that
>question is probably better answered by large-scale users of jgrapht.
>Another (drastic) option is to give the current edges the same status as
>vertices, i.e., make them user objects and move the incidence/adjacency
>relation into the graph object itself. This would effectively remove the
>user-visible edge factory altogether.
>
>I am curious to hear opinions of others on this subject.
>
>Greetings and success
>	Hartmut
>
>  
>
Hi,

Maybe it's not such a good idea to use Eclipse only. I just checked out 
the most recent version an got about 12 errors using Suns java compiler:

"ConnectivityInspector.java": a type variable may not be followed by 
other bounds at line 105, column 35
"ConnectivityInspector.java": type parameter EE is not within its bound 
at line 105, column 79
"AsUndirectedGraph.java": a type variable may not be followed by other 
bounds at line 97, column 39
"GraphDelegator.java": incompatible types; found   : 
java.util.List<capture of ? extends capture of ? extends E>, required: 
java.util.List<? extends E> at line 203, column 60
"GraphDelegator.java": incompatible types; found   : 
java.util.List<capture of ? extends capture of ? extends E>, required: 
java.util.List<? extends E> at line 219, column 60
"AsUndirectedGraph.java": type parameter ED is not within its bound at 
line 97, column 78
...

It seems the Eclipse compiler is not as strict as Suns.

Another point about the compiler warnings: I am not convinced that one 
can really eliminate all those because there are definitely some points 
in the code where the code itself is not 100% secure. Another problem 
seems to be when one would like to cast e.g. a Graph<V,E> to a 
DirectedGraph<V,DE> where E extends Edge<V> and DE extends DirEdge<V>. 
It seems secure as DirectedGraph is defined as extends Graph<V,DE> but 
I'm not sure if and how one can express it such that the type systems 
accepts it.

By the way: there seems to be a solution proposed by Sun how to 
integrate Factories into generics. I will do some experiments and send 
you the results.

-- 
Christian Hammer
E-Mail: mailto:ha...@fm...
WWW: http://www.infosun.fmi.uni-passau.de/st/staff/hammer/

RE: [jgrapht-developers] 0.7.0

[Hartmut B. <Har...@gm...>]

Hallo,

I have just merged the Generics tree into the HEAD version and create two
new tags:
	vers_0_6_0_1	Immediately before the Merge
	vers_0_6_1		The merged version.

"Down" to 206 generics-type-cast warnings now:
- alg (22 - some usage of equivalence classes untouched)
- experimental (35)
- ext (11)
- graph (18 - almost entirely related to the edge factories)
- traverse (1)
- util (3)
- testsrc (116)

This move to generis turned out to be an order of magnitude more work tan
expected - even with eclipse helping a lot. As a consequence, I merged my
work back into the main stream and I'll ask *all* developers and
non-developers to help.
I am also no longer working with the project using jgrapht and thus will be
quite limited on the time I can spend working on jgrapht in the coming
months.

The principle problems with the EdgeFactories remain. I have no immediate
solution to either removing the warnings currently there, or making the
whole construction with it type safe. Removing the default constructors,
which set problematic default factories, entirely is a solution, but that
question is probably better answered by large-scale users of jgrapht.
Another (drastic) option is to give the current edges the same status as
vertices, i.e., make them user objects and move the incidence/adjacency
relation into the graph object itself. This would effectively remove the
user-visible edge factory altogether.

I am curious to hear opinions of others on this subject.

Greetings and success
	Hartmut

[jgrapht-developers] migration from CVS to Subversion

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

Subversion is now available for all Sourceforge projects.  We should 
plan a move over as part of the next release, together with changing 
from org._3pq.jgrapht to org.jgrapht.  Hartmut, to be safe, we should 
wait until all of your changes are merged over to the trunk.

Details from the sf.net announcement below.

JVS

Subversion General Availability
-------------------------------

The SourceForge.net team is pleased to announce the General Availability
of Subversion service to SourceForge.net-hosted projects, effective
2006-02-21. This service offering is in addition to our existing CVS
service; as with all of our services, projects may select (and enable in
the project admin pages) the portion of our offering that best meets
their needs.

We wish to extend our thanks to the many projects and developers who
have helped us to test our Subversion service as part of our six-week
beta, which completed last week. Our particular thanks go to these
projects, whose members provided substantial feedback regarding the
new service:

* Inkscape - http://sourceforge.net/projects/inkscape/
* DejaVu Fonts - http://sourceforge.net/projects/dejavu/
* ScummVM - http://sourceforge.net/projects/scummvm/
* evilnet - http://sourceforge.net/projects/evilnet/


Our Subversion service includes:

SSL-based Repository Access:
* Developer Subversion access via HTTPS, auth is requested when you
perform a write operation
* Anonymous Subversion access via HTTPS
* No sync delays between developer and anonymous Subversion access
* Per-developer access control over repository access (ACL support to be
added in the future) via the SourceForge.net permissions system

Web-based viewing:
* Web-based repository access via ViewVC (formerly known as ViewCVS)

On-demand self-service backups and mirroring capability:
* Read-only rsync access to the repository to permit backups and
remote mirroring

Ease of migration:
* Automated self-service migration of your SourceForge.net project CVS
repository, CVS tarball, or Subversion dump to our Subversion service

Well-considered add-ons to basic service:
* A selected set of hook scripts, including commit email support and
CIA bot support
* Statistics tracking of Subversion repository activity


Service may be enabled by project administrators in the "Subversion"
section of the Project Admin pages.

Complete service documentation is available at:
http://sf.net/docs/E09/

Documentation is provided for supported clients at:
http://sf.net/docs/F06/ for the command-line SVN client
http://sf.net/docs/F07/ for TortoiseSVN

Our support of Subversion has been based on substantial research and
testing in the past few months, which we have pursued specifically based
on requests from the community. SourceForge.net continues to consider
new technologies and evaluate community requests in further
strengthening our service offering.

RE: [jgrapht-developers] 0.7.0

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

Thanks for the update!

Regarding experimental, we already have separate ant targets compile and
exp.compile.  If we can get compile warning-free, that would be a big
step forward.  After that we would impose the rule that any code moving
out of experimental would have to be warning-free.

I'll contact the author of .util.equivalence (in case he's not reading
this) to see if he has any more tests available.

JVS

On Wed, 2006-01-25 at 23:46 +0100, Hartmut Benz wrote:
> I just treated the .util.equivalence and some of the dependent classes
> package for generics. Down to 74 generics-type-cast warnings now:
> - alg (19 - some usage of equivalence classes untouched)
> - experimental (35)
> - graph (18 - almost entirely related to the edge factories)
> - traverse (1)
> - util.permutation (1)
> 
> The JUnit tests still work OK, but I think the equivalence package (and the
> other classes) need some regression testing (by people that actually use
> them in previously working code - the test cases are insufficient).
> 
> Hartmut
> 
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=103432&bid=230486&dat=121642
> _______________________________________________
> jgrapht-developers mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-developers

RE: [jgrapht-developers] 0.7.0

[Hartmut B. <Har...@gm...>]

I just treated the .util.equivalence and some of the dependent classes
package for generics. Down to 74 generics-type-cast warnings now:
- alg (19 - some usage of equivalence classes untouched)
- experimental (35)
- graph (18 - almost entirely related to the edge factories)
- traverse (1)
- util.permutation (1)

The JUnit tests still work OK, but I think the equivalence package (and the
other classes) need some regression testing (by people that actually use
them in previously working code - the test cases are insufficient).

Hartmut

RE: [jgrapht-developers] 0.7.0

[Hartmut B. <Har...@gm...>]

Just an addition to my previous mail:
I just checked and as far as I can see there are 77 warnings regarding type
safety left. I consider most of them non-trivial. They are in
- alg (11)
- experimental (35)
- graph (18 - almost entirely related to the edge factories)
- traverse (1)
- util (12)

Parts of the code (e.g. permutations) explicitly go through Object Arrays,
which makes it hard to keep track of the generic type (there are no
generically typed arrays).

Hartmut

RE: [jgrapht-developers] 0.7.0

[Hartmut B. <Har...@gm...>]

About the state of the generics in the branch ivins_Generics_Pre0_7_0:

I have successfully removed quite a number of warnings relating to the
generics. Alas, there is still a lot of complaining from the compiler and
some seem to point to underlying problems of the package.

Changes introduced in the branch:
- org._3pq.jgrapht.DirEdge: Interface for directed edges
- a small number of JUnit tests


Things I think should happen for 0.7.0
======================================
- Rename edge.DirectedEdge to edge.DefaultDirectedEdge
- Rename DirectedWhightedEdge to DefaultDirectedWhightedEdge
- etc.
- Lots of places still with warnings
- Lots of "COMMENT ME" places asking for comments (with and without this
  string)
- Lots of JUnit test


Things I have problems with
==================
- EdgeFactories are tricky with generics,
  and more so in the context of sub-classes of graph and the default
  constructor. The warnings are in the Default*Graph classes.
As of now, I have not been able to declare and assign an edge factory to a
graph without a compiler warning. The reason, I think, is that the types of
generics are tested (and only testable) at compile time.
Any suggestions and help are welcome.

  A more serious problem occurs with sub-classing and the default
constructor: When you use or sub-class a graph using generics specifying
that you have edges of type EEEE and forget to feed it with the correct
EdgeFactory for EEEE you will get a runtime-error. John suggested we might
need to remove the default constructor entirely.

- Heaps - I don't understand sufficiently what is going on in there in order
to get it watertight with generics/type-safety. Maybe Michael can have a
look and help.


There a probably quite a number of other things I can't remember right now
(just back from a long vacation).
In the immediate future (4-6 weeks) I will not be able to do a lot of
programming with generics. Everyone feel free to update the branch whenever
you like.


Hartmut

[jgrapht-developers] [Fwd: JGraphT contribution : Bellman-Ford algorithm]

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

Guilluame Boulmi has contributed an implementation of the Bellman-Ford
shortest-path algorithm, so if you've got a directed graph with negative
edge weights, this is your lucky day.  

(Guillaume, I'm guessing your surname from your email address; if it's
incorrect, please let me know.  Also, do you have a sourceforge account,
and do you want CVS write access to jgrapht?)

I committed Guillaume's code into CVS after adding support for generics
and making a few changes to make it more similar to the existing
DijkstraShortestPath class.  However, the two still have some interface
differences, so next I will take a look at Guillaume's enhanced Dijkstra
code and see if it can be integrated.

I also added some unit tests.  I removed some French comments because
javac was complaining about them in UTF8, and my translation attempts
would have been worse than no comments at all :)

JVS

-------- Forwarded Message --------
> From: gu boulmi <bou...@ya...>
> To: js...@gm...
> Subject: JGraphT contribution : Bellman-Ford algorithm
> Date: Thu, 5 Jan 2006 11:42:10 +0100 (CET)
> 
>   Hi and happy new year,
> 
>   Please find attached the Bellman-Ford algorithm I
> have written using JGraphT objects. It could close the
> feature request 846561 I think.
> 
>   I have also written a new class for Dijkstra
> algorithm with dedicated DijkstraIterator.
> 
>   The iterator was designed such that it that could be
> subclassed in case the seen-vertex-container change or
> in case path-cost-computation changed (e.g. with
> vertex weights taken into account) or in case not all
> outgoing-edges should be looped over (we could decide
> some edges should not be part of the returned paths).
> 
>   Furthermore paths are not represented as edge-lists
> but as a linked-list of path-element, similar to the
> sub-optimality property of shortest paths.
> 
>   Although I have not used Java generics, I hope it
> could be included in the next release 0.7.
> 
>   Best regards,
> 
>   Guillaume
> 
> 
> 	
> 	
> 		
> ___________________________________________________________________________ 
> Nouveau : téléphonez moins cher avec Yahoo! Messenger. Appelez le monde entier à partir de 0,012 €/minute ! 
> Téléchargez sur http://fr.messenger.yahoo.com

[jgrapht-developers] 0.7.0

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

Hi Hartmut,

When you get a chance, could you post an update to this list on the
state of generics support and any core changes that are going to be
required?  I'd like to start making up a list of all of the proposed
alterations we've been talking about for the 0.7.0 release.

Also, Charles Fry has reserved the org.jgrapht domain name, so we'll be
renaming all of the packages accordingly.  This requires some
coordination now that branching is being used; we won't start the
renaming until all changes to generics have been integrated to the
trunk.

JVS

p.s. Charles, I'm missing the Burma-Shave jingles!

Re: [jgrapht-developers] dumping adjacency and laplacian matrices

[Charles F. <cf...@us...>]

>   Such a work is a very good news.

Good. Glad to hear that someone else will appreciate it. :-)

> You mentioned that matrix representations could in
> turn be
> analysed and manipulated by external matrix software.
> 
> Matrix Toolkits for Java (MTJ)
> http://rs.cipr.uib.no/mtj/ seems to be a candidate to
> be used to complement JGraphT.

Excelent. I mentioned it in the documentation, and will evaluate it
myself for my own graph matrix analysis.

> In this project a text file format is already used :
> it's the matrix Market text file formats 
> http://math.nist.gov/MatrixMarket/formats.html#MMformat.
> 
> I think it would be a good idea to read/write matrices
> in the same format.

It looks like they actually use the Coordinate Text File (one of
multiple Matrix Market text file formats). The current implementation
already uses a file format that is the same, except that it is missing
the header line. I'll work on allowing MatrixExporter to be configured
to support this format.

Charles

-- 
Be a modern
Paul Revere
Spread the news
From ear
To ear
Burma-Shave
http://burma-shave.org/jingles/1935/be_a_modern

RE: [jgrapht-developers] dumping adjacency and laplacian matrices

[gu b. <bou...@ya...>]

  Hi,

  Such a work is a very good news.

You mentioned that matrix representations could in
turn be
analysed and manipulated by external matrix software.

Matrix Toolkits for Java (MTJ)
http://rs.cipr.uib.no/mtj/ seems to be a candidate to
be used to complement JGraphT.

In this project a text file format is already used :
it's the matrix Market text file formats 
http://math.nist.gov/MatrixMarket/formats.html#MMformat.

I think it would be a good idea to read/write matrices
in the same format.

  
  Guillaume

--- Charles Fry <cf...@us...> a écrit :

> Hi,
> 
> Last week John invited me to join you, implementing
> myself some of the
> long list of features that I recently requested.
> While I shall initially
> be unable to implement at the same speed which I
> requested these
> features, I do hope to make some contributions to
> JGraphT, which I have
> already found to be enourmously useful, and which I
> anticipate using for
> years to come.
> 
> John suggested that I announce my proposed changes
> on this mailing list
> in an effort to solicit discussion on them prior to
> my implementation
> efforts. I will thus start with the first piece of
> functionality which I
> have already implemented externally, that I would
> like to add to
> JGraphT.
> 
> Specifically, I would like to add the ability to
> dump graphs into
> matrix representaitons which could in turn be
> analysed and manipulated
> by external matrix software. You can read more about
> this idea in the
> feature request number 1377955.
> 
> Sample output for the adjacency matrix would be:
> 
> 1 2 1
> 1 3 1
> 2 1 1
> 3 1 1
> 3 4 1
> 4 3 1
> 5 5 0
> 
> Sample output for the Laplacian matrix would be:
> 
> 1 1 2
> 1 2 -1
> 1 3 -1
> 2 2 1
> 2 1 -1
> 3 3 2
> 3 1 -1
> 3 4 -1
> 4 4 1
> 4 3 -1
> 5 5 0
> 
> The Laplacian could alternatively be in normalized
> form:
> 
>    http://mathworld.wolfram.com/LaplacianMatrix.html
> 
> John already suggested placing this in
> org._3pq.jgrapht.ext. Perhaps it
> could be called MatrixExporter? Possible static
> method names would be
> dumpAdjacencyMatrix and dumpLaplacianMatrix, but I'd
> love to hear other
> ideas.
> 
> Any feedback on this proposed functionality is
> welcome.
> 
> thanks,
> Charles
> 
> -- 
> At intersections
> Look each way
> A harp sounds nice
> But it's
> Hard to play
> Burma-Shave
> http://burma-shave.org/jingles/1941/at_intersections
> 
> 
>
-------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do
> you grep through log files
> for problems?  Stop!  Download the new AJAX search
> engine that makes
> searching your log files as easy as surfing the 
> web.  DOWNLOAD SPLUNK!
>
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
> _______________________________________________
> jgrapht-developers mailing list
> jgr...@li...
>
https://lists.sourceforge.net/lists/listinfo/jgrapht-developers
> 



	

	
		
___________________________________________________________________________ 
Nouveau : téléphonez moins cher avec Yahoo! Messenger ! Découvez les tarifs exceptionnels pour appeler la France et l'international.
Téléchargez sur http://fr.messenger.yahoo.com

Re: [jgrapht-developers] Edge vertex types

[Christian H. <ha...@fm...>]

John V. Sichi wrote:

>I just tried it exactly as you have it below and it worked for me with
>no compiler error.
>  
>
Hi,

No problems with my version, as well...
Should work like that

-- 
Christian Hammer
E-Mail: mailto:ha...@fm...
WWW: http://www.infosun.fmi.uni-passau.de/st/staff/hammer/

Re: [jgrapht-developers] Edge vertex types

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

I just tried it exactly as you have it below and it worked for me with
no compiler error.

Did you somehow pick up a type-erased version of one of the classes,
maybe a classpath problem?

JVS

On Wed, 2005-12-14 at 00:46 -0500, Charles Fry wrote:
> Hi,
> 
> I am getting an error when compiling the following block of code:
> 
> public class NeighborIndex<V, E extends Edge<V>> implements GraphListener<V, E>
> {
>    public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
>    {
>        E edge = e.getEdge();
>        V source = edge.getSource();
>    }
> }
> 
> The error is:
> 
>    incompatible types
>    found   : java.lang.Object
>    required: V
>            V source = edge.getSource();
>                                     ^
> 
> My understanding of generics suggests that the compiler should have
> already known that E extends Edge<V>, and should thus have expected V
> instead of Object in the above block of code. Obviously I was wrong. Any
> suggestions as to what I am missing, and how I can fix this?
> 
> thanks,
> Charles
> 

Re: [jgrapht-developers] obtaining neighbor sets

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

See CrossComponentIterator.createGraphSpecifics.  It uses (g instanceof
DirectedGraph) to decide whether to use outgoingEdgeOf or edgesOf during
traversals.

So you're correct regarding interactions through the Graph interface,
but DirectedGraph and UndirectedGraph are also significant interfaces in
JGraphT.

JVS  "And who is my neighbor?"

On Tue, 2005-12-13 at 21:51 -0500, Charles Fry wrote:
> Another question: Why is AsUndirectedGraph important? I see that
> ConnectivityInspector uses it to obtain an undirected view of a directed
> graph. As far as I can tell, the only practical implication of this is
> that it provides degreeOf, which doesn't exist for DirectedGraphs. But
> as far as I can tell, a DirectedGraph interacted with through the Graph
> interface will be indistinguishable from an UndirectedGraph. Am I
> missing something here?
> 
> thanks,
> Charles
> 
> -----Original Message-----
> > From: "John V. Sichi" <js...@gm...>
> > Subject: Re: [jgrapht-developers] obtaining neighbor sets
> > Date: Mon, 12 Dec 2005 22:20:40 -0800
> > To: Charles Fry <cf...@us...>
> > Cc: jgr...@li...
> > 
> > On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> > > John suggested that this be implemented as a GraphListener. I thought it
> > > could be named NeighborListener or something like that. The static
> > 
> > Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
> > just an implementation detail; the purpose is to maintain an efficient
> > index structure for answering queries.
> > 
> > > method could match that from GraphHelper except that for efficiency I
> > > would have liked it to return a Set instead of a List:
> > > 
> > >    Set neighborListOf(Graph g, Object vertex);
> > 
> > So neighborsOf instead of neighborListOf, right?
> > 
> > Be careful about the multigraph case, where removing an edge doesn't
> > necessarily imply removing a neighbor.
> > 
> > > Would I want two different classes, one for undirected graphs, and one
> > > for directed graphs (predecessorListOf and successorListOf)?
> > 
> > For ConnectivityInspector, what we did was:
> > 
> > - ConnectivityInspector calculates connectivity information without
> > regard for edge direction; so if you give it a directed graph, it
> > inspects an undirected view
> > 
> > - StrongConnectivityInspector calculates connectivity information taking
> > edge direction into account; you can't give it an undirected graph
> > 
> > So in your case, maybe NeighborIndex and DirectedNeighborIndex?
> > 
> > JVS
> > 
> > 
> 

Re: [jgrapht-developers] dumping adjacency and laplacian matrices

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

Another possibility is a parameter telling the exporter whether to
ignore/collapse vs. assert on detecting a loop or multi-edge.

It would be nice if there were a way to query a graph for these
properties.  In the case where they were not being enforced by the graph
implementation itself, the query would actually inspect the graph
content; in case the graph already knows this inspection could be
short-circuited.  Arranging this communication in a generic way so that
we don't end up with an explosion of interface combinations is the
tricky part.  Yet another enhancement request?

JVS

On Tue, 2005-12-13 at 19:04 -0500, Charles Fry wrote:
> Now that I'm getting a little deeper into this, I realized that a
> Laplacian matrix is only defined for "an undirected, unweighted graph
> without graph loops (i,i) or multiple edges from one node to another [1]."
> 
>    1. http://mathworld.wolfram.com/LaplacianMatrix.html
> 
> Currently there are interfaces for Directed and Undirected graphs, but
> no interfaces are used to mark Multigraphs or Pseudographs. It is thus
> impossible for me to tell beforehand whether or not the graph provided
> contains loops or multiple edges.
> 
> The possible solutions that I see to this are to:
> 
>  - Define interfaces that indicate when multiple edges or loops are
>    permitted in a graph, and explicitely check those, possibly issuing a
>    warning.
> 
>  - Ignore loops, and collapse multiple edges when creating the Laplacian
>    matrix.
> 
> I don't see any reason not to do the latter, although the former may
> still be beneficial for other reasons.
> 
> Thoughts?
> 
> Charles
> 

[jgrapht-developers] Edge vertex types

[Charles F. <cf...@us...>]

Hi,

I am getting an error when compiling the following block of code:

public class NeighborIndex<V, E extends Edge<V>> implements GraphListener<V, E>
{
   public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
   {
       E edge = e.getEdge();
       V source = edge.getSource();
   }
}

The error is:

   incompatible types
   found   : java.lang.Object
   required: V
           V source = edge.getSource();
                                    ^

My understanding of generics suggests that the compiler should have
already known that E extends Edge<V>, and should thus have expected V
instead of Object in the above block of code. Obviously I was wrong. Any
suggestions as to what I am missing, and how I can fix this?

thanks,
Charles

-- 
Half a pound
For
Half a buck
Come on shavers
You're in luck
Burma-Shave
http://burma-shave.org/jingles/1931/half_a_pound

Re: [jgrapht-developers] obtaining neighbor sets

[Charles F. <cf...@us...>]

Another question: Why is AsUndirectedGraph important? I see that
ConnectivityInspector uses it to obtain an undirected view of a directed
graph. As far as I can tell, the only practical implication of this is
that it provides degreeOf, which doesn't exist for DirectedGraphs. But
as far as I can tell, a DirectedGraph interacted with through the Graph
interface will be indistinguishable from an UndirectedGraph. Am I
missing something here?

thanks,
Charles

-----Original Message-----
> From: "John V. Sichi" <js...@gm...>
> Subject: Re: [jgrapht-developers] obtaining neighbor sets
> Date: Mon, 12 Dec 2005 22:20:40 -0800
> To: Charles Fry <cf...@us...>
> Cc: jgr...@li...
> 
> On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> > John suggested that this be implemented as a GraphListener. I thought it
> > could be named NeighborListener or something like that. The static
> 
> Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
> just an implementation detail; the purpose is to maintain an efficient
> index structure for answering queries.
> 
> > method could match that from GraphHelper except that for efficiency I
> > would have liked it to return a Set instead of a List:
> > 
> >    Set neighborListOf(Graph g, Object vertex);
> 
> So neighborsOf instead of neighborListOf, right?
> 
> Be careful about the multigraph case, where removing an edge doesn't
> necessarily imply removing a neighbor.
> 
> > Would I want two different classes, one for undirected graphs, and one
> > for directed graphs (predecessorListOf and successorListOf)?
> 
> For ConnectivityInspector, what we did was:
> 
> - ConnectivityInspector calculates connectivity information without
> regard for edge direction; so if you give it a directed graph, it
> inspects an undirected view
> 
> - StrongConnectivityInspector calculates connectivity information taking
> edge direction into account; you can't give it an undirected graph
> 
> So in your case, maybe NeighborIndex and DirectedNeighborIndex?
> 
> JVS
> 
> 

-- 
A beard
That's rough
And overgrown
is better than
A chaperone
Burma-Shave
http://burma-shave.org/jingles/1951/a_beard

Re: [jgrapht-developers] dumping adjacency and laplacian matrices

[Charles F. <cf...@us...>]

> MatrixExporter sounds good.  A pattern you might consider instead of
> static methods is to support "knob" methods for tweaking the formatting
> before the export, e.g.

Excelent.

Now that I'm getting a little deeper into this, I realized that a
Laplacian matrix is only defined for "an undirected, unweighted graph
without graph loops (i,i) or multiple edges from one node to another [1]."

   1. http://mathworld.wolfram.com/LaplacianMatrix.html

Currently there are interfaces for Directed and Undirected graphs, but
no interfaces are used to mark Multigraphs or Pseudographs. It is thus
impossible for me to tell beforehand whether or not the graph provided
contains loops or multiple edges.

The possible solutions that I see to this are to:

 - Define interfaces that indicate when multiple edges or loops are
   permitted in a graph, and explicitely check those, possibly issuing a
   warning.

 - Ignore loops, and collapse multiple edges when creating the Laplacian
   matrix.

I don't see any reason not to do the latter, although the former may
still be beneficial for other reasons.

Thoughts?

Charles

-- 
Drinking drivers--
Nothing worse
They put
The quart
Before the hearse
Burma-Shave
http://burma-shave.org/jingles/1959/drinking_drivers

Re: [jgrapht-developers] obtaining neighbor sets

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

On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> John suggested that this be implemented as a GraphListener. I thought it
> could be named NeighborListener or something like that. The static

Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
just an implementation detail; the purpose is to maintain an efficient
index structure for answering queries.

> method could match that from GraphHelper except that for efficiency I
> would have liked it to return a Set instead of a List:
> 
>    Set neighborListOf(Graph g, Object vertex);

So neighborsOf instead of neighborListOf, right?

Be careful about the multigraph case, where removing an edge doesn't
necessarily imply removing a neighbor.

> Would I want two different classes, one for undirected graphs, and one
> for directed graphs (predecessorListOf and successorListOf)?

For ConnectivityInspector, what we did was:

- ConnectivityInspector calculates connectivity information without
regard for edge direction; so if you give it a directed graph, it
inspects an undirected view

- StrongConnectivityInspector calculates connectivity information taking
edge direction into account; you can't give it an undirected graph

So in your case, maybe NeighborIndex and DirectedNeighborIndex?

JVS

Re: [jgrapht-developers] dumping adjacency and laplacian matrices

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

On Mon, 2005-12-12 at 14:29 -0500, Charles Fry wrote:
> John already suggested placing this in org._3pq.jgrapht.ext. Perhaps it
> could be called MatrixExporter? Possible static method names would be
> dumpAdjacencyMatrix and dumpLaplacianMatrix, but I'd love to hear other
> ideas.

MatrixExporter sounds good.  A pattern you might consider instead of
static methods is to support "knob" methods for tweaking the formatting
before the export, e.g.

String generateMatrixWithBrackets(Graph g)
{
    MatrixExporter exporter = new MatrixExporter();
    StringWriter sw = new StringWriter();
    exporter.setBrackets("[","]");
    exporter.exportAdjacencyMatrix(sw, g);
    return sw.toString();
}

Just a made-up example for an exporter which supports bracket
customizatoin.

JVS

[jgrapht-developers] obtaining neighbor sets

[Charles F. <cf...@us...>]

Hi,

The other new feature I wanted to work on was effeciently obtaining
(caching) nieghbor sets. Currently it is unnecessarily expensive to
obtain a node's neighbors. You can see full details at feature request
number 1376875.

John suggested that this be implemented as a GraphListener. I thought it
could be named NeighborListener or something like that. The static
method could match that from GraphHelper except that for efficiency I
would have liked it to return a Set instead of a List:

   Set neighborListOf(Graph g, Object vertex);

Would I want two different classes, one for undirected graphs, and one
for directed graphs (predecessorListOf and successorListOf)?

Thanks for any advice and suggestions.

Charles

-- 
Hardly a driver
Is now alive
Who passed
On hills
At 75
Burma-Shave
http://burma-shave.org/jingles/1939/hardly_a_driver