如何在boost图上迭代，同时找到邻居的邻居？

Question

下图显示了双向图.我用boost-graph表示了下面的图表。

​

我从v1 -> v2和v1 -> v3迭代过，但不能从v3 -> v4访问。怎么做？

这是我的代码：

(顶点= V1)和(图= boost图)

 //Finding out edges of vertex
    boost::graph_traits<BGType>::out_edge_iterator ei, ei_end;
    boost::tie(ei, ei_end) = out_edges( vertex, graph ); 
    for( boost::tie(ei, ei_end) = out_edges(vertex, graph); ei != ei_end; ++ei)
    {
        auto target = boost::target ( *ei, graph );
        graph[target]._isVisible = false;
    }

    //Finding in edges of vertex
    boost::graph_traits<BGType>::in_edge_iterator ein, ein_end;
    boost::tie(ein, ein_end) = in_edges( vertex, graph ); 
    for( boost::tie(ein, ein_end) = in_edges(vertex, graph); ein != ein_end; ++ein)
    {
        auto source = boost::source ( *ein, graph ); 
        graph[source]._isVisible = false;
    }

Answer 1

如果你把你的术语弄清楚了，就会有帮助。L1，L2，L3是边而不是顶点。

所以，你想要隐藏所有的边，另外，所有的顶点都有0度。

相反，您可以为边缘设置一个可见性标志：

struct EdgeProps {
    bool _isVisible = true;
};

using BGType = boost::adjacency_list< //
    boost::vecS,                      //
    boost::vecS,                      //
    boost::bidirectionalS,            //
    VertexProps,                      //
    EdgeProps>;

现在我要做的是：

void hide_connections(Name name, BGType& graph) {
    auto it = graph.named_vertices.find(name);
    assert(it != graph.named_vertices.end());
    using boost::make_iterator_range;

    for (auto e : make_iterator_range(out_edges(*it, graph)))
        graph[e]._isVisible = false;

    for (auto e : make_iterator_range(in_edges(*it, graph)))
        graph[e]._isVisible = false;
}

现在，顶点的可见性是一个结果-一个派生的属性。你可以实时计算：

auto visible = [&graph](V v) {
    for (auto e : make_iterator_range(out_edges(v, graph)))
        if (graph[e]._isVisible)
            return true;
    for (auto e : make_iterator_range(in_edges(v, graph)))
        if (graph[e]._isVisible)
            return true;
    return false;
};

实际上，这满足了您的需求：在编译器资源管理器上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>

using Name = std::string;

struct VertexProps {
    VertexProps(Name n = "unnamed") : name(std::move(n)) {}
    Name name;
};

struct EdgeProps {
    bool _isVisible = true;
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    using type = boost::graph::vertex_from_name<VertexProps>;
};

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = Name;
        Name const& operator()(VertexProps const& vp) const { return vp.name; } 
        Name&       operator()(VertexProps& vp) const       { return vp.name; } 
    };
};

using BGType = boost::adjacency_list< //
    boost::vecS,                      //
    boost::vecS,                      //
    boost::bidirectionalS,            //
    VertexProps,                      //
    EdgeProps>;

using V = BGType::vertex_descriptor;
using E = BGType::edge_descriptor;

void hide(Name name, BGType& graph) {
    auto it = graph.named_vertices.find(name);
    assert(it != graph.named_vertices.end());

    for (auto e : make_iterator_range(out_edges(*it, graph)))
        graph[e]._isVisible = false;

    for (auto e : make_iterator_range(in_edges(*it, graph)))
        graph[e]._isVisible = false;
}

int main() {
    BGType graph;

    for (auto [from, to] : {
            std::pair{"V1", "V2"},
            {"V1", "V3"},
            {"V3", "V4"},
        })
    {
        add_edge(from, to, graph);
        add_edge(to, from, graph);
    }

    auto visible = [&graph](V v) { return 0 != degree(v, graph); };

    auto names = get(&VertexProps::name, graph);
    auto print = [&](std::ostream& os = std::cout) {
        for (auto v : boost::make_iterator_range(vertices(graph))) {
            if (!visible(v))
                continue;
            os << names[v] << " -->";
            for (auto e : make_iterator_range(out_edges(v, graph))) {
                if (graph[e]._isVisible)
                    os << " " << names[target(e, graph)];
            }
            os << "\n";
        }
    };

    print();

    hide("V1", graph);

    print(std::cout << "\nConnections of V1 hidden:\n");
}

打印

V2 --> V1
V1 --> V2 V3
V3 --> V1 V4
V4 --> V3

Connections of V1 hidden:
V3 --> V4
V4 --> V3

他山之石

这既笨拙又低效：

auto visible = [&graph](V v) {
    for (auto e : make_iterator_range(out_edges(v, graph)))
        if (graph[e]._isVisible)
            return true;
    for (auto e : make_iterator_range(in_edges(v, graph)))
        if (graph[e]._isVisible)
            return true;
    return false;
};

