incidencelistgraph.java

Java数据结构开发包

    public Edge insertEdge (Vertex v1, Vertex v2, Object elt) throws
    InvalidAccessorException {
	ILVertex ilv1 = _checkVertex(v1);
	ILVertex ilv2 = _checkVertex(v2);
        return _insertEdge( ilv1, ilv2, elt, false);
    }

    /**
     * O(1)
     */
    public Edge insertDirectedEdge (Vertex v1, Vertex v2, Object elt) throws
    InvalidAccessorException {
	ILVertex ilv1 = _checkVertex(v1);
	ILVertex ilv2 = _checkVertex(v2);
        return _insertEdge( ilv1, ilv2, elt, true);
    }

    /**
     * O(1)
     */
    public Object removeEdge (Edge e) throws InvalidAccessorException {
        ILEdge edge = _checkEdge(e);
        _removeEdge(edge);
	return e.element();
    }




   /**
     * O(1)
     */
    public Vertex splitEdge(Edge e, Object elt) throws
    InvalidAccessorException {
	ILEdge ile = _checkEdge(e);

        // create the new midpoint
        ILVertex newv = _insertVertex(elt);

	// useful info about old edge
	boolean isDir = ile.isDir();
        ILVertex[] endpts = ile.endpoints();

        // insert new edges between endpoints and new midpoint
        _insertEdge( endpts[0], newv, null, isDir );
        _insertEdge( newv, endpts[1], null, isDir );

        // remove old edge, return new vertex
        _removeEdge(ile);
        return newv ;
    }


    /**
     * Note: the "two" edges incident on v cannot be the same edge.  That is, v
     * is technically of degree 2 if it has a single self-loop and is
     * otherwise isolated, but it is impossible to unsplit that
     * edge-vertex-edge combination, so we throw IVE in that case.
     * <p>
     * O(1)
     */
    public Edge unsplitEdge (Vertex v, Object o) throws
    InvalidAccessorException, InvalidVertexException {
        ILVertex ilv = _checkVertex(v);
	
	// make sure v's degree is right
	if(ilv.degree()!=2) throw new InvalidVertexException
				("trying to unsplitEdge on vertex of degree " + ilv.degree());
	
	// get the 2 edges and 2 vertices associated with v
	EdgeIterator edges = incidentEdges(v);
	Edge e1 = edges.nextEdge();
	Edge e2 = edges.nextEdge();
	assert !edges.hasNext()
	  : "v of degree 2 has more than 2 incidentEdges()";
	// make sure this isn't a lone vertex with a self-loop
	if (e1==e2) throw new InvalidVertexException
			("trying to unsplitEdge on a vertex with only a self-loop");
	Vertex v1 = opposite(v, e1);
	Vertex v2 = opposite(v, e2);
	
	// decide whether to direct the new edge (and if so, make sure
	// v1 is the origin of the new edge, swapping v1 and v2 if necessary).
	boolean isdirected = false;
	if( isDirected(e1) && isDirected(e2) ) { 
	    if( origin(e1)==origin(e2) || destination(e1)==destination(e2) ) {
		// the edges are inconsistently directed
		isdirected = false;
	    }
	    else {
		isdirected = true;
		if( destination(e1)==v1 ) {
		    // swap the points for the call to insertDirectedEdge(.)
		    Vertex vtemp = v1 ;
		    v1 = v2 ;
		    v2 = vtemp ;
		}
	    }
	}
	// else isdirected==false because e1 or e2 is undirected    
	
	// remove the old vertex and incident edges, and add an edge
	_removeVertex(ilv);
	return _insertEdge( (ILVertex)v1, (ILVertex)v2, o, isdirected);
    }
    

    
    
    /**
     * O(1)
     */
    public boolean isDirected(Edge e) {
        return _checkEdge(e).isDir();
    }

    /**
     * O(1)
     */
    public void setDirectionFrom(Edge e, Vertex v) {
	_checkVertex(v);
        _checkEdge(e).setDirectionFrom(v);
    }

    /**
     * O(1)
     */
    public void setDirectionTo(Edge e, Vertex v) {
	_checkVertex(v);
        _checkEdge(e).setDirectionTo(v);
    }

    /**
     * O(1)
     */
    public void makeUndirected(Edge e) {
        _checkEdge(e).makeUndirected();
    }

    /**
     * O(1)
     */
    public void reverseDirection(Edge e) {
	ILEdge ile = _checkEdge(e);
        if( ile.isDir() )  ile.swapEndpoints();
        else throw new InvalidEdgeException("trying to reverse undirected edge");
    }



    public String toString() {
	return jdsl.graph.ref.ToString.stringfor(this);
    }




    

    /*********************** private helper methods ********************/

    

    

    // O(1)
    private ILVertex _insertVertex( Object elt ) {
	ILVertex vert = new ILVertex( elt );
        allverts_.posInsertLast( vert );
        return vert;
    }

    // O(1)
    private ILEdge _insertEdge( ILVertex v1, ILVertex v2, Object elt, boolean isDir) {
        ILEdge ile;
	if( v1==v2 ) ile = new ILLoopEdge( v1, elt, isDir );
	else ile = new ILNormalEdge( v1, v2, elt, isDir );
        alledges_.posInsertLast( ile );
        return ile ;
    }

    // O(degree)
    // overhead of multiple casts could be avoided by moving this
    // functionality to ILVertex
    private void _removeVertex( ILVertex vert ) {
        EdgeIterator pe = vert.incidentEdges( IN | OUT | UNDIR );
        while(pe.hasNext()) {
	    // strange-seeming containment check to guard against removing
	    // a self-loop twice:
	    if( alledges_.contains(pe.nextEdge()) ) _removeEdge( (ILEdge)pe.edge() );
	}
        allverts_.remove(vert);
    }

    // O(1)
    private void _removeEdge(ILEdge edge) {
	edge.detach();
        alledges_.remove(edge);
    }	

    // make sure vertex is valid, and cast it to implementation type
    private ILVertex _checkVertex( Vertex v ) {
	if( v==null ) throw new InvalidAccessorException
			  ( "vertex is null" );
	if( ! (v instanceof ILVertex) ) throw new InvalidAccessorException
					  ("invalid vertex class (" + v.getClass() + ")");
	if( ! allverts_.contains(v) ) throw new InvalidAccessorException
						   ("vertex belongs to a different graph");
	return (ILVertex)v;
    }

    // make sure edge is valid, and cast it to implementation type
    private ILEdge _checkEdge( Edge e ) {
	if( e==null ) throw new InvalidAccessorException
			  ( "edge is null" );
	if( ! (e instanceof ILEdge) ) throw new InvalidAccessorException
					  ("invalid edge class (" + e.getClass() + ")");
	if( ! alledges_.contains(e) ) throw new InvalidAccessorException
						   ("edge belongs to a different graph");
	return (ILEdge)e;
    }



    

    

    // ===============================================
    // nested classes
    


    /**
     * Dummy node in each vertex's list of edges, so the vertex and
     * the real edges 
     * always have something to point to (avoids special-casing on
     * ends of edge list and on detached vertices).  The interesting
     * methods take vertices (ignored by the dummy) because
     * real edges have two endpoints, so they need to know
     * which endpoint's list is being talked about.
     */
    private static class ILEdgeDummy extends ILEdge {
	private ILEdge next_, prev_;
	
	ILEdgeDummy() { next_ = prev_ = this; }
	ILEdge next() { return next_; }
	ILEdge next( Vertex whichEnd ) { return next_; }
	ILEdge prev( Vertex whichEnd ) { return prev_; }
	void setNext( Vertex whichEnd, ILEdge n ) { next_ = n; }
	void setPrev( Vertex whichEnd, ILEdge n ) { prev_ = n; }
	public String toString() { return "dummy edge!  you should never see this!"; }
	
	// using any other method indicates a bug:
	
	boolean isDir() {
	    assert false : "trying to use dummy node";
	    return false; }
        void makeDirected() {
	  assert false : "trying to use dummy node";
	}
        void makeUndirected() {
	  assert false : "trying to use dummy node";
	}
	boolean isSelfLoop() {
	    assert false : "trying to use dummy node";
	    return false; }
	ILVertex[] endpoints() {
	    assert false : "trying to use dummy node";
	    return null; }
	ILVertex origin() {
	    assert false : "trying to use dummy node";
	    return null;  }
	ILVertex destination() {
	    assert false : "trying to use dummy node";
	    return null;  }
        void setDirectionFrom(Vertex v) {
	  assert false : "trying to use dummy node";
	}
        void setDirectionTo(Vertex v) {
	  assert false : "trying to use dummy node";
	}
        void swapEndpoints() {
	  assert false : "trying to use dummy node";
	}
	int edgetype(Vertex v) {
	    assert false : "trying to use dummy node"; 
	    return -1; }
	int numMatches( Vertex v, int edgetype ) {
	    assert false : "trying to use dummy node";
	    return -1; }
        void detach() {
	  assert false : "trying to remove dummy node from e-list";
	}
    }


    
    /**
     * Vertices of <code>IncidenceListGraph</code>.  The inheritance
     * from FNSNode works the magic by which a vertex is also
     * a position in the global vertex list.  The vertex keeps a circularly
     * linked list of its incident edges.  The edges themselves contain
     * the links that implement the list (and since each edge has two
     * endpoints, it must have two sets of links).  The vertex starts
     * out with a dummy edge in order to avoid special-casing on
     * empty lists and ends of lists.
     *
     * @see IncidenceListGraph
     */
    private static class ILVertex extends jdsl.core.ref.NodeSequence.FNSNode
    implements Vertex {

	// vert holds circularly linked list of edges, with one dummy node
	// always present
	private ILEdgeDummy edummy_;
	private int size_;


        /**
         * Create a new isolated vertex.
         *
         * @param cont  The graph
         * @param elt   The element associated with this position
         */
        ILVertex( Object elt ) {
            super( elt );
	    edummy_ = new ILEdgeDummy();
	    size_ = 0;
        }


	Object replaceElement( Object newElement ) {
	    Object retval = element();
	    setElement( newElement );
	    return retval;
	}


	// used by a newly inserted edge to install itself in
	// its endpoints' incidence lists:
	ILEdgeDummy dummy() { return edummy_; }

	// an edge, when being added or removed, notifies its
	// endpoints of the arrival/departure:
	void loseEdge( ILEdge e ) { --size_; }
	void gainEdge( ILEdge e ) { ++size_; }

	
        /**
         * O(1).  Self-loops reported twice.
         *
         * @return  The degree (in, out, and undirected).
         */
        int degree() { return size_; }

	/** 
	 * O(degree).  Self-loops reported twice unless they are directed
	 * and only one direction is requested.
	 * @param edgetype
	 * @return 
	 */
 	int degree( int edgetype ) {
	    int retval = 0;
	    ILEdge e = edummy_.next();
	    while( e != edummy_ ) {
		retval += e.numMatches( this, edgetype );
		/*
		  if( (e.edgetype(this) & edgetype) != 0 ) {
		  ++retval;
		  if( e.isSelfLoop() &&
		  edgetype != IN &&
		  edgetype != OUT ) ++retval;
		  }
		  */
		e = e.next( this );
	    }
	    return retval;
	}


        /**
         * Get an iterator of all edges incident to this vertex that are of
	 * the specified type relative to this vertex (incoming, etc.).
         * A self-loop is reported twice, unless the self-loop is directed
	 * and only one direction is requested.
         *
	 * @param edgetype a constant, or an OR of constants, from
	 * the EdgeDirection interface
         * @return  All incident edges (in, out, and undirected)