首页 文章

在Boost.Graph中为图形添加边

提问于
浏览 次
1

我正在尝试使用Boost.Graph库来运行Goldberg的Max-Flow算法 . Boost.Graph称之为push_relabel_max_flow .

但是，我很难理解库及其类型系统 . 我在上面链接的文档给出了一个示例代码 . 但在该示例中，图表是从文件中读取的 . 我想在运行时生成图形 . 这是我到目前为止的代码（大多数是从示例中复制的）：

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 
        boost::property<boost::vertex_name_t, std::string>, 
        boost::property<boost::edge_capacity_t, long, 
            boost::property<boost::edge_residual_capacity_t, long, 
                boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> DirectedGraph;

DirectedGraph g;
Traits::vertex_descriptor s, t;


s = boost::add_vertex(g);
t = boost::add_vertex(g);
boost::add_vertex(g);
boost::add_vertex(g);

在我向图表添加4个顶点后，我应该"connect"，即，使边缘具有容量，剩余容量和反向值 . 这个任务的功能是 boost::add_edge() ，但我不知道如何传递我的论点 . 示例代码没有显示它，因为正如我所说，数据是从文件中读取然后直接解析为图形 . 也许在Boost.Graph库中有经验的人可以告诉我如何 .

c++ boost boost-graph

1 回答

  • 3

    您可以在顶点 s 和 t 之间添加边，如下所示：

    boost::add_edge(s, t, {33, 44}, g);

    这里将 edge_capacity 设置为33，将 edge_residual_capacity 设置为44 .

    要实际访问边缘属性，据我所知你必须做这样的事情：

    std::cout << boost::get(boost::edge_capacity, g, boost::edge(s,t,g).first) << '\n';

    这很烦人 . 如果您使用捆绑属性，则更容易，如下所示：

    typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;

struct VertexProps {
    std::string name;
};

struct EdgeProps {
    long capacity;
    long residual_capacity;
    Traits::edge_descriptor reverse;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                              VertexProps, EdgeProps > DirectedGraph;

    然后，您可以以相同的方式添加顶点和边，但更容易访问边属性，例如

    auto e = boost::edge(s,t,g).first; // get the edge descriptor for an edge from s to t, if any
std::cout << g[e].capacity << '\n';

    要在您添加的匿名第三和第四个顶点之间添加边，您可以逃脱

    boost::add_edge(2, 3, {17, 26}, g);

    因为底层存储是 vector ，所以 vertex_descriptor 只是矢量索引（又名 size_t ，这里也叫 unsigned long ） . 但更严格地说，你应该这样做

    boost:add_edge(boost::vertex(2, g), boost::vertex(3, g), {17, 26}, g);

    为了获得第3和第4个顶点的 vertex_descriptor .

    回复于

相关问题