c++ - 如何遍历图形并沿途提取边缘权重？

Question

假设我有以下无向图

A("")--2.31--B("你好")--1.036--C("")

其中 A 和 C 是空字符串，实数是权重。现在我想从 B 到 A。我知道在 boost 中，这可以用

auto vp = boost::vertices(g);
for(auto vit = vp.first; vit != vp.second; ++vit)
{
  std::cout << *vit <<  " " << std::endl;
}

当我到达顶点 A 时，我希望能够根据关于从 B 到 A 的边的权重的一些数学来随机化来自 B 的字符串。所以我希望能够执行类似 的操作g[A].name = newString(从B到A的权重);.

问题是我真的不知道该怎么做。我有边缘权重，它们是从我正在阅读的文件中正确导入的。如果我通过这种方式迭代，我知道如何获得权重:

auto es = boost::edges(g);
for(auto eit = es.first; eit != es.second; ++eit)
{
  std::cout << get(weight,*eit) << std::endl;
}

问题是这将遍历图的节点，不一定关心任何边。

boost 中有什么东西可以满足我的要求吗？我试过看 this implementation来自 Stack Overflow，我了解如何从特定顶点开始。但是，我不确定是否有办法调整此算法以使用我的边缘权重来实现我想要的，老实说 the documentation for DFS很难理解。我相信 DFS 是我想要的，但我不确定如何在不分解和编写我自己的 DFS 的情况下轻松实现它，我真的不想这样做。

Answer 1

Now I want to get from B to A. I know in boost, that can be done with [...]

不，代码只是枚举顶点，即使是那些没有边且没有特定顺序的顶点。

When I get to vertex A

“到达顶点 A”是什么意思？您是否需要在那里有一条路径，或者您只是要枚举所有顶点并从那里遍历边？

I want to be able to randomize the string from B, based on some math on the weight of the edge from B to A

我将其解读为“我想根据发现的边的权重计算一个字符串，并更新目标顶点的标签字符串。

这至少有点令人困惑，因为它暗示了无向图边上的方向。我假设您确实想要使用一个方向(边缘发现期间的遍历方向)。

And I know how to get the weights if I iterate through this way: [...snip...] The issue with this is that this will iterate through the nodes of the graph and not necessarily caring about any of the edges.

嗯。这完全颠倒过来了。该循环确实迭代边缘，特别是。您是否交换了代码示例？

Is there something in boost that will do what I want?

在您知道自己想要什么之前，这是无法回答的。

I believe DFS is what I want

好吧……让我们开始吧:

示例图

Live On Coliru

#include <boost/graph/adjacency_list.hpp>

让我们定义一个可以存储标签(名称)和权重的图:

struct Vertex { std::string name; };
struct Edge   { double weight; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;

现在，让我们以 Graphviz 格式打印示例图:

Graph make_sample();
void dump(Graph&);

int main() {
    Graph g = make_sample();
    dump(g);
}

这有点像作弊，但从大局着手并隐藏细节通常会有所帮助，所以让我们实现 make_sample:

Graph make_sample() {
    Graph g;
    auto A = add_vertex({""}, g);
    auto B = add_vertex({"Hello"}, g);
    auto C = add_vertex({""}, g);

    add_edge(A, B, {2.31}, g);
    add_edge(B, C, {1.036}, g);
    return g;
}

和转储:

#include <boost/graph/graphviz.hpp>
void dump(Graph& g) {
    boost::dynamic_properties dp;
    dp.property("node_id", get(boost::vertex_index, g));
    dp.property("label", get(&Vertex::name, g));
    dp.property("label", get(&Edge::weight, g));
    write_graphviz_dp(std::cout, g, dp);
}

图表looks like这个:

添加 DFS

搜索很简单:

#include <boost/graph/depth_first_search.hpp>

struct Visitor : boost::default_dfs_visitor {
};

void operate_on(Graph& g) {
    Visitor vis;
    std::vector<boost::default_color_type> color(num_vertices(g));
    boost::depth_first_search(g, vis, color.data());
}

但你想施展魔法:

struct Visitor : boost::default_dfs_visitor {
    void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
        std::cout << "Examining edge " << e << "\n";
    }
};

