gistfile1.txt

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package aiproject;


import java.awt.Point;
import java.util.*;

//searcher class implements the A* algorithm
public class Searcher {

    public Node rootNode;
    public String results = "";
    public String opennodes = "";
    public ArrayList nodes = new ArrayList();       //all the nodes will be represented using this arraylist
    ArrayList open = new ArrayList();               //list of open nodes to visit
    ArrayList closed = new ArrayList();
    public int[][] adjMatrix;                       //Edges will be represented as adjacency Matrix
    public String distance_root = "";
    public String estimated_dist = "";
    int size;

    public void setStartNode(Node n) {
        this.rootNode = n;
    }

    public void addNode(Node n) {
        nodes.add(n);
    }
    //return a particular node using its city name

    public Node getNode(String cityname) {
        ListIterator listIterator = nodes.listIterator();
        Node tmp = null;

        while (listIterator.hasNext()) {

            tmp = (Node) listIterator.next();

            if (tmp.city.equals(cityname)) {
                return tmp;
            }
        }
        return tmp;
    }

    public String getAllOpenNodes() {
        ListIterator listIterator = open.listIterator();
        String tmp = "";

        while (listIterator.hasNext()) {
            tmp = tmp + "," + ((Node) listIterator.next()).city;
        }
        return tmp;
    }
    //set a particular node using city name

    public void setNode(String city, Node N) {
        for (int i = 0; i < nodes.size(); i++) {
            if (((Node) nodes.get(i)).city.equals(city)) {
                nodes.set(i, N);
                break;
            }
        }
    }

    //This method will be called to make connection between two nodes based on the input file
    public void connectNode(Node start, Node end) {
        if (adjMatrix == null) {
            size = nodes.size();
            adjMatrix = new int[size][size];
        }

        int startIndex = nodes.indexOf(start);
        int endIndex = nodes.indexOf(end);
        adjMatrix[startIndex][endIndex] = 1;
        adjMatrix[endIndex][startIndex] = 1;
    }
    //get the next node to visit from a open list of possible nodes with a priority for minimual distance hueristic

    private Node getUnvisitedChildCity(Node current, Node destination) {

        int index = nodes.indexOf(current);
        int j = 0;
        double distance = 0d;

        while (j < size) {
            if (adjMatrix[index][j] == 1 && ((Node) nodes.get(j)).visited == false) {

                Node tmp = (Node) nodes.get(j);
                // System.out.println("parent:"+current.city+" child:"+tmp.city);

                if (closed.contains(tmp.city) == false) {
                    tmp.parent = current.city;
                    tmp.dist_from_root = current.dist_from_root + getlength(current, tmp);
                    tmp.estimated_dist_destination = getlength(tmp, destination);
                    nodes.set(j, tmp);
                    open.add(tmp);
                    closed.add(tmp.city);
                } else {

                    Node tp = ((Node) ((ArrayList) nodes.clone()).get(j));


                    if (!tmp.parent.equals(current.city)) {
                        if (tmp.dist_from_root + tmp.estimated_dist_destination > current.dist_from_root + getlength(current, tmp) + getlength(tmp, destination)) {
                            tp.dist_from_root = current.dist_from_root + getlength(current, tp);
                            tp.estimated_dist_destination = getlength(tp, destination);
                            tp.parent = current.city;
                            nodes.set(j, tp);
                            open.add(tp);

                        }
                    }

                }
            }
            j++;
        }


        Node temporary_node = null;
        j = 0;
        if (open.isEmpty() == false) {
            distance = ((Node) open.get(open.size() - 1)).dist_from_root + ((Node) open.get(open.size() - 1)).estimated_dist_destination;
        }

        String city = "Not Found";
        //choose the node with minumum estimated distance to destination
        for (int i = 0; i < open.size() - 1; i++) {
            if (distance > ((Node) open.get(i)).dist_from_root + ((Node) open.get(i)).estimated_dist_destination) {
                distance = ((Node) open.get(i)).dist_from_root + ((Node) open.get(i)).estimated_dist_destination;
                city = ((Node) open.get(i)).city;
                temporary_node = ((Node) open.get(i));
                j = i;
            }

        }

        //if the present node is the best node then choose that node
        if ("Not Found".equals(city)) {
            j = open.size() - 1;
            if (j == -1) {
                return null;
            }

            temporary_node = ((Node) open.get(open.size() - 1));
            open.remove(open.size() - 1);
        } else {
            open.remove(j);
        }

        return temporary_node;
    }

