jgrapht-users Mailing List for JGraphT (Page 40)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

 Thank you, John, KShortestPaths from last release is what I need, works
great.
Elena

You can try the new KShortestPaths algorithm (use the version in the
latest release, 0.7.3).

JVS

Elena Grinberg wrote:
> Hi,
>  
> I have UndirectedGraph (may be with cycles) - and I need to find all 
> possible pathes between 2 vertexes. I think I need to change 
> BellmanFordIterator, but may be there is some existed code which I can use?
> 
> Thank you,
> eagrin
> 
> 
> ------------------------------------------------------------------------
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Hi,

I have UndirectedGraph (may be with cycles) - and I need to find all
possible pathes between 2 vertexes. I think I need to change
BellmanFordIterator, but may be there is some existed code which I can use?

Thank you,
eagrin

This is a maintenance release which includes a number of bugfixes and
contributions which have accumulated since the 0.7.2 release. You can
find a description of the changes here:

http://jgrapht.wikispaces.com/Release0.7.3

In particular, you can actually access the result of k-shortest-paths
now! Sorry about that package-access oversight in the last release.

JVS

Yes, either your edge class needs to extend DefaultWeightedEdge, or your 
graph implementation needs to override setEdgeWeight.

JVS

Maarten Th. Mulders wrote:
> Hi all,
> 
> As I am trying to work with weighted graphs, I've come across a problem I
> don't understand.
> My weighted graph contains vertices of type ISynsetID and edges of
> IPointer. The former gives no problems, but when I try to set the weight
> of an edge using the graph's setEdgeWeight method, I get an 
> ClassCastException: edu.mit.jwi.item.Pointer (that is the class that
> implements the IPointer interface).
> Looking through the source code, I found that it tries to cast my edge to
> a DefaultWeigtedEdge. I don't see the reason for that. Should my edge
> class extend DefaultWeightedEdge? I can't find that in the (java)docs, nor
> on the wiki.
> 
> Thanks in advance,
> 
> Maarten Th. Mulders
> 
> PS. Please excuse my last email, it was send accidentally send without
> contents.
> 
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

Hi all,

As I am trying to work with weighted graphs, I've come across a problem I
don't understand.
My weighted graph contains vertices of type ISynsetID and edges of
IPointer. The former gives no problems, but when I try to set the weight
of an edge using the graph's setEdgeWeight method, I get an 
ClassCastException: edu.mit.jwi.item.Pointer (that is the class that
implements the IPointer interface).
Looking through the source code, I found that it tries to cast my edge to
a DefaultWeigtedEdge. I don't see the reason for that. Should my edge
class extend DefaultWeightedEdge? I can't find that in the (java)docs, nor
on the wiki.

Thanks in advance,

Maarten Th. Mulders

PS. Please excuse my last email, it was send accidentally send without
contents.

Hi,

Part of an algorithm I'm implementing requires the computation of the 
maximum height of each vertex in the graph. (By the height of a vertex 
I mean the number of edges traversed between that vertex and a leaf 
reachable from that starting vertex via depth-first traversal.)

I can think of a straightforward algorithm for computing this metric 
using the available depth-first iterator, but I was wondering if 
there's something included in JGraphT that I'm not seeing that would 
facilitate the computation.

Thanks.

Randall Schulz

http://en.wikipedia.org/wiki/Semilattice

JGraphT doesn't have anything specifically for these, but I think it 
amounts to:

a) finding the extrema by looking for vertices with in-degree/out-degree 
0 (in-degree 0 for infinum, out-degree 0 for supremum)

b) verifying reachability of all other nodes from the extrema (directed 
DFS can be used to do this)

c) verifying that the graph is a DAG (you can use CycleDetector)

JVS

Randall R Schulz wrote:
> Hi,
> 
> I'm a bit naive on the mathematics of lattices, so I'm not sure this 
> question is well-formed, complete or sensible at all, so please bear 
> with me.
> 
> I will be implementing an algorithm that operates, in part, on a graph 
> structure, which I will probably represent using JGraphT. The 
> algorithm's correctness depends on the graph being an "upper 
> semilattice." Another related algorithm requires a "meet semilattice." 
> Finally, a variation requires only a "lattice."
> 
> How might I go about verifying that the graph meets these requirements 
> (any or all of them)? Is it something that would be facilitated by, or 
> perhaps directly available in the JGraphT library?
> 
> I didn't see anything obvious in the JGraphT documentation that 
> pertains, but that may again be a function of my ignorance.
> 
> 
> Thanks in advance.
> 
> 
> Randall Schulz
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2005.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

Hi Kyle,

