Help with priority queues

[pjakubo86]

Hey guys, I was hoping you could help me with a little problem I'm having. I'd like to create a priority queue from the STL of Node objects. Node is a class I've written myself. From what I understand, the STL uses the < (less than) operator (well, it uses less<>) to compare objects when it sorts them in the queue, so I had to overload the < (less than) operator in my Node class. However, when I try to do this, I get the following error in Visual C++:

error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const Node' (or there is no acceptable conversion)

could be 'bool Node::operator <(Node)'
while trying to match the argument list '(const Node, const Node)'

while compiling class template member function 'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
with
[
_Ty=Node
]
c:\program files\microsoft visual studio 8\vc\include\queue(219) : see reference to class template instantiation 'std::less<_Ty>' being compiled
with
[
_Ty=Node
]
see reference to class template instantiation 'std::priority_queue<_Ty>' being compiled
with
[
_Ty=Node
]

OK, so it looked like it was expecting two Nodes in the arguement list. However, if I try to include two Node arguements, Visual C++ tells me that operator < has too many arguements.

Here is my overloaded operator < code:

bool Node::operator < (Node compareNode) {
if (getHeuristic() < compareNode.getHeuristic()) {
return true;
}
else {
return false;
}
}

and here is how I'm declaring the priority queue:

priority_queue<Node> fringe;

Can anyone point out my obvious flaw? I'm baffled!

Thanks so much!

[vijayan121]

make your operator< const correct.

bool Node::operator< ( const Node&) const

[Infarction]

vijayan's solution should be correct. There's a few things different between his and yours, though, which are important. First, his parameter takes a const object. This allows you to have a const Node on the right side of the expression. Second, he uses the pass-by-reference mechanism (the &) to avoid copying the node unnecessarily. Third, and the solution to your question, is the const at the end of the line which dictates that the function may be called for constant objects (which would be on the left-hand side).

[pjakubo86]

Thanks so much guys! Works perfectly...

[pjakubo86]

Actually, I have one more quick question. I'd actually like this to be a priority_queue of Node* (pointers to Node), but if I do that, then it sorts the queue using pointer arithmetic. So the Node*s with the lower addresses are put at the front and the higher ones are at the back. Is there any way for me to define a custom way to sort them in the Node class? Like, can I overload the "<" operator for just Node pointers somehow? Know what I mean?

[Infarction]

How are you currently sorting them?

[pjakubo86]

How are you currently sorting them?

Right now, I'm just using the default priority_queue sort which uses less<Typ> to sort the Node objects by their heuristic value which is a member variable of the Node class. However, I'd really like the priority_queue to use Node* instead. Is this possible? It's not that I absolutely can't use Node objects, it would just be easier to integrate with the rest of my code if they were Node*s.

[vijayan121]

Actually, I have one more quick question. I'd actually like this to be a priority_queue of Node* (pointers to Node), but if I do that, then it sorts the queue using pointer arithmetic. So the Node*s with the lower addresses are put at the front and the higher ones are at the back. Is there any way for me to define a custom way to sort them in the Node class? Like, can I overload the "<" operator for just Node pointers somehow? Know what I mean?

pointers are a standard type and you can not define how pointers are to be
compared anywhere. however, you can tell the priority_queue of Node*
how you want priorities to be compared.
a. write a binary predicate to compare nodes

struct compare_node_pointers
{
  bool operator() ( const Node* first, const Node* second ) const
  {
    // return true if first has lower priority than second.
   //  false otherwise.
  }
};

b. specify the predicate to the priority_queue

typedef std::priority_queue< Node*,  std::vector<Node*>, 
                              compare_node_pointers > my_prioroty_queue ;
// use object(s) of type my_prioroty_queue where required

remember that the predicate must be a relation that is asymetric,
irreflexive and transitive; ie. one that imposes a strict oredering
on the sequence.

[pjakubo86]

Thanks for the reply! I actually had figured this out already but forgot to post here about it. The only trouble I'm having is that sometimes the heuristic value for two of the Nodes is the same, but I can't check for that in the predicate. If I try to compare using >= or ==, an assertion gets thrown by visual c++. I'd like to tell the priority queue that if two heuristic values are equal, it should consider the new value that is being inserted in the queue to be lesser one so that newer generated Nodes are inspected last for Nodes with an equal heuristic.

Right now, it seems to work while I'm debugging in Visual Studio, i.e. the Nodes appear in the correct order, but when I pop them off to inspect them, Nodes having the same priority seem to rendomly jump around in the queue. This seems odd...

