Feature Request: Output dominator tree as GraphView

graph-tool
1

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

2

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