首页 文章

增强有向图：比较顶点的边缘

提问于
浏览 次
1

简要背景：我正在构建一个语义图，使用带有邻接列表的BGL有向图：

class SemanticGraph
{
  public:
    typedef std::shared_ptr< Node > Node_ptr;
    typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Node_ptr > Graph;
    typedef boost::graph_traits< Graph >::vertex_descriptor Vertex;
    typedef boost::graph_traits< Graph >::edge_descriptor Edge;

我需要做的一件事就是将一个较小的图形（子图）处理到我的主图中 .

这样做，包括在需要时复制节点指针，如果它们尚不存在，则将子图中的顶点复制到主图中，最重要的是，将子图中找到的每个顶点的边复制到主图中，如果还没有 Build .

前两个任务并不复杂 . 但是，我不能为我的生活，找到一种比较两个边缘的方法：

void AddSubGraph( SemanticGraph subgraph )
 {
      typename boost::graph_traits<Graph>::vertex_iterator it, end;
      Vertex vertex;

      for ( auto node : subgraph._nodes )
      {
        if ( !findNode( node ) )
           _nodes.push_back( node );

        boost::tie( it, end ) = boost::vertices( _graph );
        std::find_if( it, end, [&]( const Vertex vertex ){ return _graph[*it]->Hash() == node->Hash(); });

        if ( it == end )
          vertex = boost::add_vertex( node, _graph );
        else
          vertex = boost::vertex( *it, _graph );

        boost::tie( it, end ) = boost::vertices( subgraph._graph );
        std::find_if( it, end, [&]( const Vertex vertex ){ return subgraph._graph[*it]->Hash() == node->Hash(); });

        auto subgraph_vertex = boost::vertex( *it, subgraph._graph );
        typename boost::graph_traits<Graph>::out_edge_iterator a, z;

        // Iterate subgraph's vertex out edges
        for ( boost::tie ( a, z ) = boost::out_edges( subgraph_vertex, subgraph._graph );
              a != z;
              ++a )
        {
           typename boost::graph_traits<Graph>::out_edge_iterator my_edge, edge_end;
           boost::tie ( my_edge, edge_end ) = boost::out_edges( vertex, _graph );
           // How can I see if the same edge as the one pointed by edge iterator a, exists in my vertex's edges?
           std::find_if( my_edge, edge_end, [&]( const Edge edge ){ return edge == a; });
        }
      }
    }

编译器在^^上面的最后一个std :: find_if处抛出警告：

‘const Edge {aka const boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>}’ is not derived from ‘const std::pair<_T1, _T2>’

暗示我的lambda捕获参数应该是一对（我猜一个真正的边缘？） .

所以，我的问题是： How can I find if that similar edge exists in my vertex's out edges?

c++ algorithm boost graph

1 回答

  • 5

    你声明 a 作为迭代器：

    typename boost::graph_traits<Graph>::out_edge_iterator a, z;

    将迭代器与边缘进行比较是没有意义的 .

    相反，取消引用迭代器以获得它“指向”的边缘：

    std::find_if(my_edge, edge_end, 
     [&](const Edge edge) { return edge == *a; });

    这为我编译：看到它 Live on Coliru

    其他问题：

    • std::find_if(it, end, [&](const Vertex vertex) { return _graph[*it]->Hash() == node->Hash(); });

    • 语句无效（查找结果未使用）

    • 你正在通过哈希来查找东西？！这几乎肯定是一个设计错误 . 如果 Hash() 返回哈希值，则不能使用它来标识节点 . 相反，散列表使用它来标识要对节点进行排序的存储区 . 但是，要识别节点，您需要进行相等测试（不同的节点可以共享相同的哈希）

    • lambdas按 Value 取得他们的论据 . 这是低效的

    典型代码会看到

    vertex_iterator match = std::find_if(it, end, 
    [&](Vertex const& vertex) { return _graph[*it] == node; });`

if (end != match)
{
    // yes `match` is a match
}

    #include <boost/graph/adjacency_list.hpp>
#include <memory>

struct Node
{
    int id;
    size_t Hash() const { return id; }
    bool operator<(const Node& other) const { return id < other.id; }
    bool operator==(const Node& other) const { return id==other.id; }
};

class SemanticGraph
{
public:
    typedef std::shared_ptr< Node > Node_ptr;
    typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Node_ptr > Graph;
    typedef boost::graph_traits< Graph >::vertex_descriptor Vertex;
    typedef boost::graph_traits< Graph >::edge_descriptor Edge;

    std::vector<Node_ptr> _nodes;
    Graph _graph;

    bool findNode(Node_ptr const& n) const { return std::find(begin(_nodes), end(_nodes), n) != end(_nodes); }

    void AddSubGraph(SemanticGraph subgraph)
    {
        typename boost::graph_traits<Graph>::vertex_iterator it, end;
        Vertex vertex;
        for(auto node : subgraph._nodes)
        {
            if(!findNode(node))
            {
                _nodes.push_back(node);
            }
            boost::tie(it, end) = boost::vertices(_graph);
            std::find_if(it, end, [&](const Vertex vertex) { return _graph[*it]->Hash() == node->Hash(); });
            if(it == end)
                vertex = boost::add_vertex(node, _graph);
            else
                vertex = boost::vertex(*it, _graph);

            boost::tie(it, end) = boost::vertices(subgraph._graph);

            std::find_if(it, end, [&](const Vertex vertex) { return subgraph._graph[*it]->Hash() == node->Hash(); });

            auto subgraph_vertex = boost::vertex(*it, subgraph._graph);
            typename boost::graph_traits<Graph>::out_edge_iterator a, z;

            // Iterate subgraph's vertex out edges
            for(boost::tie(a, z) = boost::out_edges(subgraph_vertex, subgraph._graph);
                    a != z;
                    ++a)
            {
                typename boost::graph_traits<Graph>::out_edge_iterator my_edge, edge_end;
                boost::tie(my_edge, edge_end) = boost::out_edges(vertex, _graph);
                // How can I see if the same edge as the one pointed by edge iterator a, exists in my vertex's edges?
                std::find_if(my_edge, edge_end, [&](const Edge edge) { return edge == *a; });
            }
        }
    }
};

int main()
{
    SemanticGraph g;
}
    回复于

相关问题