C ++ и общий алгоритм расстояния до графа

Question

Моя проблема заключается в следующем.Я изучаю C ++, написав библиотеку графов, и хочу использовать как можно больше общих методов программирования;следовательно, ответ на мой вопрос через «use BOOST» мне не поможет;на самом деле, я пытался просмотреть код BOOST, чтобы найти ответ на мой вопрос, но это был унизительный опыт, поскольку я даже не могу понять, где определены определенные функции;слишком высокий уровень C ++, чтобы учиться на нем на моем уровне.

Тем не менее, моя библиотека настроена следующим образом:

class edge { ... };

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

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

, и я создаю более сложные графы с помощьюиспользуя классы, полученные из ребра или узла, таким образом, класс взвешенного ребра был бы просто

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

   ...
};

Теперь проблема заключается в том, что я хочу реализовать алгоритм для этой структуры, который вычисляет кратчайшее расстояние между двумя вершинами.Я мог бы легко написать два из них, один для взвешенных ребер и один для невзвешенного, но изменение крошечное: один получит доступ к полю члена weighted_edge (или производным классам), а другой примет унитарный вес.

Есть ли способ сделать это, чтобы я мог иметь только один кусок кода для обоих случаев?

Одним из решений является использование функции-члена edge::get_weight(), которая бы возвращала вес (или '1'в невзвешенном случае), но это заставило бы меня использовать определенный тип веса для класса ребра, который является невзвешенным, поэтому пахнет смешно.Я имею в виду, что шаблон должен быть

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

, что не совсем удобно для пользователя или, по крайней мере, сбивает с толку, так как вы не ожидаете, что должны быть какие-либо веса.

BGL использует функцию get() для получения веса;Я мог бы написать функцию, которая возвращает 1 или weight в зависимости от edge_T, но меня беспокоит, что произойдет, если получить из edge или weighted_edge?Если кто-то напишет:

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 ++, который бы выбирал из этих двух «более близкий» базовый класс?

Answer 1

Спасибо за ответ, сехе; Я выяснил оптимальное решение для моей проблемы. Это написать две функции,

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); }

Таким образом, когда я пишу алгоритм кратчайшего пути, он может запросить вес любого из этих двух классов или любых производных , что важно для меня, потому что я могу добавить свойства в классы базовых ребер позже (как цвета и т. д.). Следовательно, когда я пишу

class my_edge : public edge { ... };

my_edge e;

и используйте get_weight(e) Я получу поведение для невзвешенного края. Шаблонирование типа ребра здесь не поможет, потому что он не сможет использовать предписанное поведение для всех классов, начиная с edge, и отличать его от поведения для weighted_edge.

.

Answer 2

_{Предварительно : Я полагаю, вы подумали о том, чтобы сделать getWeight() виртуальным методом в базовом классе edge (и сделать реализацию по умолчанию, возвращающую 1).Я знаю об ограничениях в гибкости этого подхода, просто хотел проверить.}

---

Поскольку я не понимал цели ваших шаблонов типов возвращаемых данных, я предполагал, что вы хотите определить тип возвращаемых данных, который вы можете сделать, используя мое решение,

Обычный способ заставить get_weight выбрать правильную реализацию - использовать специализацию шаблона (обратите внимание, что код, который вы показываете, специализируется по типу возвращаемого значения; по определению этот тип никогда не будет выведен компилятором):

namespace detail
{
    template <class Edge> struct get_weight_impl;

    template <> struct get_weight_impl<edge>
    {
        typedef typename result_type int;

        result_type operator()(const edge& e) const
            { return result_type(1); }
    };

    template <> struct get_weight_impl<weighted_edge>
    {
        typedef typename result_type int;

        result_type operator()(const weighted_edge& e) const
            { return result_type(e.weight); }
    };
}

Обновление 1 Вы можете использовать result_of<edge::weight> (boost / TR1) или decltype(edge::weight) (C ++ 0x), чтобы избежать жесткого кодирования значений типа result_type.Это было бы истинной индукцией.

Обновление 2 Чтобы получить перегрузку для weighted_edge const& для 'service' производных типов ребер, а также применить немного волшебства type_trait:

http://ideone.com/AqmsL

struct edge {};
struct weighted_edge : edge          { virtual double get_weight() const { return 3.14; } };
struct derived_edge  : weighted_edge { virtual double get_weight() const { return 42; } };

template <typename E, bool is_weighted>
struct edge_weight_impl;

template <typename E>
struct edge_weight_impl<E, false>
{
    typedef int result_type;
    int operator()(const E& e) const { return 1; }
};

template <typename E>
struct edge_weight_impl<E, true>
{
    // typedef decltype(E().weight()) result_type; // c++0x
    typedef double result_type;

    result_type operator()(const E& e) const 
    { 
        return e.get_weight();
    }
};

template <typename E>
    typename edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>::result_type 
        get_weight(const E& e)
{
    return edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>()(e);
}

int main()
{
    edge e;
    weighted_edge we;
    derived_edge de;

    std::cout << "--- static polymorphism" << std::endl;
    std::cout << "edge:\t"          << get_weight(e) << std::endl;
    std::cout << "weighted_edge:\t" << get_weight(we) << std::endl;
    std::cout << "derived_edge:\t"  << get_weight(de) << std::endl;

    // use some additional enable_if to get rid of this:
    std::cout << "bogus:\t"         << get_weight("bogus") << std::endl;

    std::cout << "\n--- runtime polymorphism" << std::endl;

    edge* ep = &e;
    std::cout << "edge:\t"          << get_weight(*ep) << std::endl;
    weighted_edge* wep = &we;
    std::cout << "weighted_edge:\t" << get_weight(*wep) << std::endl;
    wep = &de;
    std::cout << "bogus:\t"         << get_weight(*wep) << std::endl;
}