"ulimit -s" has no effect?

Maciej Kalisiak mac at dgp.toronto.edu
Mon Feb 9 03:22:47 CET 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