Mark all reachable Nodes

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Mark all reachable Nodes

Gerion Entrup
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
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (673 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Mark all reachable Nodes

Snehal Shekatkar
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.label_out_component

Snehal


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, September 18, 2020 6:47 AM, Gerion Entrup <[hidden email]> 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
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool