|
From: Lucas S. <lscharen@d.umn.edu> - 2007-09-10 07:15:14
|
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). * * <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 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). * * <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 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 |