I've already successfully transferred the domain from Charles to The 
Eigenbase Project (a non-profit set up for some of the other open source 
projects I'm involved with).

JVS

Kyle Lahnakoski wrote:
> Sure, I can take this on.  I hope it is just domain registration, and
> not the whole project.
> 
> 
> 
> Charles Fry wrote:
>> Hi,
>>
>> As some of you may recall, some time ago I registered jgrapht.org for
>> use by the project. Well, it is expiring soon, and given my lack of
>> involvment in the project, I'd prefer to pass it off to someone else.
>> Let me know who would be interested in taking over the domain
>> registration.
>>
>> thanks,
>> Charles
>>
>> -------------------------------------------------------------------------
>> SF.Net email is sponsored by: 
>> Check out the new SourceForge.net Marketplace.
>> It's the best place to buy or sell services for
>> just about anything Open Source.
>> http://sourceforge.net/services/buy/index.php
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>   
> 
> 

Hi,

I'm a bit naive on the mathematics of lattices, so I'm not sure this 
question is well-formed, complete or sensible at all, so please bear 
with me.

I will be implementing an algorithm that operates, in part, on a graph 
structure, which I will probably represent using JGraphT. The 
algorithm's correctness depends on the graph being an "upper 
semilattice." Another related algorithm requires a "meet semilattice." 
Finally, a variation requires only a "lattice."

How might I go about verifying that the graph meets these requirements 
(any or all of them)? Is it something that would be facilitated by, or 
perhaps directly available in the JGraphT library?

I didn't see anything obvious in the JGraphT documentation that 
pertains, but that may again be a function of my ignorance.

Thanks in advance.

Randall Schulz

Sure, I can take this on.  I hope it is just domain registration, and
not the whole project.

Charles Fry wrote:
> Hi,
>
> As some of you may recall, some time ago I registered jgrapht.org for
> use by the project. Well, it is expiring soon, and given my lack of
> involvment in the project, I'd prefer to pass it off to someone else.
> Let me know who would be interested in taking over the domain
> registration.
>
> thanks,
> Charles
>
> -------------------------------------------------------------------------
> SF.Net email is sponsored by: 
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>   

-- 
----------------------------------------------------------------------
Kyle Lahnakoski                                       ky...@ar...
(416) 892-7784                                    Arcavia Software Ltd

I've added a new interface to package org.jgrapht:

http://jgrapht.svn.sourceforge.net/viewvc/jgrapht/trunk/src/org/jgrapht/GraphPath.java?view=markup

This is to allow algorithms such as k-shortest-paths to return path 
information without exposing their internal data structures.

If you have comments on the interface, let me know so I can incorporate 
them before release in 0.7.3.  I'll also retrofit Dijkstra and 
Bellman-Ford to instantiate this interface for uniformity (leaving the 
existing edge-list methods for backwards compatibility).

JVS

Hi,

As some of you may recall, some time ago I registered jgrapht.org for
use by the project. Well, it is expiring soon, and given my lack of
involvment in the project, I'd prefer to pass it off to someone else.
Let me know who would be interested in taking over the domain
registration.

thanks,
Charles

Could you submit a small isolated unit test which demonstrates the problem?

JVS

Petr Holub wrote:
> Hi,
> 
> we've recenlty encountered a problem with encoding DirectedWeightedMultigraph
> using XMLEncoder. Basically, for XMLEncoder to work, the object needs to
> be Java Bean and implement Serializable. Does anybody has a clue why
> it shouldn't work on DirectedWeightedMultigraph?
> 
> When attempting to serialize, I get the following execeptions:
> 
> java.lang.InstantiationException: org.jgrapht.graph.DirectedWeightedMultigraph
> Continuing ...
> java.lang.Exception: XMLEncoder: discarding statement
> XMLEncoder.writeObject(DirectedWeightedMultigraph);
> Continuing ...
> 
> TIA,
> Petr
> 
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc.
> Still grepping through log files to find problems?  Stop.
> Now Search log events and configuration files using AJAX and a browser.
> Download your FREE copy of Splunk now >> http://get.splunk.com/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

Hi,

we've recenlty encountered a problem with encoding DirectedWeightedMultigraph
using XMLEncoder. Basically, for XMLEncoder to work, the object needs to
be Java Bean and implement Serializable. Does anybody has a clue why
it shouldn't work on DirectedWeightedMultigraph?

When attempting to serialize, I get the following execeptions:

java.lang.InstantiationException: org.jgrapht.graph.DirectedWeightedMultigraph
Continuing ...
java.lang.Exception: XMLEncoder: discarding statement
XMLEncoder.writeObject(DirectedWeightedMultigraph);
Continuing ...

TIA,
Petr

All,

Please find an implementation of a BipartiteGraph attached.  I've  
seen this requested a few times in the archives and, since I need it  
myself to build upon, I thought I'd post the implementation for  
feedback and comments.

Here are some items I think could be up for refinement and debate:

	1) I implemented BipartiteGraph as a GraphDelegator.  This seemed to  
be the path of least resistance and is consistent with Wiki's  
advice.  Is there a better place in the class hierarchy to put this?
	2) I track the membership of vertices to partitions by keeping a  
private Map.  This is potentially space inefficient since Vertex  
object references are duplicated, but I don't think there's a better  
way without assuming the type of the underlying graph.
	3) The traversal in the constructor to build a bipartite graph from  
the input graph is a bit messy.  Is a TraversalListener the best way  
to do this?  Or is there an existing utility method I missed that  
will do some of this work for me?

Most of the method are self-explanatory -- I just added checks to  
ensure that the bipartite property holds after each method.  I also  
added additional methods for adding vertices to specific partitions  
and getting the set of partition vertices.  I have junit tests for  
this code that I have not posted yet.

