Feature Request: Output dominator tree as GraphView

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

Feature Request: Output dominator tree as GraphView

Gerion Entrup
Hi,

the dominator_tree function in graph_tool.topology outputs a vertex property map that codifies a graph.
To use the other graph_tool algorithms, it would be beneficial to get the dominator_tree back as Graph (or better GraphView).

Is there already a way to do this? Otherwise, how do you like the idea to implement it?

A possible use case is it to check, if a dominates b.
This would be the pseudo code, if dominator_tree returns a graph like object:

dom_tree = graph_tool.topology.dominator_tree(graph, start, as_graph=True)
try:
    next(graph_tool.topology.all_paths(a, b))
    return True
except StopIteration:
    return False

This is without (the path search runs in Python, not that much LOCs but more difficult to understand in my opinion):
dom_tree = graph_tool.topology.dominator_tree(graph, start, as_graph=True)
while b:
    if a == b:
        return True
    b = dom_tree[b]
return False

Best,
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: Feature Request: Output dominator tree as GraphView

Tiago Peixoto
Administrator
Am 19.10.20 um 19:19 schrieb Gerion Entrup:

> Hi,
>
> the dominator_tree function in graph_tool.topology outputs a vertex property map that codifies a graph.
> To use the other graph_tool algorithms, it would be beneficial to get the dominator_tree back as Graph (or better GraphView).
>
> Is there already a way to do this? Otherwise, how do you like the idea to implement it?
>
> A possible use case is it to check, if a dominates b.
> This would be the pseudo code, if dominator_tree returns a graph like object:
>
> dom_tree = graph_tool.topology.dominator_tree(graph, start, as_graph=True)
That seems too ad hoc for me. I would prefer a more general function
that creates a tree graph from an adjacency vector.

Please open an issue for this, and I will take care when I find the time.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


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

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>