Skip to content

Instantly share code, notes, and snippets.

@justcoding121
Last active Oct 12, 2015
Embed
What would you like to do?
/*
* 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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment