Looks like you want to find the out-component for a given vertex. Have a look at this: https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.la... Snehal Sent with ProtonMail Secure Email. ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Friday, September 18, 2020 6:47 AM, Gerion Entrup <gerion.entrup@flump.de> wrote:
Hi,
I need to find a way to label all reachable nodes in a directed graph starting at a specific node. Is there a short way to do this?
Currently I use this:
graph = get_graph() is_reachable = graph.new_vp("bool") start_vertex = get_start_vertex()
tc = gt.transitive_closure(graph) is_reachable[start_vertex] = True for node in tc.vertex(start_vertex).out_neighbors(): is_reachable[graph.vertex(node)] = True
This works, but seems quite inefficient, since I don't need the full transitive closure (although I have multiple such start vertexes). Another possibility should be a raw DFS but this needs far more LOC, since it needs to stop when it backtracks and therefore needs a custom visitor.
Gerion_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool