Thread: Priority Queues

  1. #1
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    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
    Last edited by Korhedron; 07-19-2010 at 09:35 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    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:riority_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
    Last edited by Korhedron; 07-19-2010 at 10:48 AM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    A vector is probably the better choice for a priority_queue. deque is the default for queue because a queue needs pop_front.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    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 !

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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);
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209
    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

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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++.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Applications of priority queues
    By C_Enthusiast in forum C Programming
    Replies: 2
    Last Post: 06-21-2010, 09:07 AM
  2. crazy pipe/fork
    By fortune2k in forum C Programming
    Replies: 8
    Last Post: 03-13-2009, 11:28 AM
  3. priority list won't work, i give up
    By teamster in forum C Programming
    Replies: 8
    Last Post: 10-19-2006, 12:26 PM
  4. Priority queue's
    By Cmuppet in forum C Programming
    Replies: 7
    Last Post: 11-23-2004, 02:21 PM
  5. BST implementation of priority queues
    By jcleong in forum C Programming
    Replies: 1
    Last Post: 05-14-2002, 09:09 AM