Detecting Cycles in a Directed Graph

I needed an algorithm for detecting cycles in a directed graph. I came up with the following. It's probably something straight from a textbook, but I couldn't find a textbook that had one, so I came up with this myself. I like the simplicity. I also like that there's a well-defined point in the algorithm where you can do any additional processing on each node for which you find that is not part of a cycle.

The function makes few assumptions about the representation of the graph; instead of a graph object, it takes in two function arguments that are called to describe the graph:

• def NODES(): an iterable returning all nodes
• def EDGES(node): an iterable returning all nodes reached via node's outgoing edges

In addition it takes a third function argument which is called once for each node:

• def READY(node): called when we know node is not part of any cycles

The function returns None upon success, or a list containing the members of the first cycle found otherwise. Here's the algorithm:

def find_cycle(NODES, EDGES, READY):
  todo = set(NODES())
  while todo:
    node = todo.pop()
    stack = [node]
    while stack:
      top = stack[-1]
      for node in EDGES(top):
        if node in stack:
          return stack[stack.index(node):]
        if node in todo:
          stack.append(node)
          todo.remove(node)
          break
      else:
        node = stack.pop()
        READY(node)
  return None

Discussion: The EDGES() function may be called multiple times for the same node, and the for loop does some duplicate work in that case. A straightforward fix for this inefficiency is to maintain a parallel stack of iterators that is pushed and popped at the same times at the main stack, and at all times contains iter(node). I'll leave that version as an excercise.

Update: Fixed a typo in the algorithm (EDGES(top)) and renamed all to todo.

The History of Python - Introduction

Python is 19 years old now. I started the design and implementation of the language on a cold Christmas break in Amsterdam, in late December 1989. It started out as a typical hobby project. Little did I know where it would all lead.

With Python's coming of age, I am going to look back on the history of the language, from the conception as a personal tool, through the the early years of community building, (If Guido was hit by a bus?), all the way through the release of Python 3000, almost 19 years later. It's been quite an adventure, for myself as well as for the users of the language.

This won't be an ordinary blog post -- it'll be an open-ended series. I may invite guest writers. I'll be touching upon many aspects of the language's history and evolution, both technical and social.

I'll start with the gradual publication of material I wrote a few years ago, when I was invited to contribute an article on Python to HOPL-III, the third installment of ACM's prestigious History of Programming Languages conference, held roughly every ten years. Unfortunately, the demands of the rather academically inclined reviewers were too much for my poor hacker's brain. Once I realized that with every round of review the amount of writing left to do seemed to increase rather than decrease, I withdrew my draft. Bless those who persevered, but I don't believe that the resulting collection of papers gives a representative overview of the developments in programming languages of the past decade.

The next destination of the draft was a book on Python to be published by Addison-Wesley. Again, the mountain of raw material that I had collected was too large and at the same time too incomplete to serve as a major section of the book, despite the editing help I received from David Beazley, a much better writer than I am.

As they tell prospective Ph.D. students, the best way to eat an elephant is one meal at a time. So today I am publishing the first bit of the elephant, perhaps still somewhat uncooked, but at least it's out there. Hopefully others who were there at the time can help clear up the inevitable omissions and mistakes. I have many more chapters, each still requiring some editing, and I expect this to be a long-running series. Therefore I am starting a separate blog title for this, unimaginatively called The History of Python. Follow the link and enjoy!