network.java

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

        double weight;

        if (! (adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
            return new LinkedList();
        Iterator netItr = breadthFirstIterator (v1);
        while (netItr.hasNext()) {

            vertex = (Vertex)(netItr.next());
            weightSum.put (vertex, new Double (MAX_PATH_WEIGHT));
            predecessor.put (vertex, new Vertex());

        } // initializing weightSum and predecessor
        LinkedList edgeList = ((LinkedList)adjacencyMap.get (v1));
        for (int i = 0; i < edgeList.size(); i++) {

            vertexWeightPair = ((VertexWeightPair)edgeList.get (i));
            weightSum.put (vertexWeightPair.getToVertex(),
                           new Double (vertexWeightPair.getWeight()));
            predecessor.put (vertexWeightPair.getToVertex(), v1);
            pq.add (vertexWeightPair);

        } // adjusting weightSum and predecessor for vertices adjacent to v1
        weightSum.put (v1, new Double (0.0));
        predecessor.put (v1, v1);

        boolean pathFound = false;
        while (!pathFound && !pq.isEmpty()) {

            vertexWeightPair = (VertexWeightPair)pq.removeMin();
            from = vertexWeightPair.getToVertex();
            if (from.equals (v2))
                pathFound = true;
            else {

                itr = ((LinkedList)adjacencyMap.get (from)).iterator();
                while (itr.hasNext()) {

                    vertexWeightPair = (VertexWeightPair)itr.next();
                    to = vertexWeightPair.getToVertex();
                    weight = vertexWeightPair.getWeight();
                    if (((Double)weightSum.get (from)).doubleValue() + weight
                              < ((Double)weightSum.get (to)).doubleValue()) {

                        weightSum.put (to, new Double (((Double)
                                weightSum.get (from)).doubleValue() + weight));
                        predecessor.put (to, from);
                        pq.add (new VertexWeightPair (to,
                                ((Double)weightSum.get (to)).doubleValue()));

                    } // if

                } // while from's neighbors have not been processed

            } // else path not yet found

        } // while not done and priority queue not empty
        LinkedList path = new LinkedList();
        if (pathFound) {

            Vertex current = v2;
            while (!(current.equals (v1))) {

                path.addFirst (current);
                current = (Vertex)(predecessor.get (current));

            } // while not back to v1
            path.addFirst (v1);

        } // if path found
        path.addLast (weightSum.get (v2));
        return path;

    } // method findShortestPath


    public LinkedList getCycle() {

        LinkedList cycle = new LinkedList();

        double cycleWeight = 0.0;

        LinkedList edgeList;

        VertexWeightPair vertexWeightPair;

        Iterator itr = iterator();

        Iterator listItr;

        Vertex v,
               start = (Vertex)itr.next();

        cycle.add (start);
        v = start;
        while (cycle.size() < size()) {

            edgeList = ((LinkedList)adjacencyMap.get (v));
            listItr = edgeList.iterator();
            do {

                vertexWeightPair = (VertexWeightPair)listItr.next();
                v = vertexWeightPair.getToVertex();

            } // do
            while (cycle.contains (v) && listItr.hasNext());
            if (!cycle.contains (v)) {

                cycle.add (v);
                cycleWeight += vertexWeightPair.getWeight();

            } // if

        } // while
        cycle.add (start);
        cycleWeight += getEdgeWeight (v, start);
        cycle.add (new Double (cycleWeight));
        return cycle;

    } // method getCycle


    // Postcondition: the string corresponding to this Network has been
    //                returned.
    public String toString() {

        return adjacencyMap.toString();

    } // method toString


class BreadthFirstIterator implements Iterator {

    Queue queue;

    HashMap reached;

    Vertex current;

    // Postcondition: this BreadthFirstIterator has been initialized at start.
    public BreadthFirstIterator (Vertex start) {

        queue = new Queue();

        reached = new HashMap();

        Iterator itr = adjacencyMap.keySet().iterator();
        while (itr.hasNext())
            reached.put (itr.next(), new Boolean (false));

        queue.enqueue (start);
        reached.put (start, new Boolean (true));

    } // one-parameter constructor


    // Postcondition: true has been returned if this BreadthFirstIterator has
    //                reached all of its reachable vertices.  Otherwise,
    //                false has been returned.
    public boolean hasNext() {

        return !(queue.isEmpty());

    } // method hasNext


    // Postcondition: the next reachable vertex in this BreadthFirstIterator
    //                has been returned.
    public Object next() {

        VertexWeightPair vertexWeightPair;

        Vertex to;

        current = (Vertex)queue.dequeue();

        LinkedList edgeList = (LinkedList)adjacencyMap.get (current);
        Iterator itr = edgeList.iterator();
        while (itr.hasNext()) {

            vertexWeightPair = (VertexWeightPair)itr.next();
            to = vertexWeightPair.getToVertex();
            if (!((Boolean)reached.get (to)).booleanValue()) {

                reached.put (to, new Boolean (true));
                queue.enqueue (to);

            } // if

        } // while
        return current;

    } // method next


    // Postcondition: the most recently returned vertex has been removed.
    public void remove() {

        Network.this.removeVertex (current);

    } // method remove


} // class BreadthFirstIterator


class DepthFirstIterator implements Iterator {

    Stack stack;

    HashMap reached;

    Vertex current;


    // Postcondition: this DepthFirstIterator has been initialized at start.
    public DepthFirstIterator (Vertex start) {

        stack = new Stack();

        reached = new HashMap();

        Iterator itr = adjacencyMap.keySet().iterator();
        while (itr.hasNext())
            reached.put (itr.next(), new Boolean (false));

        stack.push (start);
        reached.put (start, new Boolean (true));

    } // one-parameter constructor


    // Postcondition: true has been returned if this DepthFirstIterator has
    //                reached all of its reachable vertices.  Otherwise,
    //                false has been returned.
    public boolean hasNext() {

        return !(stack.isEmpty());

    } // method hasNext


    // Postcondition: the next reachable vertex in this DepthFirstIterator
    //                has been returned.
    public Object next() {

        VertexWeightPair vertexWeightPair;

        Vertex to;

        current = (Vertex)stack.pop();

        LinkedList edgeList = (LinkedList)adjacencyMap.get (current);
        Iterator itr = edgeList.iterator();
        while (itr.hasNext()) {

            vertexWeightPair = (VertexWeightPair)itr.next();
            to = vertexWeightPair.getToVertex();
            if (!((Boolean)reached.get (to)).booleanValue()) {

                reached.put (to, new Boolean (true));
                stack.push (to);

            } // if

        } // while
        return current;

    } // method next


    // Postcondition: the most recently returned vertex has been removed.
    public void remove() {

        Network.this.removeVertex (current);

    } // method remove


} // class DepthFirstIterator


  

} // class Network


class VertexWeightPair implements Comparable {

    Vertex to;  // the "from" vertex is implicit

    double weight;


    // Postcondition: this VertexWeightPair has been initialized from vertex and weight.
    public VertexWeightPair (Vertex vertex, double weight) {

        to = vertex;
        this.weight = weight;

    } // default constructor


    // Postcondition: the "to" vertex in this VertexWeightPair has been returned.
    public Vertex getToVertex() {

        return to;

    } // method getToVertex


    // Postcondition: the weight in this VertexWeightPair has been returned.
    public double getWeight() {

        return weight;

    } // method getWeight


    // Postcondition: an int <, = or > 0 has been returned, depending on
    //                whether this VertexWeightPair's weight is <, = or >
    //                VertexWeightPair's weight.
    public int compareTo (Object VertexWeightPair) {

        return (int)(weight - ((VertexWeightPair)VertexWeightPair).getWeight());

    } // method compareTo


    // Postcondition: a String representation of this VertexWeightPair
    //                has been returned.
    public String toString() {

        return to.toString() + "  " + String.valueOf (weight);

    } // method toString

} // class VertexWeightPair