"ulimit -s" has no effect?

[Josiah Carlson]

> 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.

visit(v) is now non-recursive.  I ran a test on a randomly generated 26 
node graph, and both versions resulted in the same components, node 
visit order, etc.  I think you'll be happy with it.

I notice that you are a graduate student at the University of Toronto. 
Out of curiosity, what area are you focusing on?  From your playing with 
Tarjan's algorithm, I would expect that you are either a Theory student, 
or are taking a Theory course to fulfill a requirement of some sort. 
It's all good.

I'm a graduate student at University of California at Irvine, studying 
Theory myself.  Well, I should probably get back to my own work.

Enjoy,
  - Josiah


     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):
             call_stack = [(1, v, iter(v.kids), None)]
             while call_stack:
                 tovisit, v, iterator, w = call_stack.pop()
                 if tovisit:
                     v.visited = True
                     nodes_visit_order.append(v)
                     v.num = self.next_visit_num
                     self.next_visit_num += 1
                     stack.append(v)
                 if w and not w.in_component:
                     v.root = nodes_visit_order[ min(v.root.num,\
                                                     w.root.num)]
                 cont = 0
                 for w, notused in iterator:
                     if not w.visited:
                         cont = 1
                         call_stack.append((0, v, iterator, w))
                         call_stack.append((1, w, iter(w.kids), None))
                         break
                     if not w.in_component:
                         v.root = nodes_visit_order[ min(v.root.num,\
                                                         w.root.num) ]
                 if cont:
                     continue
                 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