graphimpl.java

OpenJGraph是一个开源的Java库

package salvo.jesus.graph;

import java.util.*;
import java.io.*;
import salvo.jesus.graph.algorithm.*;
import salvo.jesus.graph.listener.*;

/**
 * An implementation of the Graph interface. GraphImpl
 * represents a materialized graph data structure in the form of a
 * set of incidence lists (one for each vertex).
 * GraphImpl relies on hashing, so the Vertex and Edge implementations
 * used must have well-behaved implementations of equals and hashCode (the
 * basic Object implementations of these methods work and are the most
 * efficient for most uses).
 *
 * $Id: GraphImpl.java,v 1.24 2002/08/24 07:32:24 jmsalvo Exp $
 */
public class GraphImpl implements Graph {

    /**
     * VertexData is the data structure kept for each vertex which is part of
     * this graph.
     */
    private static class VertexData implements Serializable
    {
        /**
         * The incidence list for each vertex is kept in a dynamic array.
         */
        private List incidentEdges;

        /**
         * unmodifiableIncidentEdges is an unmodifiable wrapper for
         * getIncidentEdges(), returned to callers whom we don't trust because
         * they might accidentally modify the incident edge list
         */
        private List unmodifiableIncidentEdges;

        VertexData()
        {
            incidentEdges = new ArrayList();
        }

        /**
         * The incident edge list for this vertex, defined by subclass
         * implementations.
         */
        final List getIncidentEdges()
        {
            return incidentEdges;
        }

        /**
         * Public accessor provides read-only access.
         */
        final List getUnmodifiableIncidentEdges()
        {
            if (unmodifiableIncidentEdges == null) {
                unmodifiableIncidentEdges = Collections.unmodifiableList(
                    getIncidentEdges());
            }
            return unmodifiableIncidentEdges;
        }
    }

    /**
     * Reference to the instance of <tt>GraphFactory</tt>
     * responsible for creating Vertices and Edges.
     */
    protected GraphFactory factory;

    /**
     * Set of adjacency lists for all vertices in the graph.  Each entry in the
     * map has a Vertex as key and an instance of VertexData as value.
     */
    private Map vertexDataMap;

    /**
     * An unmodifiable wrapper for vertexDataMap.keySet(), returned to callers
     * whom we don't trust because they might accidentally modify vertexDataMap.
     */
    private transient Set unmodifiableVertexSet;

    /**
     * Set of edges in this graph.  This is redundant with vertexDataMap, but
     * is maintained for two purposes:  (1) to allow a constant-time
     * duplicate-edge test; (2) to provide convenient iteration over all edges
     * in the graph.
     */
    private Set edgeSet;

    /**
     * An unmodifiable wrapper for edgeSet, returned to callers whom we don't
     * trust because they might accidentally modify edgeSet.
     */
    private transient Set unmodifiableEdgeSet;

    /**
     * List<GraphListener> with all listeners interested in receiving
     * notifications about modifications to this Graph.
     */
    private List listenerList;

    /**
     * A listener for incrementally maintaining connected set information
     * about this graph.  If this is non-null, then it is also registered
     * in listenerList.
     */
    private ConnectedSetListener connectedSetListener;

    /**
     * Delegate object for implementing graph traversal. The default
     * implementation is DepthFirstGraphTraversal.
     */
    protected  GraphTraversal    traversal;

    public GraphImpl() {
        vertexDataMap = new HashMap();
        edgeSet = new HashSet();
        listenerList = new ArrayList(10);

        this.factory = new GraphImplFactory();

        traversal = new DepthFirstGraphTraversal( this );
    }

    /**
     * Returns the factory that will be responsible for creating Vertices
     * and Edges in a Graph.
     */
    public GraphFactory getGraphFactory() {
        return this.factory;
    }

    /**
     * Sets the factory that will be responsible for creating Vertices
     * and Edges in a Graph.
     */
    public void setGraphFactory( GraphFactory factory ) {
        this.factory = factory;
    }

    /**
     * Returns a read-only iterator that iterates through the graph's vertices.
     *
     * @return  An iterator of vertices.
     */
    public Iterator getVerticesIterator() {
        return getVertexSet().iterator();
    }