Obviously, there is quite a bit more documentation to write before  
it's in sufficient shape for submission, but I thought it would be  
good to get some feedback.

Thank you,
-Lucas

/**
  * A bipartite delegator enforces the partitioning of the graph  
vertices into
  * two disjoint sets.  An additional addVertex() method is added  
which allows
  * the assignment of vertices to a one partition or the other.  The  
addEdge()
  * methods are checked and the addition will fail if the bipartite  
constraints
  * are violated
  *
  * @author Lucas J. Scharenbroich
  * @since Oct. 5, 2007
  */

import java.util.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;
import org.jgrapht.event.*;

public class BipartiteGraph<V, E> extends GraphDelegator<V, E>
{
	public enum Partition {V1, V2};

	protected final Map<Partition, Set<V>> vertexSetMapping =
		new EnumMap<Partition, Set<V>>(Partition.class);

	/**
      * Constructor for BipartiteGraph.
      *
      * @param g the backing graph over which the bipartite topology
      * is to be constrained
      */
     public BipartiteGraph(final Graph<V, E> g)
     {
         super(g);

         vertexSetMapping.put(Partition.V1, new HashSet<V>());
         vertexSetMapping.put(Partition.V2, new HashSet<V>());

         // Run through the current set of vertices and edges and
         // place them arbitrarily is the two classes.  This is
         // really the best we can do with a general graph.  If
         // a bipartite violation is detected, throw an exception
         //
         // We can't just iterate over the edgeSet because this can
         // fail for cases like the following
         //
         //     e1       e2       e3
         // v1 ----> v2 ----> v3 <---- v4
         //
         // If the edges are visited in the order e1, e3, e2, then
         // we might partition the vertices as ((v1, v4), (v2, v3).
         // When e2 is encountered, v2 and v3 are in the same set
         // and the test fails, even though there is a bipartite
         // paritioning of the vertices, e.g. ((v1, v3), (v2, v4))

         GraphIterator<V, E> iterator = new DepthFirstIterator<V, E>(g);

         iterator.addTraversalListener(new BipartiteListener(g));

         while (iterator.hasNext()) {
         	iterator.next();
         }
     }

	/**
	 * A small, private class to walk a graph and partition it into two  
classes.
	 */
	private final class BipartiteListener extends  
TraversalListenerAdapter<V, E>
	{
		private final Graph<V, E> g;

		public BipartiteListener(Graph<V, E> g)
		{
			this.g = g;
		}

		public void edgeTraversed(EdgeTraversalEvent<V, E> e)
     	{
     		V source = g.getEdgeSource(e.getEdge());
     		V target = g.getEdgeTarget(e.getEdge());

     		Set<V> V1 = vertexSetMapping.get(Partition.V1);
     		Set<V> V2 = vertexSetMapping.get(Partition.V2);

     		boolean V1source = V1.contains(source);
     		boolean V1target = V1.contains(target);
     		boolean V2source = V2.contains(source);
     		boolean V2target = V2.contains(target);

     		// If both vertices are in either set, throw an exception
     		if ((V1source && V1target) || (V2source && V2target)) {
     			String msg = new StringBuffer()
     				.append( source )
     				.append(" and ")
     				.append(target)
     				.append( "are in the same parition").toString();

     			throw new IllegalArgumentException(msg) ;
     		}

     		// Make sure that at least one of the vertices has been seen
     		if (!( V1source || V2source || V1target || V2target)) {
     			String msg = "Free edge encountered in traversal";

     			throw new IllegalArgumentException(msg);
     		}

     		// If only the source has been seen, assign the target to the  
other set
     		if (V1source && !(V1target || V2target)) {
     			vertexSetMapping.get(Partition.V2).add(target);
     		}

     		if (V2source && !(V1target || V2target)) {
     			vertexSetMapping.get(Partition.V1).add(target);
     		}

     		// If only the target has been seen, assign the source to the  
other set
     		if (V1target && !(V1source || V2source))
     			vertexSetMapping.get(Partition.V2).add(source);

     		if (V2target && !( V1source || V2source))
     			vertexSetMapping.get(Partition.V1).add(source);
     	}

		public void vertexTraversed(VertexTraversalEvent<V> e)
		{
			V v = e.getVertex();

			// If this vertex has not been encountered before, assign it
			// to the first partition
			if (!vertexSetMapping.get(Partition.V1).contains(v) &&
				!vertexSetMapping.get(Partition.V2).contains(v))
			{
				vertexSetMapping.get(Partition.V1).add(v);
			}
		}
	}

	/**
	 * Finds the partition set that the vertex belongs to.  Return null if
	 * the vertex does not exist.
	 *
	 * @param v Vertex
	 * @return
	 */
     private Partition vertexPartition(V v)
     {
     	for (Map.Entry<Partition, Set<V>> entry :  
vertexSetMapping.entrySet())
     		if (entry.getValue().contains( v ))
     			return entry.getKey();

     	return null;
     }

