network.java

Network数据结构与算法分析中 图的实现 相当全面 请需要的朋友们下载

import java.util.*;

public class Network {

    protected HashMap adjacencyMap;


    // Postcondition: this Network is empty.
    public Network() {

        adjacencyMap = new HashMap();

    } // default constructor


    // Precondition: V > 0; otherwise, IllegalArgumentException has been thrown.
    // Postcondition: this Network will hold, at most, V vertices.
    public Network (int V) {

        if (V <= 0)
            throw new IllegalArgumentException
                         ("number of vertices must be positive");
        adjacencyMap = new HashMap (V, 1.0f);

    } // constructor


    // Postcondition: this Network contains a clone of network.
    public Network (Network network) {

        adjacencyMap = new HashMap (network.adjacencyMap);

    } // copy constructor


    // Postcondition: true has been returned if this Network is empty;
    //                otherwise, false has been returned.
    public boolean isEmpty() {

        return adjacencyMap.isEmpty();

    } // method isEmpty


    // Postcondition: the number of vertices in this Network has been returned.
    public int size() {

        return adjacencyMap.size();

    } // method size


    // Postcondition: the number of edges in this Network has been returned.
    public int getEdgeCount() {

        int count = 0;

        Iterator itr = iterator();

        while (itr.hasNext())
            count += ((LinkedList)adjacencyMap.get (itr.next())).size();
        return count;

    } // method getEdgeCount


