Priority Queues

Hello,

I'm trying to implement a std::priority_queue, but the literature is quite fuzzy, and I don't understand some of the things I need to do.

I have a class called Paths, which contains, as its base object, a std::list <unsigned int>, which describes a certain path on a graph theoretic tree, with each node identified by an unsigned int. Each Path object has a function .getLength(), which returns the weight of the path, where each edge between nodes has a different weight / length.

I then have a list of Path objects, called list <Paths> finallist, which contains numerous Path objects as well as lots of other methods.

I'd like to copy the list of Path objects into a priority queue, probably using a std::vector as base container ( as we need random access, so the list won't do ), such that the queue maintains the different Path objects ordered with respect to their .getLength() attribute ( which returns a double ), with shortest paths first.

An integer queue seems very easy, and I've even seen examples where people use

Code:

---

priority_queue <myClass> pq;

---

to sort their class objects, but these only have a single member in their private space, which the queue seems happy to sort by with no additional instructions. I'd like to sort by the value returned by .getLength().

Any help or pointers in the right direction would be hugely appreciated.

Thank you very much,
Quentin

You can overload a free function operator< in the same namespace as the Path class that compares Path objects according to the result of the getLength() member function. std::priority_queue will then use this to determine the priority.

Thanks for the help, laserlight. That makes sense, though it's gotten a little more complicated now. The function .getLength(Graph &) actually takes an argument, which is itself another class ( you guessed, Graph ). Should I be doing something like this ?

Code:

---

bool Paths::operator>(Paths otherPath, Graph & myGraph)
{
    if(this.getLength(myGraph) > otherPath.getLength(myGraph))
        return true;
    else
        return false;
}

---

If so, how do I use the operator correctly, passing the Graph object ? This would make it a ternary operator, which doubtlessly, is wrong...

Thanks again,
Quentin

Since a Path must belong to a Graph and cannot exist without it, it might make sense to store a pointer to the Graph in the Path. In such a case, you can then implement:

Code:

---

size_type Path::getLength() const
{
    // ...
}

bool operator<(const Path& lhs, const Path& rhs)
{
    return lhs.getLength() < rhs.getLength();
}

---

But if you wish to keep to your original design, then you would need to create a function object to serve as the predicate for the comparison. This function object type would be the third template argument to priority_queue (so you also need to specify the second template argument, which is std::deque by default).

So, when creating the priority_queue, you create and pass it the function object, initialising the function object with a const reference to the Graph. This function object would presumably store a pointer to this Graph object, and thus use it in the current getLength() member function. (You presumably want to have const reference to a Graph, not a non-const reference, unless finding the length of a path in a graph can change the graph itself.)

Your first suggestion is great, but it would confuse other things, such as creating empty Paths which aren't linked to specific Graph objects yet. Some Path objects are temporary variables, which shouldn't be linked to a specific graph. I'm therefore constrained to your second suggestion.

The second suggestion, however, isn't quite clear to me. Perhaps this would work as alternative ?
The function .getLength(const Graph &) simply returns the private variable length so long as it is not equal to 0. This is because it is initiated to 0 in the constructor, and then, if found to be zero when .getLength(const Graph &) is called, the length is calculated by iterating over the path, using the Graph argument's connectivity. Therefore, perhaps I can overload the operator> using the private length variable instead of the .getLength(const Graph &) method, but ensure that this method is always called prior to insertion of a path into the priority queue ?

With respect to your second suggestion, trying to understand it : the std::priority_queue takes three optional arguments :

Code:

---

template < class T, class Container = vector<T>,
          class Compare = less<typename Container::value_type> > class priority_queue;

---

Is this correct :
- T is the type of elements, in my case, Paths
- Container would be vector <Paths> ( unless deque is fine ? )
- Compare is a boolean function that takes in three arguments, two of type Paths and one of type const Graph &, returns false if I want the first of the two paths higher in the priority queue.

