Boost directed graph: comparing edges of a vertex

Question

A brief background: I'm building a semantic graph, using BGL directed graphs with an adjacency list:

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;

One of the things I need to be able to do, is process a smaller graph (a subgraph) into my main graph.

Doing so, involves copying the Node pointers if needed, copying the vertices from the subgraph into the main graph if they don't already exist, and most importantly, copying the edges for each vertex found in the subgraph, into the main one, if not already established.

The first two tasks are not that complicated. However, I cannot for the life of me, find a way to compare two edges:

 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; });
        }
      }
    }

The compiler throws a warning at the last std::find_if above ^^:

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

Hinting that my lambda captured parameter should be a pair (I'm guessing an actual edge?).

So, my question is: How can I find if that similar edge exists in my vertex's out edges?

sehe sehe · Accepted Answer · 2013-12-08T21:47:54

you declared a as an iterator:

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

It doesn't make sense to compare an iterator to an edge.

Instead, dereference the iterator to get the edge it is "pointing to":

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

This compiles for me: See it Live on Coliru

Other problems:

std::find_if(it, end, [&](const Vertex vertex) { return _graph[*it]->Hash() == node->Hash(); });
- statement has no effect (the result of the find is unused)
- you are looking things up by a hash?! This is almost certainly a design error. If Hash() returns a hash, you CANNOT use it to identify nodes. Instead hash-tables use it to identify the the bucket in which to sort the node. However, to identify a node, you need to do an equality test (different Nodes can share the same hash)

the lambdas take their arguments by value. This is inefficient

Typical code would see

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;
}

Boost directed graph: comparing edges of a vertex

1 Answers

Other problems: