jgrapht-developers

[jgrapht-developers] dumping adjacency and laplacian matrices

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

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

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

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

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