Итерация по краям графика с использованием диапазона для

Ответ 1

Я настоятельно рекомендую использовать библиотеку Boost.Graph для таких вычислений. Основная причина заключается в том, что графики представляют собой сложные структуры данных, на которых вы можете запускать еще более сложные алгоритмы. Даже если ваша собственная структура данных вручную работает правильно, она, скорее всего, не будет работать эффективно (с точки зрения сложности пространства/времени) и может не поддерживать алгоритмы, которые необходимы вашим приложениям.

Как указание на доступность этой библиотеки: у меня не было опыта работы с Boost.Graph, но потребовалось около 30 минут, чтобы придумать следующие 30 строк кода, которые полностью воспроизводят ваш пример.

#include <iostream>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>

typedef unsigned V;
typedef std::pair<V, V> E;

// store neighbors in a std::set, vertices in a std::vector
typedef boost::adjacency_list<boost::setS, boost::vecS> Graph;

int main()
{
   // construct the graph
   E e[] = { E(1,2), E(2,3), E(1,3) };
   Graph g(std::begin(e), std::end(e), 5);

   std::cout << "iterate over vertices, then over its neighbors\n";
   auto vs = boost::vertices(g);
   for (auto vit = vs.first; vit != vs.second; ++vit) {
       auto neighbors = boost::adjacent_vertices(*vit, g);
       for (auto nit = neighbors.first; nit != neighbors.second; ++nit)
           std::cout << *vit << ' ' << *nit << std::endl;
   }

   std::cout << "iterate directly over edges\n";
   auto es = boost::edges(g);
   for (auto eit = es.first; eit != es.second; ++eit) {
       std::cout << boost::source(*eit, g) << ' ' << boost::target(*eit, g) << std::endl;
   }
}

Выход на LiveWorksSpace

Конечно, поскольку boost::edges возвращает std::pair, вы не можете использовать диапазон по умолчанию для на краях, но это только синтаксический сахар, который вы можете попробуйте восстановить, определив свои собственные функции begin/end. Важно то, что вы можете напрямую перебирать края.

Обратите внимание, что структура данных boost_adjacency_list предоставляет вам операции с краем и вершиной четко определенная сложность времени и пространства. В приведенном выше коде просто воспроизводится ваш пример, не зная, какие операции вы действительно хотите. Изменение базовых контейнеров позволяет вам соответствующим образом компрометировать ваше приложение.

Ответ 2

Я считаю, что ваше внутреннее представление графика std::vector<std::unordered_set<Vertex>> - это то, что делает код трудным для записи/чтения. Возможно, другое представление (например, std::set<std::pair<Vertex, Vertex>>) сделает ваш код более простым. Однако это трудно сказать, так как мы не знаем точно, каковы требования Graph.

В любом случае, как указано Zeta​​strong > , есть ошибка в EdgeIter::operator !=(). Например, код ниже:

int main() {

    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);

    auto i1 = g.edges().begin();
    auto i2 = i1;
    ++i2;
    std::cout << std::boolalpha;
    std::cout << (i1 != i2) << std::endl;
}

выводит false. Следовательно, код считает, что i1 и i2 не отличаются друг от друга, когда они явно.

Update:

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

#include <set>
#include <stdexcept>
#include <iostream>

typedef unsigned Vertex;

class Graph {

public:

    typedef std::pair<Vertex, Vertex> Edge;
    typedef std::set<Edge> Edges;

    void addEdge(Vertex u, Vertex v) {
      edges_.insert({u, v});
    }

    const Edges& edges() { return edges_; }

private:

    Edges edges_;
};

int main() {

    Graph g;

    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(1, 3);    

    for (auto e: g.edges())
        std::cout << e.first << ' ' << e.second << std::endl;
}

Ответ 3

Возможность для бесстыдного плагина! У меня есть проект linq-cpp для обеспечения функциональности .NET LINQ для С++ 11, и это идеальный пример, где он действительно светит.

Используя его, вы можете написать такую ​​функцию, как:

TEnumerable<std::pair<int, int>> EnumerateEdges(std::vector<std::unordered_set<int>>& neighbors)
{
    return Enumerable::FromRange(neighbors)
        .SelectManyIndexed([](std::unordered_set<int>& bNodes, int aNode)
        {
            return Enumerable::FromRange(bNodes)
                .Select([=](int bNode){ return std::make_pair(aNode, bNode); });
        });
}

И затем используйте его следующим образом:

EnumerateEdges(neighbors).ForEach([](std::pair<int, int> edge)
{
    /* your code */
});

Или может быть так:

auto edges = EnumerateEdges(neighbors).ToVector();