incidencelistgraph.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.graph.ref ;

import jdsl.core.api.*;
import jdsl.core.ref.NodeSequence;
import jdsl.graph.api.*;



/**
 * An implementation of the Graph interface, including self-loops,
 * parallel edges, and mixed directed and undirected edges.  For
 * specifications of the methods, see the documentation of
 * the interfaces. The remainder of this description is about the
 * implementation.  
 * <p>
 *
 * The following is a high-level description of the design; low-level
 * details appear further below.  The graph is implemented via a list of
 * vertices and a list of edges.  The nodes of these "global" lists are the
 * vertices and edges of the graph, respectively. In addition to the
 * global lists of vertices and edges, each vertex has a "local" list of
 * its incident edges.  Thus, each edge participates
 * in two local lists (one for each endpoint) plus the global list.  Each
 * vertex participates in only the global list.  Although sequential
 * data structures are used to implement the graph, the graph
 * conceptually consists of unordered sets; no guarantee is made
 * about where in the various lists a given accessor appears.
 * <p>
 *
 * This design forces most of the methods' time complexities.  Insertion
 * and deletion of vertices and edges are constant-time because
 * the various doubly-linked lists can be modified in constant time.
 * Adjacency queries are typically O(degrees of vertices involved).
 * Iterations take time linear in the number of things iterated over.
 * <p>
 * 
 * The remainder of this description is about low-level details
 * of the design, and efficiency tradeoffs of alternate designs.
 * <p>
 * 
 * The global list of edges exists to avoid having the duplicates in
 * edges() that would result from asking all vertices for their incident
 * edges (each edge would appear twice).  For most other purposes, the
 * only global list required would be the vertex list.  An alternate
 * design would get rid of the global edge list and would do a
 * traversal to get edges().  This would save space at the cost of
 * increasing the complexity of edges() from O(E) to O(V+E).
 * <p>
 *
 * Both global lists are implemented with JDSL NodeSequences.  In
 * contrast, the local incidence lists at each vertex are implemented
 * "by hand," with links in the ILEdges, for space efficiency.
 * Internal methods that refer to those links also take a vertex, so
 * the edge knows which set of links is being referred to (the set for
 * one endpoint or the set for the other endpoint).  Each local list
 * includes a dummy edge to handle special cases (empty list,
 * iterating till end of list, inserting at beginning of list).
 * <p>
 * 
 * To avoid the space overhead of having the global lists' positions
 * point to vertex/edge objects, which would need to point back to
 * the positions, the positions *are* the vertices/edges.
 * This is accomplished by inheriting from the position implementation
 * of the NodeSequence (called FNSNode) and using the
 * posInsert* methods to put objects of the subclass
 * into the global lists.
 * <p>
 * 
 * Research issues.  The following are changes to the design that
 * could be made if experiments indicated they were worthwhile:
 * <ul>
 *   <li>Use caches and copy-on-write techniques in more methods
 *       that return iterators.  However, many graph algorithms
 *       iterate over a given set only once, so caching the iteration
 *       might just waste time and space.  It might also be
 *       difficult to determine when to invalidate a cache.
 *   <li>Use dictionaries to store some information, for example the
 *       adjacency lists, in order to have better running-time for
 *       adjacency queries -- for example, connectingEdges(V,V).  This 
 *       would improve asymptotic performance of adjacency queries
 *       at the expense of asymptotic penalties in modifications,
 *       and at the expense of constant-factor penalties everywhere.
 *   <li>Have vertices store 3 lists of edges, incoming, outgoing, and
 *       undirected, for faster iterations over categories of edges.
 *       However, this gives space overhead, and is faster only
 *       in the rare case of a graph with both directed and undirected edges.
 * </ul>
 *
 * @see Graph
 * @see Vertex
 * @see Edge
 * @see EdgeDirection
 *
 * @author Benoit Hudson
 * @author Mark Handy
 *
 * @version JDSL 2.1.1 
 */