    /**
     * Returns a clone of the List of vertices.
     *
     * @return  A clone of the List of vertices.
     */
    public List cloneVertices() {
        return new ArrayList(getVertexSet());
    }

    /**
     * @see Graph#getVertexSet
     */
    public Set getVertexSet()
    {
        // NOTE:  this and getEdgeSet() are computed on demand because
        // they have to be transient fields for Serializable

        if (unmodifiableVertexSet == null) {
            unmodifiableVertexSet = Collections.unmodifiableSet(
                vertexDataMap.keySet());
        }
        return unmodifiableVertexSet;
    }

    /**
     * @see Graph#getEdgeSet
     */
    public Set getEdgeSet()
    {
        if (unmodifiableEdgeSet == null) {
            unmodifiableEdgeSet = Collections.unmodifiableSet(edgeSet);
        }
        return unmodifiableEdgeSet;
    }

    /**
     * Test whether a vertex is included in this graph.
     *
     * @param v the vertex to test
     *
     * @return true iff the vertex is included
     */
    public boolean containsVertex(Vertex v)
    {
        return this.vertexDataMap.containsKey(v);
    }

    /**
     * Test whether an edge is included in this graph.
     *
     * @param edge the edge to test
     *
     * @return true iff the edge is included
     */
    public boolean containsEdge(Edge edge)
    {
        return edgeSet.contains(edge);
    }

    /**
     * Returns an unmodifiable List of edges of the specified vertex.
     *
     * @param   v   The vertex whose edges we want returned
     * @return A List of Edges that are incident edges of the specified vertex.
     */
    public List getEdges( Vertex v ) {
        return getVertexData(v).getUnmodifiableIncidentEdges();
    }

    private VertexData getVertexData(Vertex v)
    {
        return (VertexData) vertexDataMap.get(v);
    }

    private List getIncidentEdges(Vertex v)
    {
        return getVertexData(v).getIncidentEdges();
    }

    private void invokeAddVertexListeners(
        GraphAddVertexEvent event,boolean before)
        throws Exception
    {
        Iterator iter = listenerList.iterator();
        while (iter.hasNext()) {
            GraphListener graphListener = (GraphListener) iter.next();
            if (before) {
                graphListener.beforeVertexAdded(event);
            } else {
                graphListener.afterVertexAdded(event);
            }
        }
    }

    private void invokeRemoveVertexListeners(
        GraphRemoveVertexEvent event,boolean before)
        throws Exception
    {
        Iterator iter = listenerList.iterator();
        while (iter.hasNext()) {
            GraphListener graphListener = (GraphListener) iter.next();
            if (before) {
                graphListener.beforeVertexRemoved(event);
            } else {
                graphListener.afterVertexRemoved(event);
            }
        }
    }

    private void invokeAddEdgeListeners(
        GraphAddEdgeEvent event,boolean before)
        throws Exception
    {
        Iterator iter = listenerList.iterator();
        while (iter.hasNext()) {
            GraphListener graphListener = (GraphListener) iter.next();
            if (before) {
                graphListener.beforeEdgeAdded(event);
            } else {
                graphListener.afterEdgeAdded(event);
            }
        }
    }

    private void invokeRemoveEdgeListeners(
        GraphRemoveEdgeEvent event,boolean before)
        throws Exception
    {
        Iterator iter = listenerList.iterator();
        while (iter.hasNext()) {
            GraphListener graphListener = (GraphListener) iter.next();
            if (before) {
                graphListener.beforeEdgeRemoved(event);
            } else {
                graphListener.afterEdgeRemoved(event);
            }
        }
    }

    /**
     * This implementation of add(Vertex) should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of vertex additions.
     *
     * @see Graph#add
     */
    public void add( Vertex newvertex ) throws Exception {
        GraphAddVertexListener	listener;

        if (this.containsVertex(newvertex)) {
            // vertex is already part of this graph; nothing to do
            return;
        }

        GraphAddVertexEvent event =
            new GraphAddVertexEvent(this,newvertex,null);
        invokeAddVertexListeners(event,true);
        addVertexUnconditionally(event);
    }

