incidencelistgraph.java

Java数据结构开发包

         */
        EdgeIterator incidentEdges( int edgetype ) {
	    Sequence accum = new jdsl.core.ref.NodeSequence();
	    ILEdge e = edummy_.next();
	    while( e != edummy_ ) {
		int num = e.numMatches( this, edgetype );
		// num is 0, 1, or 2
		if( num>0 ) accum.insertLast(e);
		if( num>1 ) accum.insertLast(e);
		/*
		  if( (e.edgetype(this) & edgetype) != 0 ) {
		  accum.insertLast( e );
		  if( e.isSelfLoop() &&
		  edgetype != IN &&
		  edgetype != OUT ) accum.insertLast( e );
		  }
		  */
		e = e.next( this );
	    }
	    return new EdgeIteratorAdapter( accum.elements() );
	}

	
        /**
         * Get an incident edge of the specified type.  Takes O(degree)
	 * time unless the specified type is the OR of all types, in which
	 * case, constant-time.
         *
         * @return An incident edge (in, out, or undirected), or Edge.NONE
         */
        ILEdge anEdge( int edgetype ) {
	    ILEdge e = edummy_.next();
	    while( e != edummy_ ) {
		if( e.numMatches( this, edgetype ) > 0 ) return e;
		e = e.next( this );
	    }
	    return null;
        }

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

    } // class ILVertex




    /**
     * Abstract superclass of all edges, basically providing an
     * interface that edges have to meet, plus element- and direction-
     * related services.  This class is here basically to
     * prevent having data members where they are not needed.
     * The inheritance from FNSNode works the magic by which an edge
     * is also a position in the global edge list.
     */
  private static abstract class ILEdge
    extends jdsl.core.ref.NodeSequence.FNSNode implements Edge {

	private boolean isDirected_;

	ILEdge() { super( null ); } // to be used only by ILEdgeDummy
	ILEdge( Object elt, boolean isDir ) {
	    super( elt );
	    isDirected_ = isDir;
	}

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

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

	// an edge, when being removed, removes itself from
	// its endpoints' incidence lists
	abstract void detach();

	// methods dealing with the edge's place in its endpoints'
	// incidence lists.  They take a vertex to specify which
	// endpoint.
 	abstract ILEdge next( Vertex whichEnd );
	abstract ILEdge prev( Vertex whichEnd );
	abstract void setNext( Vertex whichEnd, ILEdge e );
	abstract void setPrev( Vertex whichEnd, ILEdge e );

	// methods dealing with endpoints
	abstract boolean isSelfLoop();
	abstract ILVertex[] endpoints(); // if directed, origin is first
	abstract void swapEndpoints(); // if directed, reverses direction

	// methods dealing with directedness
        boolean isDir() { return isDirected_; }
        void makeDirected() { isDirected_ = true; }
	void makeUndirected() { isDirected_ = false; }
	abstract ILVertex origin();
	abstract ILVertex destination();
	abstract void setDirectionFrom( Vertex v );
	abstract void setDirectionTo( Vertex v );

	// tells whether this edge is undirected, incoming, or outgoing
	// relative to the vertex specified
	abstract int edgetype( Vertex endpoint ); // now unused
	abstract int numMatches( Vertex endpt, int edgetype );
	
    }

	

    /**
     * Edges that have two distinct endpoints.  See ILEdge
     * for specifications of methods.
     *
     * @see IncidenceListGraph
     * @see IncidenceListGraph.ILEdge
     */
    private static class ILNormalEdge extends ILEdge {
	
	// endpoints: if directed, v1 is origin, v2 dest
        private ILVertex v1_, v2_ ;
	// links in the edge lists of the two endpoints:
        private ILEdge prev1_, next1_, prev2_, next2_;

	// every edge constructed knows its endpoints, and installs itself 
	// in its endpoints' incidence lists.
        ILNormalEdge( ILVertex v1, ILVertex v2,
	       Object elt, boolean isDirected) {
            super( elt, isDirected );

	    assert v1 != v2;
            v1_ = v1;
	    v2_ = v2;

	    // link self into one endpoint's edge list:
	    prev1_ = v1.dummy();
	    next1_ = v1.dummy().next();
	    prev1_.setNext( v1, this );
	    next1_.setPrev( v1, this );
	    // notify endpoint of new arrival:
	    v1.gainEdge( this ); 

	    // symmetric code for other endpoint:
	    prev2_ = v2.dummy();
	    next2_ = v2.dummy().next();
	    prev2_.setNext( v2, this );
	    next2_.setPrev( v2, this );
	    v2.gainEdge( this );
	    
        }

	
	void detach() {

	    // unlink self from endpoints' edge lists:
	    prev1_.setNext( v1_, next1_ );
	    next1_.setPrev( v1_, prev1_ );
	    prev2_.setNext( v2_, next2_ );
	    next2_.setPrev( v2_, prev2_ );

	    // notify endpoints of the edge's departure:
	    v1_.loseEdge( this );
	    v2_.loseEdge( this );
	    
	    // encourage explosions if a bug happens:
	    prev1_ = next1_ = prev2_ = next2_ = null;
	    v1_ = v2_ = null; 

	}

	
	
	ILEdge next( Vertex whichEnd ) {
	    if( v1_==whichEnd ) return next1_;
	    assert v2_==whichEnd;
	    return next2_;
	}

	ILEdge prev( Vertex whichEnd ) {
	    if( v1_==whichEnd ) return prev1_;
	    assert v2_==whichEnd;
	    return prev2_;
	}

	void setNext( Vertex whichEnd, ILEdge n ) {
	    if( v1_==whichEnd ) next1_ = n;
	    else {
		assert v2_==whichEnd;
		next2_ = n;
	    }
	}

	void setPrev( Vertex whichEnd, ILEdge n ) {
	    if( v1_==whichEnd ) prev1_ = n;
	    else {
		assert v2_==whichEnd;
		prev2_ = n;
	    }
	}

	

        boolean isSelfLoop() { return false; }
	
        ILVertex[] endpoints() {
            ILVertex[] retval = new ILVertex[2];
            retval[0] = v1_;
            retval[1] = v2_;
            return retval;
        }

        void swapEndpoints() {
            ILVertex vtemp = v1_ ;
            v1_ = v2_ ;
            v2_ = vtemp;

            ILEdge etemp = next1_;
	    next1_ = next2_;
	    next2_ = etemp;

	    etemp = prev1_;
	    prev1_ = prev2_;
	    prev2_ = etemp;
        }


	
        ILVertex origin() {
            assert isDir();
            return v1_;
        }
	
        ILVertex destination() {
            assert isDir();
            return v2_;
        }

        void setDirectionFrom(Vertex v) {
            makeDirected();
            if(v==v1_) return;
            if(v==v2_) swapEndpoints();
	    else throw new InvalidVertexException( "Vertex " + v +
						  " not an endpoint of edge " + this );
        }

        void setDirectionTo(Vertex v) {
            makeDirected();
            if(v==v2_) return;
	    if(v==v1_) swapEndpoints();
	    else throw new InvalidVertexException( "Vertex " + v +
						  " not an endpoint of edge " + this );
        }



	int edgetype( Vertex endpoint ) {
	    if( isDir() ) {
		if( endpoint==v1_ ) return EdgeDirection.OUT;
		assert endpoint==v2_ : "not an endpoint";
		return EdgeDirection.IN;
	    }
	    else {
	        assert endpoint==v1_ || endpoint==v2_ : "not an endpoint";
		return EdgeDirection.UNDIR;
	    }
	}

	int numMatches( Vertex endpt, int edgetype ) {
	    int mytype = edgetype( endpt );
	    if( (mytype & edgetype) != 0 ) return 1;
	    else return 0;
	}


    } // class ILNormalEdge


    private static class ILLoopEdge extends ILEdge {

	private ILVertex v_; // has only one endpoint
	private ILEdge prev_, next_;

	ILLoopEdge( ILVertex v, Object elt, boolean isDirected ) {
	    super( elt, isDirected );
	    v_ = v;
	    prev_ = v.dummy();
	    next_ = v.dummy().next();
	    prev_.setNext( v, this );
	    next_.setPrev( v, this );
	    v.gainEdge( this );
	    v.gainEdge( this ); // fool v into thinking this is two edges
	}

	void detach() {
	    prev_.setNext( v_, next_ );
	    next_.setPrev( v_, prev_ );
	    v_.loseEdge( this );
	    v_.loseEdge( this ); // maintain illusion established in ctor
	    prev_ = next_ = null; // make this object useless
	    v_ = null;
	}

	

	ILEdge next( Vertex whichEnd ) {
	    assert whichEnd == v_;
	    return next_;
	}

	ILEdge prev( Vertex whichEnd ) {
	    assert whichEnd == v_;
	    return prev_;
	}

	void setNext( Vertex whichEnd, ILEdge e ) {
	    assert whichEnd == v_;
	    next_ = e;
	}

    	void setPrev( Vertex whichEnd, ILEdge e ) {
	    assert whichEnd == v_;
	    prev_ = e;
	}


	boolean isSelfLoop() { return true; }

	ILVertex[] endpoints() {
            ILVertex[] retval = new ILVertex[2];
            retval[0] = v_;
            retval[1] = v_;
            return retval;
        }

	void swapEndpoints() { }


	ILVertex origin() {
            assert isDir();
            return v_;
        }
	
        ILVertex destination() {
            assert isDir();
            return v_;
        }

	void setDirectionFrom( Vertex v ) {
	    makeDirected();
	    if( v != v_ )  throw new InvalidVertexException( "Vertex " + v +
							     " not an endpoint of edge " + this );
	}

	void setDirectionTo( Vertex v ) {
	    makeDirected();
	    if( v != v_ )  throw new InvalidVertexException( "Vertex " + v +
							     " not an endpoint of edge " + this );
	}


	int edgetype( Vertex endpoint ) {
	    // self-loops are both incoming and outgoing !
	    if( isDir() ) return EdgeDirection.IN | EdgeDirection.OUT;
	    else return EdgeDirection.UNDIR;
	}

	int numMatches( Vertex endpt, int edgetype ) {
	    assert endpt==v_;
	    if( isDir() ) {
		int retval = 0;
		if( (EdgeDirection. IN & edgetype) != 0 ) ++retval;
		if( (EdgeDirection.OUT & edgetype) != 0 ) ++retval;
		return retval;
	    }
	    else {
		if( (EdgeDirection.UNDIR & edgetype) != 0 ) return 2;
		else return 0;
	    }
	}


    } // ILLoopEdge


}