Comparing with the documentation, I realise I've mostly regurgitated what you said, which I think is a good thing ! Thanks very much for the help, I'll try that now.

Q

Quote:

---

Originally Posted by Korhedron

- Container would be vector <Paths> ( unless deque is fine ? )

---

deque should be fine.

Quote:

---

Originally Posted by Korhedron

- Compare is a boolean function that takes in three arguments, two of type Paths and one of type const Graph &, returns false if I want the first of the two paths higher in the priority queue.

---

No, the predicate has to take two arguments, both of type Paths (though of course they would actually be const reference parameters). It would return true if the first argument is "less than" the second. Therefore, you need a function object, not just a function, since you need to refer to the Graph object, i.e., you need to store some state.

A vector is probably the better choice for a priority_queue. deque is the default for queue because a queue needs pop_front.

laserlight, CornedBee, thanks for the help. I think I'm almost there, but still getting an error. I can't find a way to fix it. Any ideas would be really welcome ! Thanks.

Comparison Class .h

Code:

---

// pathcompare.h
// Class PathCompare
#ifndef _PATHCOMPARE_H
#define _PATHCOMPARE_H

#include "paths.h"
#include "graph.h"


class PathCompare
{
        public:
               
                // Constructor
                PathCompare(const Graph &);
               
                // () Operator
                bool operator() (Paths &, Paths &);
               
               
        private:
               
                // Graph variable
                const Graph * graph;
};


#endif

---

Comparison Class .cpp

Code:

---

// pathcompare.cpp
// Class PathCompare
#include "pathcompare.h"



PathCompare::PathCompare(const Graph & mygraph)
{
        graph = mygraph;
}



bool PathCompare::operator() (Path & left, Path & right)
{
        return left.getLength(graph) < right.getLength(graph)
}

---

Snippet of main.cpp

Code:

---

// ...

// Get the direct paths from sources to sinks in graph Q
list <Paths> finallist = directpaths(Q);


// Create a PathCompare object, with graph argument
PathCompare comparefunction(Q);
   
// Create a priority queue storing Paths objects, in a vector container, using the PathCompare object above
priority_queue < Paths, vector <Paths>, comparefunction > pq;
   
// Fill the queue
for(list<Paths>::iterator i = finallist.begin(); i != finallist.end(); i++)
{
    pq.push(*i);
}

// ...

---

This produces these errors on compile :

Code:

---

main.cpp: In function 'int main()':
main.cpp:136: error: comparefunction' cannot appear in a constant-expression
main.cpp:136: error: template argument 3 is invalid
main.cpp:136: error: invalid type in declaration before ';' token
main.cpp:141: error: request for member 'push' in 'pq', which is of non-class type 'int'

---

136 is the line which creates the priority_queue object.


Thank you very much for any help !

It looks like you made a typographical error or two, and were not const-correct. I would simply define the function object with implementation inlined:

Code:

---

#ifndef PATHCOMPARE_H
#define PATHCOMPARE_H

// pathcompare.h
// Class PathCompare

#include "paths.h"
#include "graph.h"

class PathCompare
{
public:
    explicit PathCompare(const Graph& mygraph) : graph(&mygraph) {}

    bool operator()(const Paths& left, const Paths& right) const
    {
        return left.getLength(*graph) < right.getLength(*graph);
    }
private:
    const Graph* graph;
};

#endif

---

Then to use it:

Code:

---

const PathCompare comparefunction(Q);

priority_queue < Paths, vector <Paths>, PathCompare > pq(comparefunction);

---

Thanks very much, that works - though I've removed const keywords because, as you've realised, I'm not comfortable with them. The main issue was the way I was passing the PathCompare object to the priority queue - thank you very much for clarifying that.

Your help was hugely appreciated, thanks again very much !

Q

If you're using the standard library, you can't really run from const. Besides, it's one of the most useful tools in C++.