interview prep-part 5

The problem today is to find "dead" nodes in a graph. This sort of algorithm could be applied to all sorts of things such as eliminating the unreachable states in a DFA or unreachable code in a compiler.

class State:
def __init__(self, id):
self.id = id
self.outs = []
self.visited = False

def __repr__(self):
return str(self.id)

def dead(begins, all):
def search(state):
if state.visited:
return
state.visited = True
for s in state.outs:
search(s)

for s in begins:
search(s)

removable = []

for s in all:
if not s.visited:
removable.append(s);
return removable


if __name__ == "__main__":
ss = []
for i in range(6):
ss.append(State(i))
ss[0].outs = [ss[5]]
ss[1].outs = [ss[3],ss[2]]
ss[2].outs = [ss[1]]
ss[3].outs = [ss[2],ss[4]]
ss[4].outs = []
ss[5].outs = []
print dead([ss[1]], ss)
for s in ss:
s.visited = False
print dead([ss[0]], ss)
for s in ss:
s.visited = False
print dead([ss[0],ss[1]], ss)