使用基于范围的for对图形的边缘进行迭代 [英] Iterating over edges of a graph using range-based for
问题描述
我有一个图表示为 std :: vector< std :: unordered_set< unsigned>> neighbors ，也就是说，顶点是整数，对于每个顶点，我们保留一组其邻居。因此，为了走所有边，我会做
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;
现在，我想从
for (auto e: g.edges())
std::cout << e.first << ' ' << e.second << std::endl;
其中 g 邻居向量。
然而，我试过的一切似乎都很复杂，最好的版本我能想出有50线，很难看到它是正确的。有这么简单的方法吗？
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?
这是我的丑陋版本：
#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;
}
推荐答案
a href =http://www.boost.org/libs/graph/> Boost.Graph 库进行此类计算。主要原因是图表是复杂的数据结构，您可以在其上运行更多复杂的算法。即使您自己的手工制作的数据结构工作正常，也可能无法高效运行（在空间/时间复杂性方面），并且可能不支持您的应用程序需要的算法。
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.
作为一个指示如何访问这个库是：我以前没有使用过Boost.Graph的经验，但花了大约30分钟得出以下30行代码，完全再现你的例子。
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;
}
}
授予，因为 boost :: edges 返回 std :: pair ，您不能在边上使用基于范围的，但这只是语法糖，您可以通过定义自己的begin / end函数尝试修复。
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.
请注意， boost_adjacency_list 数据结构为您提供边和 明确定义的时间和空间复杂度 的顶点操作。上面的代码只是复制你的例子，而不知道你真正想要什么样的操作。更改底层容器允许您根据应用程序做出适当的权衡。
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.
这篇关于使用基于范围的for对图形的边缘进行迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
