ucs

ucs.java

package ua.edu.lnu.pif.ucs;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

/**
 * Hello world!
 *
 */
public class App {

    public static void main(String[] args) {
        Node start1 = new Node("1");
        Node start2 = new Node("2");
        Node start3 = new Node("3");
        Node start4 = new Node("4");
        Node start5 = new Node("5");
        Node start6 = new Node("6");
        Node start7 = new Node("7");
        Node start8 = new Node("8");
        Node start9 = new Node("9");
        Node start10 = new Node("10");
        Node start11 = new Node("11");
        Node start12 = new Node("12");
        Node start13 = new Node("13");
        
        connectNodes(start1, start2, 75);
        connectNodes(start1, start4, 140);
        connectNodes(start1, start5, 118);
        connectNodes(start2, start3, 71);
        connectNodes(start3, start4, 151);
        connectNodes(start4, start12, 99);
        connectNodes(start4, start9, 80);
        connectNodes(start5, start6, 111);
        connectNodes(start6, start7, 70);
        connectNodes(start7, start8, 75);
        connectNodes(start8, start10, 120);
        connectNodes(start9, start10, 146);
        connectNodes(start9, start11, 97);
        connectNodes(start10, start11, 138);
        connectNodes(start11, start13, 101);
        connectNodes(start12, start13, 211);

        System.out.println(findPath(start1, start13));
    }
    
    public static List<Node> findPath(Node start, Node finish) {
        TreeMap<Integer, Node> frontier = new TreeMap<Integer, Node>();
        Set<Node> explored  = new HashSet<Node>();
        
        frontier.put(0, start);
        while(!frontier.isEmpty()) {
            System.out.println(frontier);
//            if (frontier.isEmpty()) {
//                throw new IllegalStateException("empty frontier");
//            }
            Entry<Integer, Node> firstEntry = frontier.pollFirstEntry();
            Node closest = firstEntry.getValue();
            System.out.println(firstEntry.getKey() + " " + firstEntry.getValue());
            if (finish.equals(closest)) {
                System.out.println("FINISH!!!!");
                System.out.println(firstEntry.getKey() + " " + firstEntry.getValue());
                return Arrays.asList(new Node[]{closest});
            }
            explored.add(closest);
            
            for (Entry<Integer, Node> entry : closest.getChildren().entrySet()) {
                if (!explored.contains(entry.getValue())) {
                    frontier.put(firstEntry.getKey()+entry.getKey(), entry.getValue());
                }
            }
        }
        
        return null;
    }
    
    private static void connectNodes(Node node1, Node node2, int dist) {
        node1.addEdge(node2, dist);
        node2.addEdge(node1, dist);
    }
    
    private static void printGraph(Node start) {
        System.out.println(start);
//        for (Node node : start.getChildren().keySet()) {
//            if (node.equals(start)) {
//                printGraph(node);
//            }
//        }
    }
}