c++ - una - Iteración sobre los bordes de un gráfico usando el rango para

varias graficas en r

Question

Tengo una representación de un gráfico como std::vector<std::unordered_set<unsigned>> neighbors , es decir, los vértices son enteros, y para cada vértice mantenemos un conjunto de sus vecinos. Por lo tanto, para caminar por todos los bordes, haría algo así como

for (unsigned u = 0; u < neighbors.size(); ++u)
    for (unsigned v : neighbors[u])
        if (u <= v)
            std::cout << u << '' '' << v << std::endl;

Ahora, me gustaría poder obtener el mismo efecto de

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

donde g es de una clase que encapsula el vector neighbors .

Sin embargo, todo lo que probé parece extremadamente complicado, la mejor versión que puedo encontrar tiene 50 líneas, y es difícil ver que sea correcta. ¿Hay una manera simple de hacer esto?

Aquí está mi versión fea:

#include <iostream>
#include <unordered_set>
#include <vector>
typedef unsigned Vertex;
class Graph {
public:
    typedef std::unordered_set<Vertex> Neighbors;
    std::size_t numVertices() const { return neighbors_.size(); }
    Graph(std::size_t n = 0) : neighbors_(n) { }
    void addEdge(Vertex u, Vertex v) {
        neighbors_[u].insert(v);
        neighbors_[v].insert(u);
    }
    class EdgeIter {
        friend Graph;
    public:
        bool operator!=(const EdgeIter& other) { return u_ != other.u_; }
        void operator++() {
            do {
                ++it_;
                while (it_ == it_end_) {
                    u_++;
                    if (u_ >= neighbors_.size())
                        break;
                    it_     = neighbors_[u_].cbegin();
                    it_end_ = neighbors_[u_].cend();
                }
            } while (u_ < neighbors_.size() && *it_ < u_);
        }
        std::pair<Vertex, Vertex> operator*() { return {u_, *it_}; }
    private:
        EdgeIter(const std::vector<std::unordered_set<Vertex> >& neighbors, size_t u)
            : u_(u), neighbors_(neighbors) {
            if (u < neighbors_.size()) {
                it_     = neighbors_[u_].cbegin();
                it_end_ = neighbors_[u_].cend();
                while (it_ == it_end_) {
                    u_++;
                    if (u_ >= neighbors_.size())
                        break;
                    it_     = neighbors_[u_].cbegin();
                    it_end_ = neighbors_[u_].cend();
                }
            }
        }
        Vertex u_;
        const std::vector<std::unordered_set<Vertex> >& neighbors_;
        std::unordered_set<Vertex>::const_iterator it_, it_end_;
    };
    EdgeIter edgesBegin() const { return EdgeIter(neighbors_, 0); }
    EdgeIter edgesEnd()   const { return EdgeIter(neighbors_, neighbors_.size()); }
    class Edges {
    public:
        Edges(const Graph& g) : g_(g) { }
        EdgeIter begin() const { return g_.edgesBegin(); }
        EdgeIter end  () const { return g_.edgesEnd();   }
    private:
        const Graph& g_;
    };
    Edges edges() { return Edges(*this); }
    std::vector<Neighbors> neighbors_;
};
int main() {
    Graph g(5);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(1, 3);    
    for (unsigned u = 0; u < g.numVertices(); ++u)
        for (unsigned v : g.neighbors_[u])
            if (u <= v)
                std::cout << u << '' '' << v << std::endl;
    for (auto e: g.edges())
        std::cout << e.first << '' '' << e.second << std::endl;
}

Answer 1

¡Una oportunidad para un enchufe desvergonzado! Tengo un proyecto linq-cpp para llevar la funcionalidad de .NET LINQ a C ++ 11, y este es un ejemplo perfecto de dónde realmente brilla.

Utilizándolo, podría escribir una función como la siguiente:

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

Y luego úsalo así:

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

O tal vez así:

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

Answer 2

Creo que su representación interna de un gráfico, std::vector<std::unordered_set<Vertex>> , es lo que hace que el código sea difícil de escribir / leer. Tal vez otra representación (por ejemplo, std::set<std::pair<Vertex, Vertex>> ) haría que tu código sea más simple. Sin embargo, es difícil de decir ya que no sabemos exactamente cuáles son los requisitos de Graph .

De todos modos, como señala Zeta, hay un error en EdgeIter::operator !=() . Por ejemplo, el código a continuación:

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

salidas false Por lo tanto, el código considera que i1 e i2 no son diferentes cuando claramente lo son.

Actualizar:

Probablemente sea obvio, pero aquí hay una versión más simple que usa una representación diferente para el gráfico. Sin embargo, enfatizo que esto puede no ser satisfactorio dependiendo de sus requisitos para Graph (que no conozco):

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

Answer 3

Recomiendo usar la biblioteca Boost.Graph para tales cálculos. La razón principal es que los gráficos son estructuras de datos complicadas en las que puede ejecutar algoritmos aún más complicados . Incluso si su propia estructura de datos hecha a mano funciona correctamente, es probable que no se ejecute de manera eficiente (en términos de complejidad de espacio / tiempo) y puede que no admita los algoritmos que sus aplicaciones necesitan.

Como una indicación de cuán accesible es esta biblioteca: no tenía experiencia previa con Boost.Graph, pero me tomó aproximadamente 30 minutos crear las siguientes 30 líneas de código que reproducen completamente su ejemplo.

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

Salida en LiveWorksSpace

Claro, porque boost::edges devuelve un std::pair , no se puede usar el rango para los bordes, pero eso es solo azúcar sintáctico que puedes tratar de reparar definiendo tus propias funciones de inicio / finalización. Lo importante es que puede iterar sobre los bordes directamente.

Tenga en cuenta que la estructura de datos boost_adjacency_list proporciona operaciones de flanco y vértices con una complejidad de tiempo y espacio bien definida . El código anterior simplemente reproduce su ejemplo sin saber qué tipo de operaciones realmente desea. Cambiar los contenedores subyacentes le permite hacer concesiones de manera apropiada a su aplicación.