    /**
     * Do the real work of adding a vertex, including invoking
     * after-listeners.  Before-listeners are invoked outside of this method,
     * since they may abort the vertex-adding process.
     */
    private void addVertexUnconditionally(GraphAddVertexEvent event)
        throws Exception
    {
        vertexDataMap.put(event.getVertex(),new VertexData());
        invokeAddVertexListeners(event,false);
    }

    /**
     * This implementation of addEdge should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of edge additions.
     *
     * @see Graph#addEdge(Vertex,Vertex)
     */
    public Edge addEdge( Vertex v1, Vertex v2 ) throws Exception {
        Edge edge = this.factory.createEdge( v1, v2 );
        addEdge( edge );
        return edge;
    }

    /**
     * This implementation of addEdge should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of edge additions.
     *
     * @see Graph#addEdge(Edge)
     */
    public void addEdge( Edge edge ) throws Exception {
        if (this.containsEdge(edge)) {
            // edge is already part of this graph; nothing to do
            return;
        }

        Vertex v1 = edge.getVertexA();
        Vertex v2 = edge.getVertexB();
        GraphAddVertexEvent v1addEvent = null;
        GraphAddVertexEvent v2addEvent = null;

        if (!this.containsVertex(v1)) {
            v1addEvent = new GraphAddVertexEvent(this,v1,edge);
        }
        if ((v2 != v1) && !this.containsVertex(v2)) {
            v2addEvent = new GraphAddVertexEvent(this,v2,edge);
        }

        // invoke relevant before-listeners
        if (v1addEvent != null) {
            invokeAddVertexListeners(v1addEvent,true);
        }
        if (v2addEvent != null) {
            invokeAddVertexListeners(v2addEvent,true);
        }

        GraphAddEdgeEvent event = new GraphAddEdgeEvent(
            this,
            edge,
            v1addEvent != null,
            v2addEvent != null);
        invokeAddEdgeListeners(event,true);

        // we have the go-ahead from all before-listeners; now do the real work

        if (v1addEvent != null) {
            addVertexUnconditionally(v1addEvent);
        }
        if (v2addEvent != null) {
            addVertexUnconditionally(v2addEvent);
        }

        List v1edges = this.getIncidentEdges( v1 );

        // Add the edge as an incident edge of both vertices
        v1edges.add( edge );
        if (v1 != v2) {
            // don't add the edge twice in the case of a self-loop
            List v2edges = this.getIncidentEdges( v2 );
            v2edges.add( edge );
        }

        // also add the edge to edgeSet
        edgeSet.add(edge);

        invokeAddEdgeListeners(event,false);
    }

    /**
     * This implementation of remove should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of vertex removals.
     *
     * @see Graph#remove
     */
    public void remove( Vertex v ) throws Exception {
        beforeRemoveEdges(v,true);

        GraphRemoveVertexEvent event = new GraphRemoveVertexEvent(this,v);
        invokeRemoveVertexListeners(event,true);

        // we have the go-ahead from all before-listeners; now do the real work

        removeEdgesUnconditionally(v,true);

        vertexDataMap.remove(v);
        invokeRemoveVertexListeners(event,false);
    }

    /**
     * This implementation of removeEdge should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of edge removals.
     *
     * @see Graph#removeEdge
     */
    public void removeEdge( Edge edge ) throws Exception {
        GraphRemoveEdgeEvent event = new GraphRemoveEdgeEvent(this,edge,null);
        invokeRemoveEdgeListeners(event,true);
        removeEdgeUnconditionally(event);
    }

    /**
     * Complete the work of removeEdge, after all
     * before-listeners have been notified.
     */
    private void removeEdgeUnconditionally(GraphRemoveEdgeEvent event)
        throws Exception
    {
        // Remove the edge from the vertices incident edges.
        Edge edge = event.getEdge();
        Vertex v1 = edge.getVertexA();
        List v1edges = this.getIncidentEdges( v1 );
        v1edges.remove( edge );

        Vertex v2 = edge.getVertexB();
        List v2edges = this.getIncidentEdges( v2 );
        v2edges.remove( edge );

        // Remove the edge from edgeSet
        edgeSet.remove(edge);

        invokeRemoveEdgeListeners(event,false);
    }

    /**
     * This implementation of removeEdges should not normally be
     * overridden by subclasses.  Instead, subclasses should
     * set up listeners to receive notifications of edge removals.
     *
     * @see Graph#removeEdges