mercredi 30 mars 2016

How can I get input edges of a given vertex on a directed graph?

I have a directed graph and I want to fetch the parent of a given vertex.

Say I have the graph 1 -> 2 -> 3, I hold the vertex 2 and I want to get vertex 1.

My vertex and graph definitions:

struct TreeVertex   {  int id = -1;  };

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    TreeVertex
    > tree_t;

An MVCE showing what I want to achieve (see online here):

int main() {
    tree_t tree;
    auto v1 = boost::add_vertex( tree );    
    auto v2 = boost::add_vertex( tree );    
    auto v3 = boost::add_vertex( tree );    
    boost::add_edge( v1, v2, tree );
    boost::add_edge( v2, v3, tree );

// attempt to get the input edge of v2
    auto pair_it_edge = boost::in_edges( v2, tree ); // FAILS TO BUILD  
    auto v = boost::source( *pair_it_edge.first ); // should be v1
}

Another answer suggests transforming the graph into a BidirectionalGraph but I need to keep it directed.

Question: Is this possible ? How can I get the incoming edge of v2, so that I can extract v1 ?

Aucun commentaire:

Enregistrer un commentaire