    //A* search is done using this function
    public void search(Node dest) {
        //initialize the parent node

        Node destination = dest;
        rootNode.visited = true;
        rootNode.parent = rootNode.city;
        rootNode.dist_from_root = 0d;
        rootNode.estimated_dist_destination = getlength(rootNode, destination);

        rootNode.path = rootNode.city;
        setNode(rootNode.city, rootNode);
        Node child = rootNode;

        while (true) {
            child = getUnvisitedChildCity(child, destination);

            //visit the child nodes 
            if (child != null) {

                child.visited = true;
                child.path = getNode(child.parent).path + " to " + child.city;
                setNode(child.city, child);
                String tp[] = child.path.trim().split(" to ");
                for (int m = 0; m < tp.length - 1; m++) {
                    results = results + getNode(tp[m]).p.x + "/" + getNode(tp[m]).p.y + "/" + getNode(tp[m + 1]).p.x + "/" + getNode(tp[m + 1]).p.y + ",";
                }

                results = results + "--";
                if (child.city.equals(destination.city)) {

                    String[] tt = child.path.trim().split(" to ");
                    String comp = getAllOpenNodes();
                    for (int ll = 0; ll < tt.length; ll++) {

                        if (comp.contains(tt[ll])) {
                            comp = comp.replace(tt[ll] + ",", "");
                        }
                    }
                    opennodes = opennodes + comp + "--";
                } else {
                    opennodes = opennodes + getAllOpenNodes() + "--";
                }
                distance_root = distance_root + child.dist_from_root + "--";
                estimated_dist = estimated_dist + child.estimated_dist_destination + "--";
                if (child.city.equals(destination.city)) {
                    break;
                }

            } else {
                System.out.println("No path found! Check and make sure that all cities are reachable by atleast one path");
                return;
            }
        }


    }
    //return the distance between any two  nodes

    private double getlength(Node a, Node b) {
        Point p1 = a.p;
        Point p2 = b.p;
        return p1.distance(p2);
    }

    void opener() {
    }
//used to find the minimum number of links to destination

    public int getLinks(Node start, Node finish) {
        Map<Node, Boolean> vis = new HashMap<>();
        Map<Node, Node> prev = new HashMap<>();
        List directions = new LinkedList();
        Queue q = new LinkedList();
        Node current = start;
        q.add(current);
        vis.put(current, true);
        while (!q.isEmpty()) {
            current = (Node) q.remove();
            if (current.equals(finish)) {
                break;
            } else {
                for (Object node : (ArrayList) getUnvisitedChildNode(current)) {
                    if (!vis.containsKey((Node) node)) {
                        q.add(node);
                        vis.put((Node) node, true);
                        prev.put((Node) node, current);
                    }
                }
            }
        }
        if (!current.equals(finish)) {
            System.out.println("can't reach destination");
            System.out.println(start.city + " " + finish.city);
        }
        for (Node node = finish; node != null; node = prev.get(node)) {
            directions.add(node);

        }

        return directions.size() - 1;
    }
//used by getlinks functions to get the childrens

    private ArrayList getUnvisitedChildNode(Node n) {

        int index = nodes.indexOf(n);
        ArrayList childrens = new ArrayList();
        int j = 0;
        while (j < size) {
            if (adjMatrix[index][j] == 1) {
                childrens.add((Node) nodes.get(j));
            }
            j++;
        }
        return childrens;
    }

    void close() {
        //  out.close();
    }