     /**
      * Check that the source and target vertices are not in the same  
partition
      * before joining them.
      */
     @Override
     public E addEdge(V sourceVertex, V targetVertex)
     {
     	if (vertexPartition(sourceVertex).equals(vertexPartition 
(targetVertex))) {
     		return null;
     	}
     	else {
     		return super.addEdge(sourceVertex, targetVertex);
     	}
     }

     @Override
     public boolean addEdge(V sourceVertex, V targetVertex, E e)
     {
        	if (vertexPartition(sourceVertex).equals(vertexPartition 
(targetVertex))) {
        		String msg = "A Bipartite graph cannot join vertices in the  
same set";
     		throw new IllegalArgumentException(msg);
        	}

        	return super.addEdge( sourceVertex, targetVertex, e );     

     }

     @Override
     public boolean addVertex(V v)
     {
     	return addVertex(v, Partition.V1);
     }

     public boolean addVertex(V v, Partition partition)
     {
     	boolean rval = super.addVertex(v);

     	if (rval) {
     		vertexSetMapping.get(partition).add(v);
     	}

     	return rval;
     }

     /**
      * Find a vertex in a given partition
      *
      * @param v
      * @param partition
      * @return true if the vertex is in the partition
      */
     public boolean containsVertex(V v, Partition partition)
     {
     	return vertexSetMapping.get(partition).contains(v);
     }

     @Override
     public boolean removeVertex(V v)
     {
     	boolean rval = super.removeVertex(v);

     	if (rval) {
     		vertexSetMapping.get(vertexPartition(v)).remove(v);
     	}

     	return rval;
     }

     /**
      * Get the set of all vertices in one of the partitions
      * @param partition
      * @return a set of vertices
      */
     public Set<V> vertexSet(Partition partition)
     {
     	return Collections.unmodifiableSet(vertexSetMapping.get 
(partition));
     }
}

Note that you can find a description of the changes here:

http://jgrapht.wikispaces.com/Release0.7.2

JVS

John V. Sichi wrote:
> This is a maintenance release which includes a number of bugfixes and 
> contributions which have accumulated since the 0.7.1 release.
> 
> In addition, the 0.7.2 release drops support for the JRE 1.4 Retroweaver 
> backport.  The world has moved on, and the maintenance burden was no 
> longer justifiable.  If for whatever reason you are still unfortunate 
> enough to be stuck with JRE 1.4 deployments, you can either keep 
> using/maintaining JGraphT 0.7.1, or run retroweaver privately on 0.7.2 
> and beyond (this is very likely to stop working soon).
> 
> As always, many thanks to all who have contributed code, tests, bugs, 
> bugfixes, questions, and answers!  A special thanks to Trevor Harmon for 
> providing support for many incoming questions on the forums.
> 
> JVS
> 

This is a maintenance release which includes a number of bugfixes and
contributions which have accumulated since the 0.7.1 release.

In addition, the 0.7.2 release drops support for the JRE 1.4 Retroweaver
backport.  The world has moved on, and the maintenance burden was no
longer justifiable.  If for whatever reason you are still unfortunate
enough to be stuck with JRE 1.4 deployments, you can either keep
using/maintaining JGraphT 0.7.1, or run retroweaver privately on 0.7.2
and beyond (this is very likely to stop working soon).

As always, many thanks to all who have contributed code, tests, bugs,
bugfixes, questions, and answers!  A special thanks to Trevor Harmon for
providing support for many incoming questions on the forums.

JVS

I have committed this and the AsUnweighted implementations to 
Subversion.  I suppose an AsWeightedDirectedGraph version will also be 
needed and can share most of the implementation with AsWeightedGraph.

JVS

Lucas Scharenbroich wrote:
> Here is an implementation of the AsWeightedGraph class as described on 
> the Wiki.  There may be room for some debate on the semantics of the 
> class.  I have implemented it such that calls to setEdgeWeight pass 
> through to the backing graph if it implements the WeightedGraph 
> interface.  Call to setEdgeWeight will always update the passed edge 
> weight map in order to make the graph consistent with the sequence of 
> operations performed on it.
> 
> It may be better to copy the passed weight map in the constructor rather 
> than just keeping a reference to it.
> 
> Also, calls to getEdgeWeight will pass through to the backing graph only 
> is the specified edge does no exist in the weight map.
> 
> -Lucas

Thanks, I'll review and commit it along with the others.  It's great to 
see unit tests coming along with the code!

JVS

Here is an implementation of the AsWeightedGraph class as described  
on the Wiki.  There may be room for some debate on the semantics of  
the class.  I have implemented it such that calls to setEdgeWeight  
pass through to the backing graph if it implements the WeightedGraph  
interface.  Call to setEdgeWeight will always update the passed edge  
weight map in order to make the graph consistent with the sequence of  
operations performed on it.

It may be better to copy the passed weight map in the constructor  
rather than just keeping a reference to it.

Also, calls to getEdgeWeight will pass through to the backing graph  
only is the specified edge does no exist in the weight map.

-Lucas

