graphimpl.java

OpenJGraph是一个开源的Java库

     */
    public void removeEdges( Vertex v ) throws Exception
    {
        beforeRemoveEdges(v,false);
        removeEdgesUnconditionally(v,false);
    }

    /**
     * Invoke before-listeners for removal of all edges incident
     * to v.
     */
    private void beforeRemoveEdges(Vertex v,boolean willRemoveVertex)
        throws Exception
    {
        Iterator iterator = getIncidentEdges(v).iterator();
        while( iterator.hasNext( )) {
            Edge edgetoremove = (Edge) iterator.next();
            GraphRemoveEdgeEvent event = new GraphRemoveEdgeEvent(
                this,edgetoremove,willRemoveVertex ? v : null);
            invokeRemoveEdgeListeners(event,true);
        }
    }

    /**
     * Complete the work of removeEdges, after all
     * before-listeners have been notified.
     */
    private void removeEdgesUnconditionally(Vertex v,boolean willRemoveVertex)
        throws Exception
    {
        // Remove incident edges of vertex; clone edge list
        // to avoid iteration/modification conflict.
        List vedges = new ArrayList(this.getIncidentEdges( v ));
        Iterator iterator = vedges.iterator();
        while( iterator.hasNext( )) {
            Edge edgetoremove = (Edge) iterator.next();
            GraphRemoveEdgeEvent event = new GraphRemoveEdgeEvent(
                this,edgetoremove,willRemoveVertex ? v : null);
            this.removeEdgeUnconditionally( event );
        }
    }

    /**
     * Returns the number of vertices in the graph
     *
     * @return	The number of vertices in the graph.
     */
    public int getVerticesCount() {
        return vertexDataMap.size();
    }

    /**
     * @see Graph#getEdgesCount
     */
    public int getEdgesCount() {
        return edgeSet.size();
    }

    /**
     * Returns all vertices with the specified degree.
     *
     * @param   degree    The degree of the vertex to be returned.
     * @return  A collection of vertices with the above specified degree.
     */
    public Set getVertices( int degree ) {
        Set       verticesofsamedegree = new HashSet();
        Iterator  iterator;
        Vertex    vertex;

        iterator = this.getVerticesIterator();
        while( iterator.hasNext() ) {
            vertex = (Vertex) iterator.next();
            if( this.getAdjacentVertices( vertex ).size() == degree )
                verticesofsamedegree.add( vertex );
        }

        return Collections.unmodifiableSet(verticesofsamedegree);
    }

    /**
     * Returns the vertices adjacent to the specified vertex.
     *
     * @param v The Vertex you want to determine its adjacent vertices.
     * @return List of vertices adjacent to the specified vertex v.
     */
    public List getAdjacentVertices( Vertex v ) {
        List    adjacentVertices = new ArrayList( 10 );
        List      incidentEdges = this.getEdges( v );
        Iterator  iterator;
        Edge      edge;
        Vertex    oppositeVertex;

        if( incidentEdges != null ) {
            iterator = incidentEdges.iterator();
            while( iterator.hasNext() ) {
                edge = (Edge) iterator.next();
                oppositeVertex = edge.getOppositeVertex( v );
                if( oppositeVertex != null )
                    adjacentVertices.add( oppositeVertex );
            }
        }

        return Collections.unmodifiableList(adjacentVertices);
    }

    /**
     * Returns the vertices adjacent to all the vertices in the given
     * collection.
     *
     * @param vertices List of Vertex where each vertex in the returned Set
     * must be adjacent to.
     * @return Set of vertices adjacent to all the vertices in the supplied
     * List.
     */
    public Set getAdjacentVertices( List vertices ) {
        HashSet adjacentVertices = new HashSet(
            this.getAdjacentVertices( (Vertex) vertices.get(0)) );
        int i, size = vertices.size();

        for( i = 1; i < size; i++ ) {
            adjacentVertices.retainAll(
                this.getAdjacentVertices( (Vertex) vertices.get(i)));
        }

        return Collections.unmodifiableSet(adjacentVertices);
    }

    /**
     * Construct a ConnectedSetListener for this graph if there isn't
     * one already.
     *
     * @return the new or existing ConnectedSetListener
     */
    private ConnectedSetListener getConnectedSetListener()
    {
        if (connectedSetListener == null) {
            connectedSetListener = new ConnectedSetListener(this);
            addListener(connectedSetListener);
        }
        return connectedSetListener;
    }

    /**
     * @see Graph#getConnectedSet()
     */
    public Collection getConnectedSet( ){
        return getConnectedSetListener().getConnectedSets();
    }

    /**
     * @see Graph#getConnectedSet(Vertex)
     */
    public Set getConnectedSet( Vertex v ){
        return getConnectedSetListener().getConnectedSet(v);
    }

    /**
     * Forget any information which has been incrementally maintained
     * about this graph's connected sets.  Such information is computed
     * on demand, so before doing a large number of graph updates, it's a good
     * idea to call this method if one of the getConnectedSet methods has been
     * previously called.
     */
    public void forgetConnectedSets()
    {
        if (connectedSetListener == null) {
            // can't forget something you don't remember
            return;
        }
        removeListener(connectedSetListener);
        connectedSetListener = null;
    }

    /**
     *  Traverses the Graph starting at startat Vertex.  Only the connected
     *  components to which startat belongs to will be traversed.
     */
    public List traverse( Vertex startat ){
        return traversal.traverse( startat );
    }

    /**
     * Gets the traversal algorithm used by the Graph.
     *
     * @return  GraphTraversal object performing traversal for the Graph.
     */
    public GraphTraversal getTraversal( ) {
        return this.traversal;
    }

    /**
     * Sets the graph traversal algorithm to be used
     *
     * @param traversal A concrete implementation of the GraphTraversal object.
     */
    public void setTraversal( GraphTraversal traversal ){
        this.traversal = traversal;
    }

    /**
     * Determines if two vertices are connected
     *
     * @param v1 starting Vertex for the path
     * @param v2 ending Vertex for the path
     * @return true if v1 and v2 are connected.
     */
    public boolean isConnected( Vertex v1, Vertex v2 ){
        Set connectedsetv1 = this.getConnectedSet( v1 );

        if( connectedsetv1.contains( v2 ))
            return true;
        else
            return false;
    }

    /**
     * Returns the degree of the graph, which is simply the highest degree
     * of all the graph's vertices.
     *
     * @return An int indicating the degree of the graph.
     */
    public int getDegree( ) {
        Vertex  v;
        Collection set;

        set = getVertexSet();
        if( set.size() > 0 ){
            v = (Vertex) Collections.max( set, new Comparator() {
                    public int compare( Object obj1, Object obj2 ) {
                        Vertex v1 = (Vertex) obj1, v2 = (Vertex) obj2;
                        int    countv1 = getDegree( v1 );
                        int    countv2 = getDegree( v2 );

                        if( countv1 < countv2 ) return -1;
                        if( countv1 > countv2 ) return 1;
                        else return 0;
                    }
                    public boolean equals( Object objcomparator ) {
                        return objcomparator.equals( this );
                    }
                }
                );
            return this.getEdges( v ).size();
        }
        else
            return 0;
    }

    /**
     * Returns the degree of the vertex, which is simply the number of edges
     * of the vertex.
     *
     * @return  The degree of the vertex.
     */
    public int getDegree( Vertex v ) {
        return this.getEdges( v ).size();
    }

    public void addListener(GraphListener listener) {
        listenerList.add(listener);
    }

    public void removeListener(GraphListener listener) {
        listenerList.remove(listener);
    }

    // Adaptor classes which adapt deprecated Listener interfaces to
    // replacement GraphListener interface.  Note that these define equals in
    // such a way that a List.remove(listener) will remove the adaptor
    // instead.

    private static abstract class ListenerAdaptor extends NullGraphListener
    {
        protected Object listener;

        protected ListenerAdaptor(Object listener)
        {
            this.listener = listener;
        }

        public boolean equals(Object obj)
        {
            if (!(obj instanceof ListenerAdaptor)) {
                return false;
            }
            return listener == ((ListenerAdaptor) obj).listener;
        }
    }

    private static class AddVertexListenerAdaptor extends ListenerAdaptor
    {
        AddVertexListenerAdaptor(GraphAddVertexListener listener)
        {
            super(listener);
        }

        public void afterVertexAdded(GraphAddVertexEvent event)
        {
            ((GraphAddVertexListener) listener).vertexAdded(event);
        }
    }

    private static class RemoveVertexListenerAdaptor extends ListenerAdaptor
    {
        RemoveVertexListenerAdaptor(GraphRemoveVertexListener listener)
        {
            super(listener);
        }

        public void beforeVertexRemoved(GraphRemoveVertexEvent event)
        {
            ((GraphRemoveVertexListener) listener).vertexRemoved(event);
        }
    }

    private static class AddEdgeListenerAdaptor extends ListenerAdaptor
    {
        AddEdgeListenerAdaptor(GraphAddEdgeListener listener)
        {
            super(listener);
        }

        public void afterEdgeAdded(GraphAddEdgeEvent event)
        {
            ((GraphAddEdgeListener) listener).edgeAdded(event);
        }
    }

    private static class RemoveEdgeListenerAdaptor extends ListenerAdaptor
    {
        RemoveEdgeListenerAdaptor(GraphRemoveEdgeListener listener)
        {
            super(listener);
        }

        public void beforeEdgeRemoved(GraphRemoveEdgeEvent event)
        {
            ((GraphRemoveEdgeListener) listener).edgeRemoved(event);
        }
    }


    /**
     * Adds a GraphAddVertexListener to the Graph's internal List of
     * GraphAddVertexListeners so that when a new Vertex is added,
     * all registered GraphAddVertedListeners are notified of the event.
     *
     * @param listener GraphAddVertexListener you want registered or be
     * notified when a new Vertex is added
     * @see salvo.jesus.graph.GraphAddVertexListener
     * @see #removeGraphAddVertexListener( GraphAddVertexListener )
     */
    public void addGraphAddVertexListener( GraphAddVertexListener listener ) {
        addListener(new AddVertexListenerAdaptor(listener));
    }

    /**
     * Adds a GraphAddEdgeListener to the Graph's internal List of
     * GraphAddEdgeListeners so that when a new Edge is added,
     * all registered GraphAddEdgeListeners are notified of the event.
     *
     * @param listener GraphAddEdgeListener you want registered or be notified
     * when a new Edge is added
     * @see salvo.jesus.graph.GraphAddEdgeListener
     * @see #removeGraphAddEdgeListener( GraphAddEdgeListener )
     */
    public void addGraphAddEdgeListener( GraphAddEdgeListener listener ) {
        addListener(new AddEdgeListenerAdaptor(listener));
    }

    /**
     * Adds a GraphRemoveEdgeListener to the Graph's internal List of
     * GraphRemoveEdgeListeners so that when an Edge is removed,
     * all registered GraphRemoveEdgeListeners are notified of the event.
     *
     * @param listener GraphRemoveEdgeListener you want registered or be
     * notified when an Edge is removed
     * @see salvo.jesus.graph.GraphRemoveEdgeListener
     * @see #removeGraphRemoveEdgeListener( GraphRemoveEdgeListener )
     */
    public void addGraphRemoveEdgeListener( GraphRemoveEdgeListener listener ) {
        addListener(new RemoveEdgeListenerAdaptor(listener));
    }

    /**
     * Adds a GraphRemoveVertexListener to the Graph's internal List of
     * GraphRemoveVertexListeners so that when a Vertex is removed,
     * all registered GraphRemoveVertexListeners are notified of the event.
     *
     * @param listener GraphRemoveVertexListener you want registered or be
     * notified when a Vertex is removed
     * @see salvo.jesus.graph.GraphRemoveVertexListener
     * @see #removeGraphRemoveVertexListener( GraphRemoveVertexListener )
     */
    public void addGraphRemoveVertexListener( GraphRemoveVertexListener listener ) {
        addListener(new RemoveVertexListenerAdaptor(listener));
    }

    /**
     * Removes a GraphAddVertexListener from the Graph's internal List of
     * GraphAddVertexListeners.
     *
     * @param listener GraphAddVertexListener you no longer want registered or
     * be notified when a Vertex is added
     * @see salvo.jesus.graph.GraphAddVertexListener
     * @see #addGraphAddVertexListener( GraphAddVertexListener )
     */
    public void removeGraphAddVertexListener( GraphAddVertexListener listener ) {
        removeListener(new AddVertexListenerAdaptor(listener));
    }

    /**
     * Removes a GraphAddEdgeListener from the Graph's internal List of
     * GraphAddEdgeListeners.
     *
     * @param listener GraphAddEdgeListener you no longer want registered or be
     * notified when an Edge is added
     * @see salvo.jesus.graph.GraphAddEdgeListener
     * @see #addGraphAddEdgeListener( GraphAddEdgeListener )
     */
    public void removeGraphAddEdgeListener( GraphAddEdgeListener listener ) {
        removeListener(new AddEdgeListenerAdaptor(listener));
    }

    /**
     * Removes a GraphRemoveEdgeListener from the Graph's internal List of
     * GraphRemoveEdgeListeners.
     *
     * @param listener GraphRemoveEdgeListener you no longer want registered or
     * be notified when an Edge is removed
     * @see salvo.jesus.graph.GraphRemoveEdgeListener
     * @see #addGraphRemoveEdgeListener( GraphRemoveEdgeListener )
     */
    public void removeGraphRemoveEdgeListener( GraphRemoveEdgeListener listener ) {
        removeListener(new RemoveEdgeListenerAdaptor(listener));
    }

    /**
     * Removes a GraphRemoveVertexListener from the Graph's internal List of
     * GraphRemoveVertexListeners.
     *
     * @param listener GraphRemoveVertexListener you no longer want registered
     * or be notified when a Vertex is removed
     * @see salvo.jesus.graph.GraphRemoveVertexListener
     * @see #addGraphRemoveVertexListener( GraphRemoveVertexListener )
     */
    public void removeGraphRemoveVertexListener( GraphRemoveVertexListener listener ) {
        removeListener(new RemoveVertexListenerAdaptor(listener));
    }

    /**
     * Returns a String representation of the Graph. The string returned in the
     * form: "Vertices: " + getVertexSet().toString() + "\n " + "Edges: " +
     * getEdgeSet().toString()
     *
     * @return	String representation of the Graph
     */
    public String toString() {
        return "Vertices: " + getVertexSet().toString() + "\n " +
            "Edges: " + getEdgeSet().toString();
    }
}