    //A* search for minimum links is done using this function
    public void search1(Node dest) {
        //initialize the parent node

        Node destination = dest;
        rootNode.visited = true;
        rootNode.parent = rootNode.city;
        rootNode.links_from_root = 0;
        rootNode.est_links_to_dest = getLinks(rootNode, destination);
        rootNode.path = rootNode.city;
        setNode(rootNode.city, rootNode);
        Node child = rootNode;

        while (true) {
            child = getUnvisitedChildCity1(child, destination);

            if (child != null) {
                child.visited = true;
                child.path = getNode(child.parent).path + " to " + child.city;
                setNode(child.city, child);
                String tp[] = child.path.trim().split(" to ");
                for (int m = 0; m < tp.length - 1; m++) {
                    results = results + getNode(tp[m]).p.x + "/" + getNode(tp[m]).p.y + "/" + getNode(tp[m + 1]).p.x + "/" + getNode(tp[m + 1]).p.y + ",";
                }

                results = results + "--";
                if (child.city.equals(destination.city)) {

                    String[] tt = child.path.trim().split(" to ");
                    String comp = getAllOpenNodes();
                    for (int ll = 0; ll < tt.length; ll++) {

                        if (comp.contains(tt[ll])) {
                            comp = comp.replace(tt[ll] + ",", "");
                        }
                    }
                    opennodes = opennodes + comp + "--";
                } else {
                    opennodes = opennodes + getAllOpenNodes() + "--";
                }
                distance_root = distance_root + child.links_from_root + "--";
                estimated_dist = estimated_dist + child.est_links_to_dest + "--";
                if (child.city.equals(destination.city)) {
                    break;
                }

            } else {
                System.out.println("No path found! Check and make sure that all cities are reachable by atleast one path");
                return;
            }
        }


    }
//minimum links A* uses this function

    private Node getUnvisitedChildCity1(Node current, Node destination) {

        int index = nodes.indexOf(current);
        int j = 0;
        double distance = 0d;

        while (j < size) {
            if (adjMatrix[index][j] == 1 && ((Node) nodes.get(j)).visited == false) {

                Node tmp = (Node) nodes.get(j);


                if (closed.contains(tmp.city) == false) {
                    tmp.parent = current.city;
                    tmp.links_from_root = current.links_from_root + 1;
                    tmp.est_links_to_dest = getLinks(tmp, destination);
                    nodes.set(j, tmp);
                    open.add(tmp);
                    closed.add(tmp.city);
                } else {

                    Node tp = ((Node) ((ArrayList) nodes.clone()).get(j));

                    if (!tmp.parent.equals(current.city)) {
                        if (tmp.links_from_root + tmp.est_links_to_dest > current.links_from_root + getLinks(current, tmp) + getLinks(tmp, destination)) {
                            tp.links_from_root = current.links_from_root + getLinks(current, tp);
                            tp.est_links_to_dest = getLinks(tp, destination);
                            tp.parent = current.city;
                            nodes.set(j, tp);
                            open.add(tp);

                        }
                    }

                }
            }
            j++;
        }




        Node temporary_node = null;
        j = 0;
        if (open.isEmpty() == false) {
            distance = ((Node) open.get(open.size() - 1)).links_from_root + ((Node) open.get(open.size() - 1)).est_links_to_dest;
        }

        String city = "Not Found";
        //choose the node with minumum estimated links to destination
        for (int i = 0; i < open.size() - 1; i++) {
            if (distance > ((Node) open.get(i)).links_from_root + ((Node) open.get(i)).est_links_to_dest) {
                distance = ((Node) open.get(i)).links_from_root + ((Node) open.get(i)).est_links_to_dest;
                city = ((Node) open.get(i)).city;
                temporary_node = ((Node) open.get(i));
                j = i;
            }

        }

        //if the present node is the best node then choose that node
        if ("Not Found".equals(city)) {
            j = open.size() - 1;
            if (j == -1) {
                return null;
            }

            temporary_node = ((Node) open.get(open.size() - 1));
            open.remove(open.size() - 1);
        } else {
            open.remove(j);
        }

        return temporary_node;
    }
}