subgraph.java

来自「JAVA图论的算法包。用过觉得还不错」· Java 代码 · 共 543 行 · 第 1/2 页

        assert (base.getEdgeTarget(e) == targetVertex);

        if (containsEdge(e)) {
            return false;
        } else {
            edgeSet.add(e);

            return true;
        }
    }

    /**
     * Adds the specified vertex to this subgraph.
     *
     * @param v the vertex to be added.
     *
     * @return <code>true</code> if the vertex was added, otherwise <code>
     * false</code>.
     *
     * @throws NullPointerException
     * @throws IllegalArgumentException
     *
     * @see Subgraph
     * @see Graph#addVertex(Object)
     */
    public boolean addVertex(V v)
    {
        if (v == null) {
            throw new NullPointerException();
        }

        if (!base.containsVertex(v)) {
            throw new IllegalArgumentException(NO_SUCH_VERTEX_IN_BASE);
        }

        if (containsVertex(v)) {
            return false;
        } else {
            vertexSet.add(v);

            return true;
        }
    }

    /**
     * @see Graph#containsEdge(Object)
     */
    public boolean containsEdge(E e)
    {
        return edgeSet.contains(e);
    }

    /**
     * @see Graph#containsVertex(Object)
     */
    public boolean containsVertex(V v)
    {
        return vertexSet.contains(v);
    }

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

        return unmodifiableEdgeSet;
    }

    /**
     * @see Graph#edgesOf(Object)
     */
    public Set<E> edgesOf(V vertex)
    {
        assertVertexExist(vertex);

        Set<E> edges = new ArrayUnenforcedSet<E>();
        Set<E> baseEdges = base.edgesOf(vertex);

        for (E e : baseEdges) {
            if (containsEdge(e)) {
                edges.add(e);
            }
        }

        return edges;
    }

    /**
     * @see Graph#removeEdge(Object)
     */
    public boolean removeEdge(E e)
    {
        return edgeSet.remove(e);
    }

    /**
     * @see Graph#removeEdge(Object, Object)
     */
    public E removeEdge(V sourceVertex, V targetVertex)
    {
        E e = getEdge(sourceVertex, targetVertex);

        return edgeSet.remove(e) ? e : null;
    }

    /**
     * @see Graph#removeVertex(Object)
     */
    public boolean removeVertex(V v)
    {
        // If the base graph does NOT contain v it means we are here in
        // response to removal of v from the base. In such case we don't need
        // to remove all the edges of v as they were already removed.
        if (containsVertex(v) && base.containsVertex(v)) {
            removeAllEdges(edgesOf(v));
        }

        return vertexSet.remove(v);
    }

    /**
     * @see Graph#vertexSet()
     */
    public Set<V> vertexSet()
    {
        if (unmodifiableVertexSet == null) {
            unmodifiableVertexSet = Collections.unmodifiableSet(vertexSet);
        }

        return unmodifiableVertexSet;
    }

    /**
     * @see Graph#getEdgeSource(Object)
     */
    public V getEdgeSource(E e)
    {
        return base.getEdgeSource(e);
    }

    /**
     * @see Graph#getEdgeTarget(Object)
     */
    public V getEdgeTarget(E e)
    {
        return base.getEdgeTarget(e);
    }

    private void addEdgesUsingFilter(Set<E> edgeSet, Set<E> filter)
    {
        E e;
        boolean containsVertices;
        boolean edgeIncluded;

        for (Iterator<E> iter = edgeSet.iterator(); iter.hasNext();) {
            e = iter.next();

            V sourceVertex = base.getEdgeSource(e);
            V targetVertex = base.getEdgeTarget(e);
            containsVertices =
                containsVertex(sourceVertex)
                && containsVertex(targetVertex);

            // note the use of short circuit evaluation
            edgeIncluded = (filter == null) || filter.contains(e);

            if (containsVertices && edgeIncluded) {
                addEdge(sourceVertex, targetVertex, e);
            }
        }
    }

    private void addVerticesUsingFilter(Set<V> vertexSet, Set<V> filter)
    {
        V v;

        for (Iterator<V> iter = vertexSet.iterator(); iter.hasNext();) {
            v = iter.next();

            // note the use of short circuit evaluation
            if ((filter == null) || filter.contains(v)) {
                addVertex(v);
            }
        }
    }

    public G getBase()
    {
        return base;
    }

    /**
     * @see Graph#getEdgeWeight(Object)
     */
    public double getEdgeWeight(E e)
    {
        return base.getEdgeWeight(e);
    }

    /**
     * @see WeightedGraph#setEdgeWeight(Object, double)
     */
    public void setEdgeWeight(E e, double weight)
    {
        ((WeightedGraph<V, E>) base).setEdgeWeight(e, weight);
    }

    //~ Inner Classes ----------------------------------------------------------

    /**
     * An internal listener on the base graph.
     *
     * @author Barak Naveh
     * @since Jul 20, 2003
     */
    private class BaseGraphListener
        implements GraphListener<V, E>,
            Serializable
    {
        private static final long serialVersionUID = 4343535244243546391L;

        /**
         * @see GraphListener#edgeAdded(GraphEdgeChangeEvent)
         */
        public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
        {
            if (isInduced) {
                E edge = e.getEdge();
                addEdge(
                    base.getEdgeSource(edge),
                    base.getEdgeTarget(edge),
                    edge);
            }
        }

        /**
         * @see GraphListener#edgeRemoved(GraphEdgeChangeEvent)
         */
        public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
        {
            E edge = e.getEdge();

            removeEdge(edge);
        }

        /**
         * @see VertexSetListener#vertexAdded(GraphVertexChangeEvent)
         */
        public void vertexAdded(GraphVertexChangeEvent<V> e)
        {
            // we don't care
        }

        /**
         * @see VertexSetListener#vertexRemoved(GraphVertexChangeEvent)
         */
        public void vertexRemoved(GraphVertexChangeEvent<V> e)
        {
            V vertex = e.getVertex();

            removeVertex(vertex);
        }
    }
}

// End Subgraph.java