制作一个包含对 <int, custom class> 的最小堆

Question

我正在设计 Actor 和 Movie 对象的二分图，我想对其执行 djikstra 算法以找到两个 Actor 对象之间的最短路径。

我已经设计并构建了图表。如果您有兴趣，这是我的设计...

actor.h:

/* (Vertex) Object Class to represent actors */
 class ActorNode {
         friend class Movie;
         friend class ActorGraph;
     public:
         /*Member Variables*/
         std::string name;
         std::set<Movie*> movies;
         /*Constructor*/
         ActorNode(std::string name) : name(name) {}
         /*Destructor*/
         ~ActorNode();

         /*Getters and Setters*/
         std::string getName();
         void setName(std::string actor);

         /*Member Functions*/

 };

movie.h:

 class Movie {
     public:
         friend class ActorNode;
         friend class ActorGraph;

         std::string name;
         int year;
         int weight;
         std::set<ActorNode*> cast;
         /*Constructor*/
         Movie(std::string name, int year) : name(name), year(year), weight(1) {}
         /*Destructor*/
         ~Movie();
         /*Getters and Setters*/
         std::string getMovie();
         void setMovie(std::string movie);

         int getYear();
         void setYear(int yr);

         int getWeight();
         void setWeight(int wt);

         /*Member Functions*/
 };

ActorGraph.h:

  class ActorGraph {
       public:
         unordered_map<std::string,ActorNode*> actorMap;
         unordered_map<std::string,Movie*> movieMap;

         ActorGraph(void);

         bool loadFromFile(const char* in_filename, bool use_weighted_edges);

     };

函数 loadFromFile 从一个文件中读取，其中每一行都是他们主演的演员和电影以及年份。只是让我可以更轻松地从文本文件创建图表。

无论如何，我的问题是尝试用我的数据结构实现 djikstra。

我想使用一对整数的优先级队列，ActorNode* 其中整数将代表我与源的距离。默认情况下，优先级队列是 max_heap 但我想将其设为最小堆。这在显示此内容的其他一些主题中有所介绍...

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

所以为了我的目的，我试着按照这个例子...

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>,std::greater<int>> min_heap;

但它说参数 2 和 3 无效。有没有办法按照我的意愿制作优先级队列？谢谢！

更新

好的，我写了我的比较class...

/* comparison class */
 class pairCompare{
     public:
         typedef std::pair<int, ActorNode*> p;

         struct compare{
             bool operator()(const p& a, const p& b) {
                 if (a.first > b.first) return true;
                 else return false;
             }
         };

     private:
         std::priority_queue<p,std::vector<std::pair<int,ActorNode*>>,pairCompare> pq; };

但现在出现类型不完整的错误...

In file included from /usr/include/c++/5/queue:64:0,
                 from movie.h:6,
                 from actor.h:8,
                 from ActorGraph.h:14,
                 from ActorGraph.cpp:15:
/usr/include/c++/5/bits/stl_queue.h: In instantiation of ‘class std::priority_queue<std::pair<int, ActorNode*>, std::vector<std::pair<int, ActorNode*> >, pairCompare>’:
ActorGraph.h:61:84:   required from here
/usr/include/c++/5/bits/stl_queue.h:391:18: error: ‘std::priority_queue<_Tp, _Sequence, _Compare>::comp’ has incomplete type
       _Compare   comp;

我对此进行了研究，发现的解决方案是我应该在我的比较 class 中转发声明我的 ActorNode class，但没有修复错误。我是否正确创建了比较 class？试图让它产生一个优先级队列，它是一个最小堆。

其他问题：假设我可以得到这个比较 class 工作...我是否通过创建 comparePairs 对象来使用成员变量 pq？也许创建比较 class 将使用它的 pq 分开会更容易。与仅创建优先级队列并使用 comparePairs 作为要使用的比较的第三个参数相比，实际创建 comparePairs 对象似乎很奇怪。

Answer 1

这一行，

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>,std::greater<int>> min_heap;

在第二个参数中，

std::vector<std::pair<int,ActorNode*>。你不关闭尖括号。试试这个：

std::priority_queue<std::pair<int,ActorNode*>,std::vector<std::pair<int,ActorNode*>>,std::greater<int>> min_heap;

附带说明一下，当我以前做 Djikstra 或 A* 时，我发现 std::map 的表现比 std::priority_queue 好得多。不过，这可能是我这边的一个实施问题。如果您担心性能，您可能需要检查 std::map。

制作一个包含对 <int, custom class> 的最小堆

Making a min heap that holds pair <int, custom class>

c++

algorithm

graph

priority-queue

shortest-path