import java.util.Iterator;

public class DecreasingPath {
    public static void main(String[] args) {
        WeightedGraph G = makeExampleGraph();
        
        int startNode = 11;
        boolean done = false;
        int currentNode = startNode;
        double lastWeight = Double.POSITIVE_INFINITY;
        while(!done) {
            System.out.printf("I am now at %d\n", currentNode);
            double maxValidEdgeWeight = Double.NEGATIVE_INFINITY;
            int maxValidNeighbor = -1;
            
            for(Integer neighbor : G.getNeighbors(currentNode)) {
                double w = G.getWeight(currentNode, neighbor);
                if(w > maxValidEdgeWeight && w < lastWeight) {
                    maxValidEdgeWeight = w;
                    maxValidNeighbor = neighbor;
                }
            }
            if(maxValidEdgeWeight == Double.NEGATIVE_INFINITY) {
                done = true;
            } else {
                System.out.printf("Taking edge {%d,%d} with weight %f\n",
                    currentNode, maxValidNeighbor, maxValidEdgeWeight);
                currentNode = maxValidNeighbor;
                lastWeight = maxValidEdgeWeight;
            }
        }
    }
    
    public static WeightedGraph makeExampleGraph() {
        WeightedGraph G = new MysteryWeightedGraphImplementation(false, 13);
        G.addEdge(11, 0, 8.0);
        G.addEdge(11, 12, 9.9);
        G.addEdge(0, 1, 3.6);
        G.addEdge(12, 1, 7.0);
        G.addEdge(0, 2, 2.5);
        G.addEdge(1, 3, 4.8);
        G.addEdge(1, 4, 9.2);
        G.addEdge(4, 5, 1.5);
        G.addEdge(3, 5, 1.3);
        G.addEdge(2, 3, 1.7);
        G.addEdge(2, 6, 0.1);
        G.addEdge(6, 7, 7.9);
        G.addEdge(5, 6, 3.5);
        G.addEdge(2, 8, 5.5);
        G.addEdge(5, 10, 5.0);
        G.addEdge(10, 9, 2.0);
        G.addEdge(7, 9, 0.5);
        G.addEdge(7, 10, 6.6);
        G.addEdge(6, 10, 9.9);
        G.addEdge(7, 8, 8.4);
        return G;
    }
}