/* ==========================================
  * JGraphT : a free Java graph-theory library
  * ==========================================
  *
  * Project Info:  http://jgrapht.sourceforge.net/
  * Project Creator:  Barak Naveh (http://sourceforge.net/users/ 
barak_naveh)
  *
  * (C) Copyright 2003-2007, by Barak Naveh and Contributors.
  *
  * This library is free software; you can redistribute it and/or  
modify it
  * under the terms of the GNU Lesser General Public License as  
published by
  * the Free Software Foundation; either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful, but
  * WITHOUT ANY WARRANTY; without even the implied warranty of  
MERCHANTABILITY
  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General  
Public
  * License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public  
License
  * along with this library; if not, write to the Free Software  
Foundation,
  * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  */
/*  ----------------------
  * AsWeightedGraph.java
  * ----------------------
  * (C) Copyright 2007, by John V. Sichi and Contributors.
  *
  * Original Author:  Lucas J. Scharenbroich
  *
  * $Id: $
  *
  * Changes
  * -------
  * 10-Sep-2007 : Initial revision (LJS);
  *
  */
package edu.uci.datalab.jgrapht;

import java.io.*;
import java.util.Map;
import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * A weighted view of the backing graph specified in the 
constructor. This graph
 * allows modules to apply algorithms designed for weighted graphs 
to an unweighted
 * graph by providing an explicit edge weight mapping.
 *
 * Query operations on this graph "read through" to the backing 
graph. Vertex
 * addition/removal and edge addition/removal are all supported (and
 * immediately reflected in the backing graph). Setting an edge weight
 * will pass the operation to the backing graph as well if the backing
 * graph implements the WeightedGraph interface. Setting an edge 
weight
 * will modify the weight map in order to maintain a consistent 
graph.
 *
 * Note that edges returned by this graph's accessors are really 
just the
 * edges of the underlying directed graph.
 *
 * This graph does not pass the hashCode and equals 
operations through
 * to the backing graph, but relies on <tt>Object</tt>'s <tt>equals</ 
tt> and
 * <tt>hashCode</tt> methods. This graph will be serializable if the 
backing
 * graph is serializable.
 *
 * @author Lucas J. Scharenbroich
 * @since Sep 10, 2007
 */

public class AsWeightedGraph<V, E>
	extends GraphDelegator<V, E>
	implements Serializable, WeightedGraph<V, E>
{
	//~ Static fields/initializers   
---------------------------------------------

     private static final long serialVersionUID = 9102007L;

     //~ Instance fields  
--------------------------------------------------------

     protected final Map<E, Double> weightMap;
     private final boolean isWeightedGraph;

     //~ Constructors  
-----------------------------------------------------------

     /**
      * Constructor for AsWeightedGraph.
      *
      * @param g the backing graph over which a weighted view is to
      * be created.
      * @param weightMap A mapping of edges to weights.  If an edge is
      * not present in the weight map, the edge weight for the  
underlying
      * graph is returned.
      */
     public AsWeightedGraph(Graph<V, E> g, Map<E, Double> weightMap)
     {
         super(g);
         this.weightMap = weightMap;

         // Remember is the backing graph implements the  
WeightedGraph interface
         this.isWeightedGraph = (g instanceof WeightedGraph);
     }

     //~ Methods  
----------------------------------------------------------------

     /**
      * @see WeightedGraph#setEdgeWeight(E e, double weight)
      */
     public void setEdgeWeight(E e, double weight)
     {
     	if ( isWeightedGraph )
     		super.setEdgeWeight(e, weight);

     	// Always modify the weight map.  It would be a terrible violation
     	// of the use contract to silently ignore changes to the weights.
     	if (weightMap != null)
     		weightMap.put(e, weight);
     }

     /**
      * @see Graph#getEdgeWeight(E e)
      */
     public double getEdgeWeight(E e)
     {
     	double weight;

     	// Always return the value from the weight map first and
     	// only pass the call through as a backup
     	if (weightMap != null && weightMap.containsKey(e))
     		weight = weightMap.get(e);
     	else
     		weight = super.getEdgeWeight(e);

         return weight;
     }
}

// End AsWeightedGraph.java

package edu.uci.datalab.jgrapht;

import java.util.*;
import junit.framework.JUnit4TestAdapter;
import static org.junit.Assert.*;
import org.junit.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;

public class AsWeightedGraphTest
{
	public SimpleWeightedGraph<String, DefaultWeightedEdge> weightedGraph;
	public SimpleGraph<String, DefaultEdge> unweightedGraph;

	@Before
	public void setUp()
	{
		weightedGraph   = new SimpleWeightedGraph<String,  
DefaultWeightedEdge>( DefaultWeightedEdge.class );
		unweightedGraph = new SimpleGraph<String, DefaultEdge> 
( DefaultEdge.class );

		// Create a very simple graph
		weightedGraph.addVertex("v1");
		weightedGraph.addVertex("v2");
		weightedGraph.addVertex("v3");

		unweightedGraph.addVertex("v1");
		unweightedGraph.addVertex("v2");
		unweightedGraph.addVertex("v3");

		weightedGraph.setEdgeWeight( weightedGraph.addEdge( "v1", "v2" ),   
1. );
		weightedGraph.setEdgeWeight( weightedGraph.addEdge( "v2", "v3" ),   
2. );
		weightedGraph.setEdgeWeight( weightedGraph.addEdge( "v3", "v1" ),   
3. );

		unweightedGraph.addEdge( "v1", "v2" );
		unweightedGraph.addEdge( "v2", "v3" );
		unweightedGraph.addEdge( "v3", "v1" );
	}