你真正想说的是：

auto visible = [&graph](V v) { return 0 != degree(v, graph); };

然而，它不会工作，因为你实际上没有删除任何东西，所以BGL会认为边缘仍然存在。

您可以通过使用filtered_graph_adaptor来修复模型，您可以将过滤器存储在图形模型之外。

滤波图

因此，这使透视图回到原来的位置:隐藏顶点。让我们从简单的开始：

std::set<V> vhidden;
std::set<E> ehidden;

这是包含所有隐藏顶点描述符的集合。

现在，我们可以设置过滤器谓词和经过调整的图表：

std::function epred = [&](E e) { return not ehidden.contains(e); };
std::function vpred = [&](V v) { return not vhidden.contains(v); };

boost::filtered_graph f(graph, epred, vpred);

添加一些帮助来隐藏边缘/顶点。

auto ehide = [&](E e) {
    if (auto u = target(e, graph); 0 == degree(u, f))
        vhidden.insert(u);
    ehidden.insert(e);
};

注意，我们很懒，在过滤后的图形(!)上使用degree(v, f)。这样我们就不必手动计算已经过滤过的边缘数。

auto vhide = [&](Name const& name) {
    auto it = graph.named_vertices.find(name);
    assert(it != graph.named_vertices.end());
    V v = *it;
    vhidden.insert(v);

    for (auto e: make_iterator_range(out_edges(v, graph)))
        ehide(e);
    for (auto e: make_iterator_range(in_edges(v, graph)))
        ehide(e);
};

隐藏顶点会无条件地穿越一个级别到邻居。作为停止条件(对你的评论的响应)，这已经足够好了，因为除非向同一个目标节点隐藏更多的边缘，否则程度不能改变。

使用筛选的视图：

std::cout << "Filtered edges(" << ehidden.size() << "), vertices(" << vhidden.size() << ")\n";
print_graph(f, names, std::cout << "Filtered view: \n");

vhide("V1");

std::cout << "Filtered edges(" << ehidden.size() << "), vertices(" << vhidden.size() << ")\n";
print_graph(f, names, std::cout << "Connections of V1 hidden:\n");

看吧，在编译器资源管理器上直播

Filtered edges(0), vertices(0)
Filtered view: 
V2 --> V1 
V1 --> V2 V3 
V3 --> V1 V4 
V4 --> V3 
Filtered edges(4), vertices(2)
Connections of V1 hidden:
V3 --> V4 
V4 --> V3 

完整列表(过滤图)

为子孙后代：在编译器资源管理器上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>

using Name = std::string;

struct VertexProps {
    VertexProps(Name n = "unnamed") : name(std::move(n)) {}
    Name name;
};

struct EdgeProps {
    bool _isVisible = true;
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    using type = boost::graph::vertex_from_name<VertexProps>;
};

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = Name;
        Name const& operator()(VertexProps const& vp) const { return vp.name; } 
        Name&       operator()(VertexProps& vp) const       { return vp.name; } 
    };
};

using BGType = boost::adjacency_list< //
    boost::vecS,                      //
    boost::vecS,                      //
    boost::bidirectionalS,            //
    VertexProps,                      //
    EdgeProps>;

using V = BGType::vertex_descriptor;
using E = BGType::edge_descriptor;

int main() {
    BGType graph;

    for (auto [from, to] : {
            std::pair{"V1", "V2"},
            {"V1", "V3"},
            {"V3", "V4"},
        })
    {
        add_edge(from, to, graph);
        add_edge(to, from, graph);
    }

    auto names = get(&VertexProps::name, graph);

    print_graph(graph, names, std::cout << "Unfiltered graph:\n");

    std::set<V> vhidden;
    std::set<E> ehidden;

    std::function epred = [&](E e) { return not ehidden.contains(e); };
    std::function vpred = [&](V v) { return not vhidden.contains(v); };

    boost::filtered_graph f(graph, epred, vpred);

    auto ehide = [&](E e) {
        if (auto u = target(e, graph); 0 == degree(u, f))
            vhidden.insert(u);
        ehidden.insert(e);
    };
    auto vhide = [&](Name const& name) {
        auto it = graph.named_vertices.find(name);
        assert(it != graph.named_vertices.end());
        V v = *it;
        vhidden.insert(v);

        for (auto e: make_iterator_range(out_edges(v, graph)))
            ehide(e);
        for (auto e: make_iterator_range(in_edges(v, graph)))
            ehide(e);
    };

    std::cout << "Filtered edges(" << ehidden.size() << "), vertices(" << vhidden.size() << ")\n";
    print_graph(f, names, std::cout << "Filtered view: \n");

    vhide("V1");

    std::cout << "Filtered edges(" << ehidden.size() << "), vertices(" << vhidden.size() << ")\n";
    print_graph(f, names, std::cout << "Connections of V1 hidden:\n");
}