C ++和通用图距离算法 [英] C++ and generic graph distance algorithm

问题描述

我的问题如下。我通过编写图形库来学习C ++，并希望尽可能多地使用通用编程技术;因此，通过使用BOOST回答我的问题不会帮助我;事实上，我试图通过BOOST的代码来回答我的问题，但它是一个耻辱的经验，因为我甚至不能确定某些函数的定义;

My problem is the following. I am learning C++ by writing a graph library and want to make use of as much generic programming techniques as possible; hence, answering my question through "use BOOST" will not help me; in fact, I tried looking through BOOST's code for an answer to my question, but it was a humbling experience, since I can't even figure out where certain functions are defined; just way too high level of C++ for learning from it at my level.

也就是说，我的库以下列方式模板：

That said, my library is templated in the following way:

class edge { ... };

template <class edge_T>
class node { ... };

template <class edge_T, class node_T>
class graph { ... };

我使用从边或节点派生的类创建更复杂的图，

and I am creating more complex graphs by using classes derived from edge or node, so a weighted edge class would be simply

template <class T>
class weighted_edge : public edge {
   public:
     T weight;

   ...
};

现在的问题是我想在这个结构上实现一个算法，顶点。我可以很容易地写两个，一个用于加权边缘，一个用于未加权，但变化很小：可以访问 weighted_edge （或派生类）的成员字段，

The problem now is that I want to implement an algorithm on this structure that computes the shortest distance between two vertices. I could easily write two of these, one for weighted edges and one for unweighted, but the change is tiny: one would access a member field of weighted_edge (or derived classes) and the other would assume unitary weight.

有没有办法做到这一点，这样我可以只有一个代码为这两种情况？

Is there a way of doing this, so that I can have just one piece of code for both cases?

一个解决方案是使用一个成员函数 edge :: get_weight（）来返回权重（在未加权的情况下为'1' ，但这将迫使我使用一个特定的权重类型为边缘类是未加权的，所以它闻起来很滑稽。我的意思是，模板需要

One solution is to use a member function edge::get_weight() that would return the weight (or '1' in unweighted case), but that would force me to use a specific weight type for edge class that is unweighted, so it smells funny. I mean, the template would need to be

template <class T>
class edge {
   public:
     ...
     virtual T get_weight(void) { return T(1); } 
}

这不是用户友好的，

BGL使用 get（）函数来获取重量;我可以写一个函数返回1或 weight 取决于 edge_T ，但我关心的是当一个源自 edge 或 weighted_edge ？如果有人写：

BGL uses a get() function to obtain the weight; I could write a function that returns 1 or the weight depending on the edge_T, but my concern is what happens when one derives from edge or weighted_edge? If one writes:

template <class T>
inline T get_weight(edge & e) { return T(1); }

template <class T>
inline T get_weight(weighted_edge & e) { return T(e.weight); }

如果传递一个派生类会发生什么？有没有一个C ++机制，从这两个中选择更接近的基类？

what would happen if one passed a derived class? Is there a C++ mechanism that would select the 'closer' base class out of these two?

推荐答案

;我想出了我的问题的最佳解决方案。它是写两个函数，

Thanks for the response, sehe; I figured out the optimal solution for my problem. It is to write two functions,

template <class T>
inline T get_weight(edge const & e)
{ return T(1); }

template <class T>
inline T get_weight(weighted_edge const & e)
{ return T(e.weight); }

这样，当我写一个最短路径算法时，它可以要求这两个类或任何派生类，这对我很重要，因为我可能想在以后添加属性到基边类（如颜色等）。因此，当我写

This way, when I write a shortest-path algorithm it can ask for the weight of either of these two classes or any derived ones, which is important to me because I might want to add properties to the base edge classes later on (like colors, etc.). Hence, when I write

class my_edge : public edge { ... };

my_edge e;

并使用 get_weight（e）获得未加权边缘的行为。对边缘类型的模板化在这里不会有帮助，因为它不能使用从 edge 下降的所有类上的规定的行为，并且将其与 weighted_edge 。

and use get_weight(e) I will get the behavior for the unweighted edge. Templating on the edge type would not help here, because it would not be able to use the prescribed behavior on all classes descending from edge, and distinguishing that from the behavior for weighted_edge.

这篇关于C ++和通用图距离算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！