	@After
	public void tearDown()
	{
	}

	@Test
	public void test1()
	{
		Map<DefaultEdge, Double>         weightMap1 = new  
HashMap<DefaultEdge, Double>();
		Map<DefaultWeightedEdge, Double> weightMap2 = new  
HashMap<DefaultWeightedEdge, Double>();

		DefaultEdge e1 = unweightedGraph.getEdge( "v1", "v2" );
		DefaultEdge e2 = unweightedGraph.getEdge( "v2", "v3" );
		DefaultEdge e3 = unweightedGraph.getEdge( "v3", "v1" );

		DefaultWeightedEdge e4 = weightedGraph.getEdge( "v1", "v2" );
		DefaultWeightedEdge e5 = weightedGraph.getEdge( "v2", "v3" );
		DefaultWeightedEdge e6 = weightedGraph.getEdge( "v3", "v1" );

		weightMap1.put( e1, 9.0 );

		weightMap2.put( e4, 9.0 );
		weightMap2.put( e6, 8.0 );

		assertEquals( unweightedGraph.getEdgeWeight( e1 ),  
WeightedGraph.DEFAULT_EDGE_WEIGHT );

		WeightedGraph<String, DefaultEdge>         g1 = new  
AsWeightedGraph<String, DefaultEdge>( unweightedGraph, weightMap1 );
		WeightedGraph<String, DefaultWeightedEdge> g2 = new  
AsWeightedGraph<String, DefaultWeightedEdge>( weightedGraph,  
weightMap2 );

		assertEquals( g1.getEdgeWeight( e1 ), 9.0 );
		assertEquals( g1.getEdgeWeight( e2 ),  
WeightedGraph.DEFAULT_EDGE_WEIGHT );
		assertEquals( g1.getEdgeWeight( e3 ),  
WeightedGraph.DEFAULT_EDGE_WEIGHT );

		assertEquals( g2.getEdgeWeight( e4 ), 9.0 );
		assertEquals( g2.getEdgeWeight( e5 ), 2.0 );
		assertEquals( g2.getEdgeWeight( e6 ), 8.0 );

		g1.setEdgeWeight(e2, 5.0);
		g2.setEdgeWeight(e5, 5.0);

		assertEquals( g1.getEdgeWeight( e2 ), 5.0 );
		assertEquals( unweightedGraph.getEdgeWeight( e2 ),  
WeightedGraph.DEFAULT_EDGE_WEIGHT );

		assertEquals( g2.getEdgeWeight( e5 ), 5.0 );
		assertEquals( weightedGraph.getEdgeWeight( e5 ), 5.0 );
	}

	public static junit.framework.Test suite()
	{
		return new JUnit4TestAdapter( AsWeightedGraphTest.class );
	}
}

Thanks Lucas, I'll check these in and think of some more items for the 
low-hanging-fruit list.

JVS

Lucas Scharenbroich wrote:
> I picked up the jgrapht package this weekend for use in my University 
> studies and had the need to view a weighted directed graph as undirected 
> for performing a BreadthFirstSearch in a residual network for for an 
> Edmunds-Karp implementation.  I saw on the WIki that these classes have 
> been requested often and are considered a low hanging fruit.  As such, I 
> though I'd share my (trivial) implementation of the classes.
> 
> It appears that the two implementations are needed because the 
> Disjkstra's Shorted Path implementation would not respect the edges in a 
> directed graph unless the graph implements the DirectedGraph interface.
> 
> Feedback is welcome.  As I said, I've only been using the library for a 
> few hours and am interested in learning it so I can contribute some code 
> back.  
> 
> -Lucas

I picked up the jgrapht package this weekend for use in my University  
studies and had the need to view a weighted directed graph as  
undirected for performing a BreadthFirstSearch in a residual network  
for for an Edmunds-Karp implementation.  I saw on the WIki that these  
classes have been requested often and are considered a low hanging  
fruit.  As such, I though I'd share my (trivial) implementation of  
the classes.

It appears that the two implementations are needed because the  
Disjkstra's Shorted Path implementation would not respect the edges  
in a directed graph unless the graph implements the DirectedGraph  
interface.

Feedback is welcome.  As I said, I've only been using the library for  
a few hours and am interested in learning it so I can contribute some  
code back.

-Lucas

/* ==========================================
  * JGraphT : a free Java graph-theory library
  * ==========================================
  *
  * Project Info:  http://jgrapht.sourceforge.net/
  * Project Creator:  Barak Naveh (http://sourceforge.net/users/ 
barak_naveh)
  *
  * (C) Copyright 2003-2007, by Barak Naveh and Contributors.
  *
  * This library is free software; you can redistribute it and/or  
modify it
  * under the terms of the GNU Lesser General Public License as  
published by
  * the Free Software Foundation; either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful, but
  * WITHOUT ANY WARRANTY; without even the implied warranty of  
MERCHANTABILITY
  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General  
Public
  * License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public  
License
  * along with this library; if not, write to the Free Software  
Foundation,
  * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  */