现在，我们打印:

Examining edge (0,1)
Examining edge (1,0)
Examining edge (1,2)
Examining edge (2,1)

现在，让我们检查相关顶点的属性:

Vertex const& s = g[source(e, g)];
Vertex const& t = g[target(e, g)];

现在你可以做一些逻辑了:

if (s.name.empty() && !t.name.empty()) { // use your own logic here
    std::cout << "Updating label for '" << t.name << "' in edge " << e << "\n";
}

已经打印:

Updating label for 'Hello' in edge (0,1)
Updating label for 'Hello' in edge (2,1)

写入 - 访问

出于安全原因，Graph 由访问者中的const& 接收。为了能够变异，我们需要一个可写的引用。一种方法是在访问者内部存储一个 Graph&:

struct Visitor : boost::default_dfs_visitor {
    Graph& _g;

    Visitor(Graph& g) : _g(g) {}

    void examine_edge(Graph::edge_descriptor e, const Graph&) const {

        // get vertex bundles
        Vertex& s = _g[source(e, _g)];
        Vertex& t = _g[target(e, _g)];

        if (s.name.empty() && !t.name.empty()) { // use your own logic here
            t.name += '(' + std::to_string(_g[e].weight) + ')';
        }
        return;
    }
};

也许更惯用的方法是使用 Property Maps - 具有类似的效果:

struct Visitor : boost::default_dfs_visitor {
    boost::property_map<Graph, std::string Vertex::*>::type _name;
    boost::property_map<Graph, double Edge::*>::const_type _weight;

    Visitor(Graph& g)
        : _name(get(&Vertex::name, g)),
          _weight(get(&Edge::weight, static_cast<Graph const&>(g)))
    { }

    void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
        auto& sname = _name[source(e, g)];
        auto& tname = _name[target(e, g)];

        if (sname.empty() && !tname.empty()) { // use your own logic here
            tname += '(' + std::to_string(_weight[e]) + ')';
        }
        return;
    }
};

Caveat: write access during algorithm is dangerous. Be careful not to violate the pre-conditions/invariants of the algorithm

完整演示

Live On Coliru

#include <boost/graph/adjacency_list.hpp>

struct Vertex { std::string name; };
struct Edge   { double weight; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;

Graph make_sample();
void dump(Graph&);
void operate_on(Graph&);

int main() {
    Graph g = make_sample();
    operate_on(g);
    dump(g);
}

Graph make_sample() {
    Graph g;
    auto A = add_vertex({""}, g);
    auto B = add_vertex({"Hello"}, g);
    auto C = add_vertex({""}, g);

    add_edge(A, B, {2.31}, g);
    add_edge(B, C, {1.036}, g);
    return g;
}

#include <boost/graph/graphviz.hpp>
void dump(Graph& g) {
    boost::dynamic_properties dp;
    dp.property("node_id", get(boost::vertex_index, g));
    dp.property("label", get(&Vertex::name, g));
    dp.property("label", get(&Edge::weight, g));
    write_graphviz_dp(std::cout, g, dp);
}

#include <boost/graph/depth_first_search.hpp>

struct Visitor : boost::default_dfs_visitor {
    boost::property_map<Graph, std::string Vertex::*>::type _name;
    boost::property_map<Graph, double Edge::*>::const_type _weight;

    Visitor(Graph& g)
        : _name(get(&Vertex::name, g)),
          _weight(get(&Edge::weight, static_cast<Graph const&>(g)))
    { }

    void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
        auto& sname = _name[source(e, g)];
        auto& tname = _name[target(e, g)];

        if (sname.empty() && !tname.empty()) { // use your own logic here
            tname += '(' + std::to_string(_weight[e]) + ')';
        }
    }
};

void operate_on(Graph& g) {
    Visitor vis { g };
    std::vector<boost::default_color_type> color(num_vertices(g));
    boost::depth_first_search(g, vis, color.data());
}

打印:

graph G {
0 [label=""];
1 [label="Hello(2.310000)(1.036000)"];
2 [label=""];
0--1  [label=2.31];
1--2  [label=1.036];
}

哪个looks like :