dominator_tree

Contents

dominator_tree#

graph_tool.topology.dominator_tree(g, root, dom_map=None)[source]#

Return a vertex property map the dominator vertices for each vertex.

Parameters:
gGraph

Graph to be used.

rootVertex

The root vertex.

dom_mapVertexPropertyMap (optional, default: None)

If provided, the dominator map will be written in this property map.

Returns:
dom_mapVertexPropertyMap

The dominator map. It contains for each vertex, the index of its dominator vertex.

Notes

A vertex u dominates a vertex v, if every path of directed graph from the entry to v must go through u.

The algorithm runs with \(O((V+E)\log (V+E))\) complexity.

References

Examples

>>> g = gt.random_graph(100, lambda: (2, 2))
>>> tree = gt.min_spanning_tree(g)
>>> g.set_edge_filter(tree)
>>> root = [v for v in g.vertices() if v.in_degree() == 0]
>>> dom = gt.dominator_tree(g, root[0])
>>> print(dom.a)
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Contents