/*  ----------------------
  * AsUnweightedGraph.java
  * ----------------------
  * (C) Copyright 2007, by John V. Sichi and Contributors.
  *
  * Original Author:  John V. Sichi
  * Contributor(s):   Lucas J. Scharenbroich
  *
  * $Id: $
  *
  * Changes
  * -------
  * 7-Sep-2007 : Initial revision (LJS);
  *
  */
package edu.uci.datalab.jgrapht;

import java.io.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * An unweighted view of the backing weighted graph specified in the
 * constructor. This graph allows modules to apply algorithms 
designed for
 * unweighted graphs to a weighted graph by simply ignoring edge 
weights.
 *
 * Query operations on this graph "read through" to the backing 
graph. Vertex
 * addition/removal and edge addition/removal are all supported (and
 * immediately reflected in the backing graph).
 *
 * Note that edges returned by this graph's accessors are really 
just the
 * edges of the underlying directed graph.
 *
 * This graph does not pass the hashCode and equals 
operations through
 * to the backing graph, but relies on <tt>Object</tt>'s <tt>equals</ 
tt> and
 * <tt>hashCode</tt> methods. This graph will be serializable if the 
backing
 * graph is serializable.
 *
 * @author Lucas J. Scharenbroich
 * @since Sep 7, 2007
 */

public class AsUnweightedDirectedGraph<V, E>
	extends GraphDelegator<V, E>
	implements Serializable, DirectedGraph<V, E>
{
	//~ Static fields/initializers   
---------------------------------------------

     private static final long serialVersionUID = 9072007L;

     //~ Constructors  
-----------------------------------------------------------

     /**
      * Constructor for AsUnweightedGraph.
      *
      * @param g the backing graph over which an unweighted view is to
      * be created.
      */
     public AsUnweightedDirectedGraph(DirectedGraph<V, E> g)
     {
         super(g);
     }

     //~ Methods  
----------------------------------------------------------------

     /**
      * @see Graph#getEdgeWeight(E e)
      */
     public double getEdgeWeight(E e)
     {
         return WeightedGraph.DEFAULT_EDGE_WEIGHT;
     }
}

// End AsUnweightedDirectedGraph.java

/* ==========================================
  * JGraphT : a free Java graph-theory library
  * ==========================================
  *
  * Project Info:  http://jgrapht.sourceforge.net/
  * Project Creator:  Barak Naveh (http://sourceforge.net/users/ 
barak_naveh)
  *
  * (C) Copyright 2003-2007, by Barak Naveh and Contributors.
  *
  * This library is free software; you can redistribute it and/or  
modify it
  * under the terms of the GNU Lesser General Public License as  
published by
  * the Free Software Foundation; either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful, but
  * WITHOUT ANY WARRANTY; without even the implied warranty of  
MERCHANTABILITY
  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General  
Public
  * License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public  
License
  * along with this library; if not, write to the Free Software  
Foundation,
  * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  */
/*  ----------------------
  * AsUnweightedGraph.java
  * ----------------------
  * (C) Copyright 2007, by John V. Sichi and Contributors.
  *
  * Original Author:  John V. Sichi
  * Contributor(s):   Lucas J. Scharenbroich
*
  * $Id: $
  *
  * Changes
  * -------
  * 7-Sep-2007 : Initial revision (LJS);
  *
  */
package edu.uci.datalab.jgrapht;

import java.io.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * An unweighted view of the backing weighted graph specified in the
 * constructor. This graph allows modules to apply algorithms 
designed for
 * unweighted graphs to a weighted graph by simply ignoring edge 
weights.
 *
 * Query operations on this graph "read through" to the backing 
graph. Vertex
 * addition/removal and edge addition/removal are all supported (and
 * immediately reflected in the backing graph).
 *
 * Note that edges returned by this graph's accessors are really 
just the
 * edges of the underlying directed graph.
 *
 * This graph does not pass the hashCode and equals 
operations through
 * to the backing graph, but relies on <tt>Object</tt>'s <tt>equals</ 
tt> and
 * <tt>hashCode</tt> methods. This graph will be serializable if the 
backing
 * graph is serializable.
 *
 * @author Lucas J. Scharenbroich
 * @since Sep 7, 2007
 */

public class AsUnweightedGraph<V, E>
	extends GraphDelegator<V, E>
	implements Serializable
{
	//~ Static fields/initializers   
---------------------------------------------

     private static final long serialVersionUID = 9072007L;

     //~ Constructors  
-----------------------------------------------------------

     /**
      * Constructor for AsUnweightedGraph.
      *
      * @param g the backing graph over which an unweighted view is to
      * be created.
      */
     public AsUnweightedGraph(Graph<V, E> g)
     {
         super(g);
     }

     //~ Methods  
----------------------------------------------------------------

     /**
      * @see Graph#getEdgeWeight(E e)
      */
     public double getEdgeWeight(E e)
     {
         return WeightedGraph.DEFAULT_EDGE_WEIGHT;
     }
}

