CODEWITHSUNDEEP
javapriority-queue
orderof1
orderof1

Reputation: 12751

java.util.PriorityQueue's elements does not move up on poll()

I am implementing a BFS on a graph, where nodes are marked by objects of a State class (I have implemented an implicit equals to method for comparison).

I have implemented my queue using a PriorityQueue with a comparator that returns 1 since I want to expand the program to handle DFS, Astar etc, which I can do by just changing the logic inside the comparator

Here is the relevant code:

//BFSComparator.java

import java.util.Comparator;

public class BFSComparator implements Comparator<State>{
    @Override public int compare(State x, State y) {
       return 1;
    }
}

//solver.java

Comparator comparator = new BFSComparator();
PriorityQueue<State> frontierList = new PriorityQueue<State>(500,comparator); //List of nodes to be expanded
frontierList.add(seed state0);
while (!frontierList.isEmpty()){
        curState = frontierList.poll();
        //handle, expand and add child states to frontierList

While iterating through the list and printing elements present, I found that some elements do not move up the rank (example, {a,b,c,d,e} on poll becomes {b,e,c,d} on poll() rather than {b,c,d,e}), and hence, it does not perform FIFO.

for(State x:frontierList) {
             //print x
}

1) Is there something wrong with my comparator?

2) Is there a better way to do this generically? i.e. , a better Container than priority queue that I can just add to while changing the logic behind the sorting rather than use Queues and stacks with difference call names like push and pop? This would be helpful when I sort them later based on heuristics. Or should I just use a linked list and perform an insertion sort based approach?

EDIT: I'd like to make it a little more clear. I'm trying to implement a collection that I can throw things at with a common add(State) or State x = remove() irrespective of DFS or BFS (FIFO or LIFO) or other priority based algorithms like A-Star and Beam Search.

I'm probably going to extend collection and implement add and other methods.

Upvotes: 0

Views: 589

Answers (1)

kdlan
kdlan

Reputation: 15

public int compare(State x, State y)

This method return a positive value means x > y, a negative value means x < y and 0 means x==y.

I thouht you should use Queue to declare frontierList instead

When you need DFS, use LinkedList<State>

When you need BFS, use PriorityQueue<State> and a Comparator<State> return the min or max State you want

Upvotes: 1

Related Questions