增强带有黑名单边缘的过滤图 [英] Boost filtered graph with blacklisted edges

问题描述

我想在具有黑名单边缘的图形上运行Dijkstra，即我想计算不使用那些链接的最短路径.目前，我首先定义过滤器:

  typedef std :: pair< int，int>边缘;typedef boost :: adjacency_list< boost :: listS，boost :: vecS，boost :: directedS，boost :: no_property，boost :: property< boost :: edge_weight_t，int>>graph_t; 

struct BlackListEdgeConstraint{私人的:std :: set blackList;graph_t * g;

  public:BlackListEdgeConstraint():blackList(std :: set< Edge>())，g(NULL){};BlackListEdgeConstraint(std :: set< Edge>& list，graph_t * g_):blackList(list)，g(g_){}/***这是boost :: filtered_graph(*参见http://www.boost.org/doc/libs/1_64_0/libs/graph/doc/filtered_graph.html)*返回true，边缘包含在过滤的图形中，否则将被排除.*/布尔运算符()(const boost :: graph_traits< graph_t> :: edge_descriptor& e)const{边缘edge(source(e，* g)，target(e，* g));//如果边缘不在黑名单中，则将其包括在内.返回blackList.find(edge)== blackList.end();}}; 

然后在may main(...)函数

中执行此操作

  ...我填满了图形g ...std :: set< Edge>黑名单;blacklist.insert(Edge(0,1));BlackListEdgeConstraint过滤器(blacklist，&g);boost :: filtered_graph< graph_t，BlackListEdgeConstraint>已过滤(g，过滤器);...我在过滤后的图表上运行Dikjstra ... 

现在，我所做的工作很有效，但这很奇怪.确实，我首先在顶点0和1之间创建了一条边.然后，在 operator()(...)内部，我有一个 edge_descriptor 而不是Edge (如果我将Edge作为参数，则编译器会按照

摘要 Edge 类型的成本不存在.任何实际成本都将取决于在 edge_descriptor 上使用 boost :: source()和 boost :: target().

看到边缘容器选择器是 listS ，边缘容器是基于节点的，这意味着边缘描述符是稳定的，并且基本上是对边缘对象的类型擦除引用.调用 boost :: source(e，g)所做的只不过是强制转换描述符和取消引用.根据使用方式的不同，编译器可能甚至可以查看这些间接指令.

如果您不喜欢这种花费，请调整Graph类型:)(您的用例可能可以使用EdgeList概念，或者可以使用基于节点的边缘容器等).

I want to run Dijkstra on a graph with blacklisted edges, i.e., I want to compute shortest paths that do not use those links. For the moment, I first define the filter:

typedef std::pair<int, int> Edge;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, int> > graph_t;

struct BlackListEdgeConstraint { private: std::set blackList; graph_t* g;

public:

    BlackListEdgeConstraint():blackList(std::set<Edge>() ),g(NULL){};

    BlackListEdgeConstraint(std::set<Edge>& list, graph_t* g_) : blackList(list), g(g_)
    {
    }

    /**
     * This is the "predicate function" used by boost::filtered_graph (
     *  see http://www.boost.org/doc/libs/1_64_0/libs/graph/doc/filtered_graph.html )
     *  It it returns true, the edge is included in the filtered graph, otherwise it is excluded.
     */
    bool operator()(const boost::graph_traits<graph_t>::edge_descriptor& e) const
    {
        Edge edge(source(e,*g), target(e,*g) );
        //Include the edge if it's not in the blacklist.
        return blackList.find( edge ) == blackList.end();
    }
};

and then I do this in may main(...) function

... I fill the graph g ...
std::set<Edge> blacklist; blacklist.insert( Edge(0,1)  );
BlackListEdgeConstraint filter(blacklist, &g);
boost::filtered_graph<graph_t, BlackListEdgeConstraint> filtered(g, filter);
... I run Dikjstra on the filtered graph ...

Now, what I did works, but it is weird. Indeed, I first create an edge between vertex 0 and 1. Then, inside the operator() (...), I have an edge_descriptor instead of an Edge (if I put Edge as parameter, the compiler complains as explained here, so I guess boost is performing some conversion somewhere and for a reason I do not know). Then, I retrieve again the vertices 0 and 1 inside operator() (...) and I reconstruct the Edge. You understand that I am taking a long tour to do something that would be easy if only the operator()(..) accepted directly Edge.

Do you think I can do the same operations in a more elegant and efficient way?

解决方案

What you basically ask has little to do with boost graph. You want to be able to lookup a pair of vertex-descriptors, efficiently.

The deciding factor will be the choice of data structure for the blacklist.

As a side note, you do not insert Edge objects into the graph. The graph model you chose is an adjacency-list so it stores lists of adjacent vertices for each vertex.

The pair<int,int> is merely a convenience type that is used for easily initializing the graph. You could do without it entirely.

After thinking about the possible choices I don't think there's a swifter way.

• At certain, large, scales, you might get higher effective performance

  • using a blacklist that is itself represented as an adjacency-list (e.g. std::map<source_vertex, std::list<target_vertex> >) or
  • to use an unordered_set<>.

  Both optimizations are unlikely to yield significant difference unless at large scale.

• you might benefit from locality-of-reference by using a boost::container::flat_set

Is The Cost Real?

If you think that "constructing the Edge" is a waste of resources, forget about that: it's a POD type (std::pair<int, int>) and as such has only trivial constructor/destructors. Seeing that set<Edge> is a template class, most operations on it can be inlined. The compiler will inline away the method call, enregister the arguments, remove redundant load/store cycles and effectively generate optimal code:

#include <set>
#include <utility>

using Edge = std::pair<int, int>;
using Blacklist = std::set<Edge>;

struct Pred {
    Blacklist blacklist { { 
        { 92, 29 },
        { 74, 92 },
        { 86, 6 },
        { 67, 35 },
        { 59, 4 },
        { 66, 13 },
        { 82, 37 },
        { 51, 94 },
        { 32, 6 }
    } };

    bool operator()(int source, int target) const {
        return blacklist.end() != blacklist.find(Edge {source, target});
    }
};

View Disassembly Live On Godbolt GCC Explorer

Pro tip: Click # button on the Clang disassembly to see optimizer comments

Summary The cost of the Edge type is non-existent. Any real cost would be down to using boost::source() and boost::target() on the edge_descriptor.

Seeing that your edge container selector is listS, your edge containers are node-based, meaning that the edge-descriptor is stable, and basically a type-erased reference to the edge object. Calling boost::source(e, g) does little more than casting the descriptor and dereferencing. Depending on how it's used, the compiler might even be able to see through these indirections.

If that cost is not to your liking, tweak the Graph type :) (Your use case might warrant an EdgeList concept instead, or benefit from using a node-based edge container etc.).

这篇关于增强带有黑名单边缘的过滤图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！