Iterating over edges of a graph using range-based

问题:

I have a representation of a graph as a std::vector<std::unordered_set<unsigned>> neighbors, that is, vertices are integers, and for each vertex we keep a set of its neighbors. Thus, to walk all edges, I would do something like

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

Now, I would like to be able to get the same effect from

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

where g is from a class encapsulating the neighbors vector.

However, everything I tried seems extremely complicated, the best version I can come up with has 50 lines, and it's hard to see that it is correct. Is there a simple way to do this?

Here's my ugly version:

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

回答1:

I strongly recommend using the Boost.Graph library for such computations. The main reason is that graphs are complicated data structures on which you can run even more complicated algorithms. Even if your own hand-made data structure works correctly, it is likely not to run efficiently (in terms of space/time complexity) and may not support the algorithms that your applications needs.

As an indication on how accessible this library is: I had no prior experience with Boost.Graph, but it took about 30 minutes to come up with the following 30 lines of code that completely reproduces your example.

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

Output on LiveWorksSpace

Granted, because boost::edges returns a std::pair, you can't use range-based for on the edges, but that's only syntactic sugar which you can try to repair by defining your own begin/end functions. What's important is that you can iterate over edges directly.

Note that the boost_adjacency_list data structure provides you with edge and vertex operations of well-defined time and space complexity. The code above merely reproduces your example without knowing what kind of operations you really want. Changing the underlying containers allows you to make tradeoffs appropriately to your application.

回答2:

An opportunity for a shameless plug! I have a project linq-cpp for bringing .NET LINQ functionality to C++11, and this is a perfect example for where it really shines.

Using it, you could write a function like the following:

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

And then use it like this:

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

Or maybe like this:

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

回答3:

I believe that your internal representation of a graph, std::vector<std::unordered_set<Vertex>>, is what makes the code hard to write/read. Maybe another representation (e.g. std::set<std::pair<Vertex, Vertex>>) would make your code simpler. However, it's hard to tell since we don't know exactly what are the requirements of Graph.

Anyway, as pointed out by Zeta there's a bug in EdgeIter::operator !=(). For instance, the code below:

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

outputs false. Hence, the code considers that i1 and i2 are not different when they clearly are.

Update:

It's probably obvious but here is a simpler version which uses a different representation for the graph. However, I emphasize that this may not be satisfactory depending on your requirements for Graph (which I don know):

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