[jgrapht-users] AsWeightedGraph implementation with unit test

[Lucas S. <lscharen@d.umn.edu>]

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.*;

/**
  * <p>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.</p>
  *
  * <p>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.</p>
  *
  * <p>Note that edges returned by this graph's accessors are really  
just the
  * edges of the underlying directed graph.</p>
  *
  * <p>This graph does <i>not</i> 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.</p>
  *
  * @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 );
	}
}