3
\$\begingroup\$

I am writing the code for A*, Uniform cost search and Greedy best first search algorithms in Java. I have finished the code which is working fine but I have used a bit different design strategy while writing this code and I want this code to be as efficient and as clean as possible so I could really use your help.

The basic idea I have used is all 3 are best first search algorithms, just the difference is that they way in which they put nodes in queue. For A* the queue priority is based on distance plus heuristics value, while for greedy it's just the heuristic value, so I wrote code for BestFirstSearch and wrote a different Queue for each algorithm. Below is my code

BestFirstSearch.Java

import java.util.Collections;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class BestFirstSearch {
    Graph g;
    /* Dont set infinity to Integer.MAX_VALUE it will result 
       into integer overflow when you add heuristics cost
       into it */    
    int INFINITY = 100000007;

    /* Priority queue for holding pairs of vertex id */
    BestFirstSearchQueue queue;

    /* Previous node in path */
    int previousNode[];

    /* Distance of this node from source */
    int shortestDistance[];

    /* Debugging related data */
    ArrayList<Integer> exploredCities;

    public BestFirstSearch(Graph g, BestFirstSearchQueue queue) {
        this.g = g;
        this.queue = queue;
        previousNode = new int[g.getV()];
        shortestDistance = new int[g.getV()];
        for (int i = 0; i < g.getV(); i++) {
            previousNode[i] = -1;
            shortestDistance[i] = INFINITY;
        }
        exploredCities = new ArrayList<>();
    }


    private void explore(int currNode, ArrayList<Integer> adjList) {
        for (int succesor : adjList) {
            int currDist = shortestDistance[currNode] + 
                g.getEdgeCost(currNode, succesor);            
            if (shortestDistance[succesor] > currDist) {
                // Distance should never contain heuristic cost
                shortestDistance[succesor] = currDist;
                /* Update if already exitst else add*/
                queue.add(succesor, currDist);
                previousNode[succesor] = currNode;
            }
        }
        exploredCities.add(currNode);
    }

    public SearchData getPathData(int src, int dst) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        int curr = dst;
        while (curr != src && previousNode[curr] != -1) {
            path.add(curr);
            curr = previousNode[curr];
        }
        path.add(src);
        Collections.reverse(path);
        SearchData sData = new SearchData(shortestDistance[dst],
                                          path,
                                          exploredCities);
        return sData;
    }

    public SearchData search(int src, int dst) {
        shortestDistance[src] = 0;
        queue.add(src, 0);
        while (!queue.isEmpty() &&
               queue.peek() != dst) {
            int currNode = queue.poll();
            ArrayList<Integer> adjList = g.getAdjVertices(currNode);
            explore(currNode, adjList);
        }
        return getPathData(src, dst);
    }

}

BestFirstSearchQueue.java - interface for API

import java.util.PriorityQueue;
public interface BestFirstSearchQueue {
    /* Provides a common interface for all best first search graph
       queues. Implement this interface according to search 
       strategy (viz. A*, Uniform cost, Greedy) and pass this queue
       to BestFirstSearch Class. */
    /* This queue interface works on vertex id of each node, basically
       it can store a particular vertex with its cost and retrieve these
       values as per request from search function. The heuristic calculations
       happen inside this class - search function doesn't need to 
       know about these heuristics */

    /* This is the Priority queue used by all classes, comparator will 
       change */

    int initialCapacity = 512;
    /* Adds a new vertex into queue with given cost if its not already
       present, if it is already present in queue then replace it with 
       this value */
    public void add(int vertex, int cost);

    /* returns vertex id of top element of queue */
    public int poll();

    /* removes and returns topmost element of queue */
    public int peek();

    /* checks if queue is empty */
    public boolean isEmpty();
}

AStarSearchQueue.java

import java.util.HashMap;
import java.util.Comparator;
import java.util.PriorityQueue;

class AStarSearchQueue implements BestFirstSearchQueue {
    PriorityQueue<Integer> queue = null;
    /* Hashmap for storing path distance to a node */
    HashMap<Integer, Integer> distanceMap;
    /* Hashmap for storing heuristic value for a node */
    HashMap<Integer, Double> heuristicsMap;

    public AStarSearchQueue() {
        queue = new PriorityQueue<>(initialCapacity,
                                    new AStarCostComparator());
        distanceMap = new HashMap<>();
    }

    public AStarSearchQueue(HashMap<Integer, Double> heuristics) {
        this();
        heuristicsMap = heuristics;
    }

    public AStarSearchQueue(double heuristics[]) {
        this();
        heuristicsMap = new HashMap<>();
        int vertex = 0;
        for(double cost : heuristics) {
            heuristicsMap.put(vertex++, cost);
        }
    }

    public void add(int vertex, int value) {
        if (queue.contains(vertex)) {
            queue.remove(vertex);
            distanceMap.remove(vertex);
        }         
        distanceMap.put(vertex, value);
        queue.add(vertex);
    }

    public int poll() {
        return queue.poll();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public int peek() {
        return queue.peek();
    }

    /* Comparator for A* search strategy */
    class AStarCostComparator implements Comparator<Integer> {
        public int compare(Integer o1, Integer o2) {
            double cost1 = distanceMap.get(o1);
            double cost2 = distanceMap.get(o2);
            cost1 += heuristicsMap.get(o1);
            cost2 += heuristicsMap.get(o2);
            if (cost1 > cost2)
                return 1;
            else if (cost1 == cost2)
                return 0;
            return -1;
        }
    }
}

Code for UniformSearchQueue.java and GreedySearchQueue.java is almost same as AStarSearchQueue.java except that it has different comparator class which compares heuristics (for greedy) and cost distance (for uniform).

And I create Object for BestFirstSearch as follows:

    BestFirstSearch bfs = new BestFirstSearch(usa.getGraph(),
                                              new AStarSearchQueue(usa.getHeuristics(src)));
\$\endgroup\$
1
\$\begingroup\$

Missing classes

This is not a complete code. It is missing Graph and SearchData. Please provide those. In particular, I'm not sure what Graph.getV() does, so even though I belieave there's a weak point in BestFirstSearch that relates to it, I will not investigate.

AStarSearchQueue is not a Queue

But it could be. Why make it have a delegate PriorityQueue field, and not simply extend PriorityQueue<Integer> ? If you're not going to change implementations, this will be more natural, and reduce the objects count.

And don't worry, to your BestFirstSearch class, these queues will not be PriorityQueues, but BestFirstSearchQueues, so not fear of exposing to many methods.

BestFirstSearchQueue interface has a constant initialCapacity field

This is considered bad practice. If you're an interface, you have NO IDEA what the implementations are. How come do you know in advance what kind of initial size is good? It is not only implementation-dependant, it is also instance-dependant (if my problem is small, why do i want 512? if my problem is huge, why limit to 512?). This is arbitrary, and should go.

Units

Why are your distances stored as Integers, when your heuristic allows Double? Make it all store Doubles.

Declaration types

Always declare Objects as being of the highest-level class that you can get away with. For instance:

ArrayList<Integer> exploredCities;

Must become:

List<Integer> exploredCities;

This way you'll be able to easily switch implementation later on.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.