Re: [Boost-users] Iterating "root" vertices with boost::graph

Subject: Re: [Boost-users] Iterating "root" vertices with boost::graph
From: Daniel Hofmann (daniel_at_[hidden])
Date: 2015-11-24 20:30:19

The recommended way is to throw an exception from within the visitor:

http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/faq.html

e.g. create a termination struct:

    struct all_done_signal{};

and then throw it in the visitor:

    throw all_done_signal{};

and wrap the algorithm in a try-catch block:

    try {
      graph_algorithm(my_visitor);
    } catch(const all_done_signal&) { /* early termination */ }

Now, I don't understand why you need a depth-first-search for
enumerating all vertices with zero input edges. What about:

    boost::for_each(vertices(graph), check_no_in_edges);

with a check_no_in_edges lambda that counts the each vertex' in_edges?

(Note: instead of for_each you might want to use accumulate, or similar)

Cheers,
Daniel J H

On 11/25/2015 01:13 AM, Isaac Lascasas wrote:
> Hello I want to enumerate all vertices with zero input edge count in a
> graph, I am using DFS right now:
> 
> struct vertex_visitor : public boost::default_dfs_visitor
>     {
>     std::vector<vertex_t> Output;
> 
>     void discover_vertex(vertex_t v, graph_t const& g)
>         {
>         graph_t::in_edge_iterator edgeIt, edgeEnd;
>         tie(edgeIt, edgeEnd) = boost::in_edges(v, g);
>         if (edgeIt==edgeEnd)
>             Output.push_back(v);
>         }
>     };
> 
> vertex_visitor vis;
> boost::depth_first_search(g, boost::visitor(v));
> 
> However I don't know how to cleanly stop execution after depth 0 inside
> my visitor and I can't figure out a better way to archieve this. Since I
> am fairly new to boost graph I supose that I'm missing something.
> 
> Thanks.
> 
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>