12

我将图表示为 a std::vector<std::unordered_set<unsigned>> neighbors，也就是说，顶点是整数，并且对于每个顶点，我们保留一组它的邻居。因此，要走所有边缘，我会做类似的事情

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;

whereg来自封装neighbors向量的类。

然而，我尝试的一切似乎都非常复杂，我能想到的最好的版本有 50 行，很难看出它是正确的。有没有一种简单的方法可以做到这一点？

这是我的丑陋版本：

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

3 回答 3

14

我强烈建议使用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返回 a std::pair，您不能在边缘上使用基于范围的 for ，但这只是您可以通过定义自己的开始/结束函数来尝试修复的语法糖。重要的是您可以直接迭代边缘。

请注意，该数据结构为您提供了定义明确的时间和空间复杂度boost_adjacency_list的边和顶点操作。上面的代码只是在不知道您真正想要什么样的操作的情况下重现您的示例。更改底层容器允许您对您的应用程序进行适当的权衡。

于 2013-04-05T08:06:13.190 回答
1

一次无耻插队的机会！我有一个项目linq-cpp用于将 .NET LINQ 功能引入 C++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();
于 2013-04-04T22:57:03.643 回答
1

我相信您对图表的内部表示std::vector<std::unordered_set<Vertex>>，是使代码难以编写/阅读的原因。也许另一种表示形式（例如std::set<std::pair<Vertex, Vertex>>）会使您的代码更简单。但是，很难说，因为我们不确切知道Graph.

无论如何，正如Zeta所指出的，在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当它们明显不同时并没有什么不同。

更新：

这可能很明显，但这是一个更简单的版本，它使用不同的图形表示。但是，我强调这可能并不令人满意，具体取决于您的要求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;
}
于 2013-04-04T22:44:39.773 回答