// End AsUnweightedGraph.java

Hi,
I faced a same problem before.=20
=20
I tried serializing the model of JGraph. It worked fine.
=20
regards,
Suren

________________________________

From: jgr...@li... on behalf of Tanton Gibbs
Sent: Sat 8/11/2007 6:15 AM
To: jgr...@li...
Subject: [jgrapht-users] serializing a graph

I want to store my jgrapht graph in a database.  I was going to use an
exporter and store it in GraphML, GML, or DOT format (it doesn't
really matter the format).  However, I don't know how to create the
graph from the serialized format.  I can write the code to do it, but
I'd rather use someone else's :-)  Can anyone tell me if there exists
code to create a graph that has been created via an exporter?  Or, are
any of the graph classes serializable?

Thanks!
Tanton

-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >>  http://get.splunk.com/
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=20
Disclaimer:

This message and the information contained herein is proprietary and=
 confidential and subject to the Tech Mahindra policy statement, you may=
 review the policy at <a href=
=3D"http://www.techmahindra.com/Disclaimer.html">http://www.techmahindra.co=
m/Disclaimer.html</a> externally and <a href=
=3D"http://tim.techmahindra.com/Disclaimer.html">http://tim.techmahindra.co=
m/Disclaimer.html</a> internally within Tech Mahindra.

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

2003	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct (2)	Nov	Dec
2004	Jan (1)	Feb	Mar	Apr	May	Jun (1)	Jul (1)	Aug	Sep (1)	Oct	Nov	Dec (2)
2005	Jan	Feb (1)	Mar (5)	Apr (1)	May	Jun (12)	Jul (6)	Aug (7)	Sep (2)	Oct	Nov (1)	Dec
2006	Jan (4)	Feb (3)	Mar (2)	Apr (3)	May (6)	Jun (2)	Jul (3)	Aug (12)	Sep (6)	Oct (3)	Nov (12)	Dec
2007	Jan (6)	Feb	Mar (6)	Apr (8)	May (2)	Jun (8)	Jul (2)	Aug (3)	Sep (7)	Oct (3)	Nov	Dec (1)
2008	Jan (11)	Feb (4)	Mar (8)	Apr (3)	May (4)	Jun (1)	Jul	Aug (3)	Sep (1)	Oct (4)	Nov (5)	Dec (5)
2009	Jan (3)	Feb (12)	Mar (14)	Apr (9)	May (8)	Jun (1)	Jul (4)	Aug (10)	Sep	Oct (10)	Nov	Dec (4)
2010	Jan (9)	Feb (16)	Mar (14)	Apr (19)	May (1)	Jun (3)	Jul (17)	Aug (9)	Sep (4)	Oct (4)	Nov (11)	Dec (8)
2011	Jan (10)	Feb (11)	Mar (10)	Apr (14)	May (6)	Jun (8)	Jul (9)	Aug (11)	Sep (13)	Oct (7)	Nov (9)	Dec (1)
2012	Jan (5)	Feb (14)	Mar (4)	Apr (25)	May (18)	Jun (18)	Jul (3)	Aug (6)	Sep (3)	Oct (16)	Nov (5)	Dec (12)
2013	Jan (1)	Feb (6)	Mar (14)	Apr (34)	May (9)	Jun (3)	Jul (8)	Aug	Sep (10)	Oct (11)	Nov (11)	Dec (15)
2014	Jan (2)	Feb (6)	Mar (11)	Apr (12)	May (6)	Jun (7)	Jul	Aug (4)	Sep (1)	Oct (1)	Nov (5)	Dec (6)
2015	Jan (15)	Feb (4)	Mar (7)	Apr (8)	May (1)	Jun (18)	Jul (27)	Aug (13)	Sep (4)	Oct (8)	Nov (7)	Dec (6)
2016	Jan (4)	Feb (5)	Mar	Apr (15)	May (5)	Jun (4)	Jul (1)	Aug (1)	Sep (7)	Oct (2)	Nov (4)	Dec (2)
2017	Jan (7)	Feb (1)	Mar (17)	Apr (2)	May (1)	Jun	Jul	Aug (3)	Sep (3)	Oct	Nov (5)	Dec (6)
2018	Jan (23)	Feb (17)	Mar (4)	Apr (5)	May (6)	Jun (3)	Jul (5)	Aug (2)	Sep (3)	Oct (2)	Nov (5)	Dec
2019	Jan (1)	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2020	Jan	Feb (2)	Mar	Apr (1)	May (1)	Jun (8)	Jul (8)	Aug	Sep (2)	Oct (9)	Nov	Dec (1)
2021	Jan	Feb (4)	Mar (2)	Apr	May	Jun	Jul	Aug (3)	Sep (3)	Oct (3)	Nov (1)	Dec
2023	Jan	Feb	Mar	Apr	May (2)	Jun	Jul	Aug	Sep	Oct (4)	Nov	Dec
2024	Jan	Feb	Mar	Apr (1)	May	Jun (1)	Jul	Aug	Sep	Oct	Nov	Dec

jgrapht-users Mailing List for JGraphT (Page 40)

jgrapht-users — JGraphT user list.