Всем доброго дня!

Есть граф, состоящий, как известно, из узлов и соединяющих их ребёр. И есть несколько алгоритмов его обхода, которые надо реализовать. Количество алгоритмов может и будет увеличиваться и они совсем разные. Выходные данные алгоритмов тоже отличаются. В качестве абстрактного примера можно рассмотреть построение текста по блок-схеме, а в качестве живого примера можно посмотреть в SQL Server Enterprise Manager на дизайнер запросов, там для генерации SQL запроса из диаграммы тоже наверное применяется хитрый алгоритм обхода.

Хотелось бы сделать нечто, упрощающее разработку и отладку этих алгоритмов, и уменьшающее число потенциальных ошибок. Мне для этих целей приглянулся паттерн "визитёр". Как я думаю, любой алгоритм обхода состоит из последовательности действий "старт", "переход", "возврат" и "стоп". Вот на этом я и застрял. Хочется сделать что-то такое, чтобы класс "алгоритм обхода" реализовывал некий одинаковый интерфейс и предоставлял некую f(last_action, link, node), возвращающую следующее действие из 4х приведённых. Но пока не очень-то получается.

Собственно поэтому и пишу — я не очень силён в теории, возможно в мои выкладки где-то закралась ошибка, или я чего-то недопонимаю, может быть сообщество поможет мне преодолеть этот затык или поправит меня в чёмто?

Здравствуйте, hell citizen, Вы писали:

HC>Всем доброго дня!

HC>Собственно поэтому и пишу — я не очень силён в теории, возможно в мои выкладки где-то закралась ошибка, или я чего-то недопонимаю, может быть сообщество поможет мне преодолеть этот затык или поправит меня в чёмто?

А зачем такая детализация для обходов ? Большинство типов обхода графа укладываются либо в обход в глубину, либо в ширину.

Вообще, максимальная общность достигается на простейшем интерфейсе:

class IVisitor
{
public:
    void Traverse(class Graph& graph) = 0;
};

Здравствуйте, _Obelisk_, Вы писали:

_O_>Здравствуйте, hell citizen, Вы писали:

HC>>Всем доброго дня!

HC>>Собственно поэтому и пишу — я не очень силён в теории, возможно в мои выкладки где-то закралась ошибка, или я чего-то недопонимаю, может быть сообщество поможет мне преодолеть этот затык или поправит меня в чёмто?

_O_>А зачем такая детализация для обходов ?
Я не знаю, какая действительно понадобится, вот в чем дело.

_O_>Вообще, максимальная общность достигается на простейшем интерфейсе:
Я вообще имел в виду нечто такое:

class Graph
{
    ...
public:
    void Traverse(IVisiter *visiter)
    {
       ...
          visiter.VisitNode(&node, &link)
       ...
    }
};

За наводку на глубину и ширину спасибо.

Здравствуйте, hell citizen, Вы писали:

_O_>>А зачем такая детализация для обходов ?
HC>Я не знаю, какая действительно понадобится, вот в чем дело.

Может проще сделать так ?

class ILink;

// интерфейс для ноды
class INode
{
public:
    // возвращает все ребра исходящие из ноды
    virtual void GetOutgoingEdges(std::vector<ILink*>& result) = 0;
    // возвращает все ребра входящие в ноду
    virtual void GetIncomingEdges(std::vector<ILink*>& result) = 0;
};

// интерфейс для ребра
class ILink
{
public:    
    virtual INode* GetSource() = 0;
    virtual INode* GetTarget() = 0;
};

В таком случае можно будет реализовать любой алгоритм обхода и нет необходимости встравить поддержку алгоритмов обхода в иерархию классов графа.

Здравствуйте, _Obelisk_, Вы писали:

_O_>Может проще сделать так ?

Так и сделано, за исключением входящих рёбер.

_O_>В таком случае можно будет реализовать любой алгоритм обхода и нет необходимости встравить поддержку алгоритмов обхода в иерархию классов графа.

Дело в том, что алгоритмы обхода не будут жить сами по себе, а будут на основании узлов и их порядка выдавать данные. Хотелось алгоритм обхода отделить от процедуры обработки узлов, т.к. один и тот же алгоритм может быть использован в нескольких задачах.

Здравствуйте, hell citizen, Вы писали:
HC>Дело в том, что алгоритмы обхода не будут жить сами по себе, а будут на основании узлов и их порядка выдавать данные. Хотелось алгоритм обхода отделить от процедуры обработки узлов, т.к. один и тот же алгоритм может быть использован в нескольких задачах.
Алгоритм обхода — преобразование графа к итератору.
Применение процедуры обработки делается так:

public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
{
  foreach(T item in source) action(item);
}

Здесь source инкапсулирует логику обхода, action — процедуру обработки узлов. Всё.
Получать source можно как угодно — граф сам может реализовывать IEnumerable<NodeType>, может публиковать несколько методов, а можно делать через внешний метод обхода, опирающийся на общий интерфейс ноды.

Здравствуйте, Sinclair, Вы писали:

S>Алгоритм обхода — преобразование графа к итератору.
Простого итератора помоему не всегда достаточно. Выше я приводил как пример использования генерацию кода из блок-схемы. Например, пришёл к нам в action() из твоего примера узел "условие". Как решить — писать в вывод "if (условие) {" или "else {"? Надо где-то знать, что это возврат.
Но идея ясна, спасибо, буду пробовать расширить...