"ulimit -s" has no effect?
Maciej Kalisiak
mac at dgp.toronto.edu
Sun Feb 8 21:22:47 EST 2004
Josiah Carlson <jcarlson at nospam.uci.edu> writes:
> Though it sometimes takes work, _any_ recursive algorithm can be made
> iterative. If you are willing to cough up your code (via email or otherwise),
> I'd be willing to give a shot at converting it.
n
Sure, here is the algorithm code. The routine is ripped out of a much larger
class, but it should be relatively independent. The class among other things
contains a graph, with the graph vertices in `self.nodes'. Each node object
has a `kids' attribute, which is a list of (kid node, edge type) tuples. The
edge type is unimportant as far as this algo is concerned.
def find_scc(self):
"""Find the 'strongly connected component' (SCC) of the graph.
Implemented using Tarjan's algorithm.
"""
# prep the vertices
for n in self.nodes:
n.num = None # the "visit order number"
n.root = n
n.visited = False
n.in_component = None
stack = []
components = []
nodes_visit_order = []
self.next_visit_num = 0
def visit(v):
v.visited = True
nodes_visit_order.append(v)
v.num = self.next_visit_num
self.next_visit_num += 1
stack.append(v)
for w,type in v.kids:
if not w.visited:
visit(w)
if not w.in_component:
v.root = nodes_visit_order[ min(v.root.num, w.root.num) ]
if v.root == v:
c = []
while 1:
w = stack.pop()
w.in_component = c
c.append(w)
if w == v:
break
components.append(c)
# the "main" routine
for v in self.nodes:
if not v.visited:
visit(v)
# extract SCC info
for n in self.nodes:
if n.in_component and len(n.in_component) > 1:
# part of SCC
n.hidden = False
else:
# either not in a component, or singleton case
n.hidden = True
More information about the Python-list
mailing list