I assume this is because my predicate does not meet the criteria above. Perhaps I should also number the nodes in increasing order as they are generated and then compare not just the heuristic value but when the node was generated - this should strictly order them, no?

[pjakubo86]

OK, this is just strange:

If I use this predicate (which is wrong):

struct comp
{
bool operator() ( const Node* first, const Node* second ) const
{
if (first->getHeuristic() > second->getHeuristic()) {
return true;
}
else if (first->getOrder() < second->getOrder()) {
return true;
}
else {
return false;
};
}
};

then the Nodes are ordered correctly by order, just backwards. So the most recently added Node becomes the next to pop off if the heuristics are equal. Here is the output showing this (Node value - heuristic value - order generated):

346 - 0 - 6
344 - 2 - 5
355 - 2 - 4
335 - 2 - 3
445 - 2 - 2
245 - 2 - 1

See, I would like all the ones with heuristic value of 2 to be ordered in increasing order.

However, if I use the correct predicate:

struct comp
{
bool operator() ( const Node* first, const Node* second ) const
{
if (first->getHeuristic() > second->getHeuristic()) {
return true;
}
else if (first->getOrder() < second->getOrder()) {
return false;
}
else {
return false;
};
}
};

then the order turns out all jumbled, like this:
346 - 0 - 6
245 - 2 - 1
335 - 2 - 3
344 - 2 - 5
445 - 2 - 2
355 - 2 - 4

Which is not right. Any ideas why?

[vijayan121]

However, if I use the correct predicate: ...

the predicate you have written (as the correct one) is equivalent to

bool operator() ( const Node* first, const Node* second ) const
{
  return first->getHeuristic() > second->getHeuristic() ;
  // in all other cases you are returning false
}

the order is not involved at all.

[pjakubo86]

Gah!!! No matter what I do, every time I make a correct implementation of this priority queue, when I try to run my program, I get this:
---------------------------
Microsoft Visual C++ Debug Library
---------------------------
Debug Assertion Failed!
Program: ...
File: c:\program files\microsoft visual studio 8\vc\include\algorithm
Line: 2025
Expression: invalid operator<
For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.
(Press Retry to debug the application)
---------------------------
Abort Retry Ignore
---------------------------

No matter what little tricks I try!

My current predicate looks like this:

struct comp
{
bool operator() ( const Node* first, const Node* second ) const
{
if (first->getHeuristic() > second->getHeuristic()) {
return true;
}
else if (second->getOrder() < first->getOrder()) {
return true;
}
else {
return false;
};
}
};

the only way this thing will run is if I make the < in the first else if statement a >, which orders them backwards. What the heck is going on???

[vijayan121]

Gah!!! No matter what I do, every time I make a correct implementation of this priority queue, when I try to run my program, I get this:
---------------------------
Microsoft Visual C++ Debug Library
---------------------------
Debug Assertion Failed!
Program: ...
File: c:\program files\microsoft visual studio 8\vc\include\algorithm
Line: 2025
Expression: invalid operator<
For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.
(Press Retry to debug the application)
---------------------------
Abort Retry Ignore
---------------------------

No matter what little tricks I try!

My current predicate looks like this:

struct comp
{
bool operator() ( const Node* first, const Node* second ) const
{
if (first->getHeuristic() > second->getHeuristic()) {
return true;
}
else if (second->getOrder() < first->getOrder()) {
return true;
}
else {
return false;
};
}
};

the only way this thing will run is if I make the < in the first else if statement a >, which orders them backwards. What the heck is going on???

i had said in my earlier reply

remember that the predicate must be a relation that is asymetric,
irreflexive and transitive; ie. one that imposes a strict oredering
on the sequence.

because it is important to understand it.

take two nodes
node_a ( getHeuristic returns 10, getOrder returns 6) and
node_b ( getHeuristic returns 11, getOrder returns 5)

comp()(a,b) returns true
if (first->getHeuristic() > second->getHeuristic()) // false
else if (second->getOrder() < first->getOrder()) // true

comp()(b,a) also returns true
if (first->getHeuristic() > second->getHeuristic()) // true

this is illogical; as per your predicate, both the following statements are true:
one: node_a has a lower priority than node_b
two: node_b has a lower priority than node_a
which is absurd. (not asymetric!)

[pjakubo86]

Thank you!!!! Finally, everything is working nicely! Thanks for putting up with my newbie skills. :-)

[vijayan121]

great. perhaps you would not be viewed as a newbie; certainly not in daniweb. thimgs like predicates are rocket science out here.