@not_implemented_for('undirected')
def immediate_dominators(G, start):
 if (start not in G):
  raise nx.NetworkXError('start is not in G')
 idom = {start: start}
 order = list(nx.dfs_postorder_nodes(G, start))
 dfn = {u: i for (i, u) in enumerate(order)}
 order.pop()
 order.reverse()
 def intersect(u, v):
  while (u != v):
   while (dfn[u] < dfn[v]):
    u = idom[u]
   while (dfn[u] > dfn[v]):
    v = idom[v]
  return u
 changed = True
 while changed:
  changed = False
  for u in order:
   new_idom = reduce(intersect, (v for v in G.pred[u] if (v in idom)))
   if ((u not in idom) or (idom[u] != new_idom)):
    idom[u] = new_idom
    changed = True
 return idom

@ not_implemented_for ( 'undirected' ) def immediate_dominators ( G , start ) : if ( start not in G ) : raise nx . NetworkXError ( 'start is not in G' ) idom = { start : start } order = list ( nx . dfs_postorder_nodes ( G , start ) ) dfn = { u : i for ( i , u ) in enumerate ( order ) } order . pop ( ) order . reverse ( ) def intersect ( u , v ) : while ( u != v ) : while ( dfn [ u ] < dfn [ v ] ) : u = idom [ u ] while ( dfn [ u ] > dfn [ v ] ) : v = idom [ v ] return u changed = True while changed : changed = False for u in order : new_idom = reduce ( intersect , ( v for v in G . pred [ u ] if ( v in idom ) ) ) if ( ( u not in idom ) or ( idom [ u ] != new_idom ) ) : idom [ u ] = new_idom changed = True return idom
returns the immediate dominators of all nodes of a directed graph .