    // Postcondition: if <v1, v2> forms an edge in this Network, the weight of
    //                that edge has been returned. Otherwise, -1.0 has been
    //                returned.
    public double getEdgeWeight (Vertex v1, Vertex v2) {

        if (! (adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
            return -1.0;

        LinkedList list = (LinkedList)(adjacencyMap.get (v1));
        Iterator itr = list.iterator();
        while (itr.hasNext()) {

            VertexWeightPair vertexWeightPair = (VertexWeightPair)(itr.next());
            if (vertexWeightPair.getToVertex().equals (v2))
                return vertexWeightPair.getWeight();

        } // while
        return -1.0;  // there is no edge <v1, v2>

    } // method getEdgeWeight


    // Postcondition: true has been returned if this Network contains vertex;
    //                otherwise, false has been returned.
    public boolean containsVertex (Vertex vertex) {

        return adjacencyMap.containsKey (vertex);

    } // method containsVertex


    // Postcondition: true has been returned if this Network contains the
    //                edge <v1, v2>.  Otherwise, false has been returned.
    public boolean containsEdge (Vertex v1, Vertex v2) {

        if (! (adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
            return false;
        Iterator itr = ((LinkedList)adjacencyMap.get(v1)).iterator();
        while (itr.hasNext())
           if (((VertexWeightPair)itr.next()).getToVertex().equals (v2))
               return true;
        return false;

    } // method containsEdge


    // Postcondition: if vertex is already in this Network, false has been
    //                returned. Otherwise, vertex has been added to this
    //                Network and true has been returned.
    public boolean addVertex (Vertex vertex) {

        if (adjacencyMap.containsKey (vertex))
            return false;
        adjacencyMap.put (vertex, new LinkedList());
        return true;

    } // method addVertex


    // Postcondition: the edge <v1, v2> with the given weight has been
    //                added to this Network.
    public boolean addEdge (Vertex v1, Vertex v2, double weight) {

        addVertex (v1);
        addVertex (v2);
        VertexWeightPair vertexWeightPair = new VertexWeightPair (v2, weight);
        ((LinkedList)adjacencyMap.get (v1)).add (vertexWeightPair);
        return true;

    } // method addEdge


    // Postcondition: if vertex is a Vertex in this Network, vertex has been
    //                removed and true has been returned.  Otherwise, false has
    //                been returned.
    public boolean removeVertex (Vertex vertex) {

        if (!adjacencyMap.containsKey (vertex))
            return false;

        Iterator itr1 = adjacencyMap.keySet().iterator();
        while (itr1.hasNext()) {

            LinkedList list = (LinkedList)(adjacencyMap.get (itr1.next()));

            // If vertex is in a pair on list, remove that pair from list.
            Iterator itr2 = list.iterator();
            while (itr2.hasNext())
                if (((VertexWeightPair)itr2.next()).getToVertex().equals (vertex)) {

                    itr2.remove();
                    break;

                } // pair found and removed from vertex's adjacency list

        } // while iterating through the map of vertex keys
        adjacencyMap.remove (vertex);
        return true;

    } // removeVertex


    // Postcondition: if <v1, v2> is an edge in this Network, that edge has
    //                been removed and true has been returned.  Otherwise,
    //                false has been returned.
    public boolean removeEdge (Vertex v1, Vertex v2) {

        if (!adjacencyMap.containsKey (v1) || !adjacencyMap.containsKey (v2))
            return false;

        Iterator itr = ((LinkedList)adjacencyMap.get (v1)).iterator();
        while (itr.hasNext())
            if (((VertexWeightPair)itr.next()).getToVertex().equals (v2)) {

                itr.remove();
                return true;

            } // if
        return false;

    } // method removeEdge


    // Postcondition: an iterator over the vertices in this Network has
    //                been returned.
    public Iterator iterator() {

        return adjacencyMap.keySet().iterator();

    } // method iterator


    // Postcondition: a breadth-first iterator over all vertices reachable
    //                from v has been returned.
    public BreadthFirstIterator breadthFirstIterator (Vertex v) {

       if (!adjacencyMap.containsKey (v))
           return null;
      return new BreadthFirstIterator (v);

    } // method breadthFirstIterator


    // Postcondition: a depth-first iterator over all vertices reachable
    //                from v has been returned.
    public DepthFirstIterator depthFirstIterator (Vertex v) {

       if (!adjacencyMap.containsKey (v))
           return null;
       return new DepthFirstIterator (v);

    } // method depthFirstIterator


    // Postcondition: true has been returned if this Network is connected.
    //                Otherwise, false has been returned.
    public boolean isConnected() {

        Iterator itr1 = adjacencyMap.keySet().iterator();

        // For each vertex v, see if the number of vertices reachable from v
        // is equal to the total number of vertices in this Network.
        while (itr1.hasNext()) {

            Vertex v = (Vertex)(itr1.next());

            // Count the vertices reachable from v.
            BreadthFirstIterator itr2 = new BreadthFirstIterator (v);
            int count = 0;
            while (itr2.hasNext()) {

              itr2.next();
              count++;
            }     
            if (count < adjacencyMap.size())
                return false;

        } // while itr1 not finished iterating
        return true;

    } // method isConnected


    // Precondition: this Network is connected.  Otherwise,
    //               UnsupportedOperationException has been thrown.
    // Postcondition: a minimum spanning tree for this Network has
    //                been returned.
    public Network getMinimumSpanningTree() {

        Network tree = new Network(); // the minimal spanning tree is a
                                      // network so weights can be included

        PriorityQueue pq = new Heap();

        VertexWeightPair vertexWeightPair;

        Edge edge;

        Vertex root,
               w,
               x,
               y,
               z;

        Iterator itr1,
                 itr2,
                 itr3;

        double weight;

        if (!isConnected())
            throw new UnsupportedOperationException ("not connected");
        if (isEmpty())
            return tree;
        itr1 = adjacencyMap.keySet().iterator();
        root = (Vertex)(itr1.next());
        tree.addVertex (root);

        itr2 = ((LinkedList)adjacencyMap.get (root)).iterator();
        while (itr2.hasNext()) {

            vertexWeightPair = (VertexWeightPair)itr2.next();
            w = vertexWeightPair.getToVertex();
            weight = vertexWeightPair.getWeight();
            edge = new Edge (root, w, weight);
            pq.add (edge);

        } // adding root's edges to pq

        while (tree.size() < size()) {

            edge = (Edge)pq.removeMin();
            x = edge.getFromVertex();
            y = edge.getToVertex();
            weight = edge.getWeight();
            if (!tree.containsVertex (y)) {

                tree.addVertex (y);
                tree.addEdge (x, y, weight);

                itr3 = ((LinkedList)adjacencyMap.get (y)).iterator();
                while (itr3.hasNext()) {

                    vertexWeightPair = (VertexWeightPair)itr3.next();
                    z = vertexWeightPair.getToVertex();
                    if (!tree.containsVertex (z)) {

                        weight = vertexWeightPair.getWeight();
                        edge = new Edge (y, z, weight);
                        pq.add (edge);

                    } // z not already in tree

                } // iterating over y's neighbors

            } // y not already in tree

        } // tree has fewer vertices than this Network
        return tree;

    } // method getMinimumSpanningTree

    
    // Postcondition: the shortest path from v1 to v2 and its total weight
    //                have been returned.
    public LinkedList getShortestPath (Vertex v1, Vertex v2) {

        final double MAX_PATH_WEIGHT = Double.MAX_VALUE;

        HashMap weightSum = new HashMap();
        HashMap predecessor = new HashMap();

        PriorityQueue pq = new Heap();

        Iterator itr;

        Vertex vertex,
               to = null,
               from;

        VertexWeightPair vertexWeightPair;