public class IncidenceListGraph extends AbstractGraph
implements Graph, EdgeDirection {

    private NodeSequence allverts_ ;
    private NodeSequence alledges_ ;


    /**
     * Creates a new IncidenceListGraph with default parameters.
     * <p>
     * O(1)
     */
    public IncidenceListGraph() {
        super();
        allverts_ = new NodeSequence();
        alledges_ = new NodeSequence();
    }





    /************ [Positional] Container ***************/


    /**
     * O(1)
     */
    public Container newContainer() {
        return new IncidenceListGraph();
    }

    /**
     * O(1)
     */
    public Object replaceElement( Accessor p, Object newElement ) {
	if( allverts_.contains(p) ) return ( (ILVertex)p ).replaceElement( newElement );
	if( alledges_.contains(p) ) return ( (ILEdge)p ).replaceElement( newElement );
	throw new InvalidAccessorException( "Accessor not contained: " + p );
    }

    /** 
     * O(1) 
     */
     public boolean contains( Accessor p ) {
	return allverts_.contains(p) || alledges_.contains(p);
     }

    /**
     * O(V+E)
     */
    public ObjectIterator elements() {
	return new OO_to_O_MergerIterator(
					  allverts_.elements(),
					  alledges_.elements()
					  );
    }



    /************ InspectableGraph ***************/
    
    /**
     * O(1)
     */
    public int numVertices() {
        return allverts_.size() ;
    }

    /**
     * O(1)
     */
    public int numEdges() {
        return alledges_.size() ;
    }

    /**
     * O(V)
     */
    public VertexIterator vertices() {
	return new VertexIteratorAdapter( allverts_.positions() );
    }

    /**
      * O(1)
      */
    public Vertex aVertex() {
	if (allverts_.isEmpty()) return Vertex.NONE;
	return (Vertex)allverts_.first();
    }

    /**
     * O(E)
     */
    public EdgeIterator edges() {
	return new EdgeIteratorAdapter( alledges_.positions() );
    }
    
    /**
     * O(1)
     */
    public Edge anEdge() {
	if (alledges_.isEmpty()) return Edge.NONE;
	return (Edge)alledges_.first();
    }

    
    
    /**
     * O(1)
     */
    public int degree (Vertex v) throws InvalidAccessorException {
        return _checkVertex(v).degree();
    }

    /**
     * O(degree)
     */
    public int degree( Vertex v, int edgetype ) throws InvalidAccessorException {
	return _checkVertex(v).degree( edgetype );
    }
	
    
    /**
     * O(degree)
     */
    public EdgeIterator incidentEdges (Vertex v) throws
    InvalidAccessorException {
	return _checkVertex(v).incidentEdges( IN | OUT | UNDIR );
    }
    
    /**
     * O(degree)
     */
    public EdgeIterator incidentEdges( Vertex v, int edgetype ) throws
    InvalidAccessorException {
	return _checkVertex(v).incidentEdges( edgetype );
    }
    
    /**
     * O(1)
     */
    public Edge anIncidentEdge (Vertex v) throws InvalidAccessorException {
        Edge retval = _checkVertex(v).anEdge( IN | OUT | UNDIR );
	if( retval==null ) retval = Edge.NONE;
	return retval;
    }
    
    /**
     * O(degree)
     */
    public Edge anIncidentEdge( Vertex v, int edgetype ) throws 
    InvalidAccessorException {
	Edge retval = _checkVertex(v).anEdge( edgetype );
	if( retval==null ) retval = Edge.NONE;
	return retval;
    }


    /**  
     * O(1)
     */
    public Vertex[] endVertices (Edge e) {
        return _checkEdge(e).endpoints();
    }
    
    /** 
     * O(1)
     */
    public boolean areIncident(Vertex v, Edge e) {
	_checkVertex(v);
	Vertex [] ev = endVertices(e);
	return (ev[0] == v || ev[1] == v);
    }

    /** 
     * O(1)
     */
    public Vertex opposite (Vertex v, Edge e) {
	_checkVertex(v);
	Vertex[] ends = endVertices(e);
	if( ends[0]==v ) return ends[1];
	if( ends[1]==v ) return ends[0];
	throw new InvalidVertexException( "v not an endpoint of e" );
    }

    /**
     * O(1)
     */
    public Vertex origin(Edge e) {
	if(!isDirected(e))
	    throw new InvalidEdgeException("Undirected edge:\n"+ e);
	else
	    return endVertices(e)[0];
    }

    /**
     * O(1)
     */
    public Vertex destination(Edge e) {
	if(!isDirected(e))
	    throw new InvalidEdgeException("Undirected edge:\n"+ e);
	else
	    return endVertices(e)[1];
    }




    
    /*************** [Modifiable] Graph ******************/
    
    
    /**
     * O(1)
     */
    public Vertex insertVertex(Object elt) {
	return _insertVertex( elt );
    }

    /**
     * O(degree)
     */
    public Object removeVertex(Vertex v) throws InvalidAccessorException {
        _removeVertex( _checkVertex(v) );
	return v.element();
    }


    

    /**
     * O(1)
     */
    public Edge attachVertex(Vertex v, Object vertexInfo, Object edgeInfo)
    throws InvalidAccessorException {
	ILVertex ilv = _checkVertex(v);
        ILVertex newv = _insertVertex( vertexInfo );
        return _insertEdge( ilv, newv, edgeInfo, false );
    }

    /**
     * O(1)
     */
    public Edge attachVertexFrom(Vertex v, Object vertexInfo, Object edgeInfo)
    throws InvalidAccessorException {
	ILVertex ilv = _checkVertex(v);
        ILVertex newv = _insertVertex( vertexInfo );
        return _insertEdge( ilv, newv, edgeInfo, true);
    }

    /**
     * O(1)
     */
    public Edge attachVertexTo(Vertex v, Object vertexInfo, Object edgeInfo)
    throws InvalidAccessorException {
	ILVertex ilv = _checkVertex(v);
        ILVertex newv = _insertVertex( vertexInfo );
        return _insertEdge( newv, ilv, edgeInfo, true);
    }



    
    /**
     * O(1)
     */