Topological Sort and Graphing in Python 3

Question

I wrote a program for DFS traversal, topological sort, find all vertices, and has_cycle methods.

Can you please suggest more elegant and eloquent ways for this program?
(Perhaps better ways to represent a graph with vertices and edges?)

NOTE: dfs and has_cycle implementation is inspired by the book "Algorithm Design Manual".

from itertools import dropwhile

class Graph(object):
    @staticmethod
    def dfs(v, edges, may_enter=None, cross=None, leave=None):
        if may_enter is None:
            may_enter = lambda v, entered=set(): v not in entered and not entered.add(v)
        if may_enter(v):
            for e in (edges[v] or []):
                cross is not None and cross(e, v)
                Graph.dfs(e.y, edges, may_enter, cross, leave)
            leave is not None and leave(v)

class Edge(object): # weight is None in unweighted graph
    def __init__(self, y=None, weight=None):
        self.y, self.weight = y, weight

    def __repr__(self):
        attrs = (self.weight, self.y)
        return "Edge({0})".format(', '.join(reversed( \
            [repr(e) for e in dropwhile(lambda e: e is None, attrs)])))

Topological Sort

def topological_sort(edges):
    sort, entered = [], set()
    may_enter = lambda v: v not in entered and not entered.add(v)
    leave = lambda v: sort.append(v)
    for v in range(len(edges)):
        if v not in entered:
            Graph.dfs(v, edges, may_enter, leave=leave)
    return sort

# graph:       D3 ⇾ H7
#              ↑
#    ┌──────── B1 ⇾ F5
#    ↓         ↑     ↑
#   J9 ⇽ E4 ⇽ A0 ⇾ C2 ⇾ I8
#              ↓
#              G6
edges = [[]] * 10
edges[0] = [Edge(1), Edge(2), Edge(4), Edge(6)] # 1, 2, 4, and 6
edges[1] = [Edge(3), Edge(5), Edge(9)] # 3, 5, and 9
edges[2] = [Edge(5), Edge(8)] # 5, 8
edges[3] = [Edge(7)] # 7
edges[4] = [Edge(9)] # 9

assert [7, 3, 5, 9, 1, 8, 2, 4, 6, 0] == topological_sort(edges)

Find all vertices

def find_all(source, edges):
    reached = set()
    cross = lambda e, x: reached.add(e.y)
    Graph.dfs(source, edges, None, cross, None)  
    return reached

def can_reach(source, sink):
    return sink in find_all(source, edges)

# graph: B1 ← C2 → A0
#        ↓  ↗
#        D3 ← E4
edges = [[]] * 5
edges[0] = [] # out-degree of 0
edges[1] = [Edge(3)] # B1 → D3
edges[2] = [Edge(0), Edge(1)] # C2 → A0, C2 → B1
edges[3] = [Edge(2)] # D3 → C2
edges[4] = [Edge(3)] # E4 → D3

assert can_reach(4, 0)
assert not can_reach(0, 4)
assert not can_reach(3, 4)

assert {0, 1, 2, 3} == find_all(4, edges)
assert {0, 1, 2, 3} == find_all(3, edges)
assert {0, 1, 2, 3} == find_all(2, edges)
assert set() == find_all(0, edges)

Has cycle (inspired by Algorithm Design Manual)

def has_cycle(edges, directed):
    for v in range(len(edges)):
        entered = set()
        exited = set()
        tree_edges = {} # keyed by children; also called parents map.
        back_edges = {} # keyed by ancestors, or the other end-point.
        may_enter = lambda v: v not in entered and not entered.add(v)
        exit = lambda v: exited.add(v)
        def cross(e, x):
            if e.y not in entered:
                tree_edges[e.y] = x
            elif (not directed and tree_edges.get(x, None) != e.y) \
                 or (directed and e.y not in exited):
                 back_edges.setdefault(e.y, []).append(x) # x = 1, e.y = 0
        Graph.dfs(v, edges, may_enter, cross, exit)
        if back_edges:
            return True
    else:
        return False

Has cycle in Directed Graph

# directed graph: B1 ← C2 → A0
#                 ↓  ↗
#                 D3 ← E4
edges = [[]] * 5
edges[0] = [] # out-degree of 0
edges[1] = [Edge(3, 4)] # B1 → D3
edges[2] = [Edge(0, 4), Edge(1, 6)] # C2 → A0, C2 → B1
edges[3] = [Edge(2, 9)] # D3 → C2
edges[4] = [Edge(3, 3)] # E4 → D3
assert has_cycle(edges, True)

# directed graph: B1 ← C2 → A0
#                 ↓    ↓
#                 D3 ← E4
edges = [[]] * 5
edges[0] = []
edges[1] = [Edge(3)]
edges[2] = [Edge(0), Edge(1), Edge(4)]
edges[3] = []
edges[4] = [Edge(3)]
assert not has_cycle(edges, True)

Has cycle in Undirected Graph

# undirected graph: A0 - B1 - C2
edges = [[]] * 3
edges[0] = [Edge(1)] # A0 - B1
edges[1] = [Edge(0), Edge(2)] # B1 - A0, B1 - C2
edges[2] = [Edge(1)] # C2 - B1
assert not has_cycle(edges, False)

# undirected graph: A0 - B1
#                    \  /
#                     C2
edges[0].append(Edge(2)) # A0 - C2
edges[2].append(Edge(0)) # C2 - A0
assert has_cycle(edges, False)

Answer 1

1. There's no documentation! How am I supposed to use any of this code? There ought to be docstrings for all the classes and functions.

2. The class Graph contains a single function decorated with @staticmethod. So why bother with a class at all? Python is not Java: not everything needs to be a class.

3. Your code requires a graph to be represented as a list giving the neighbours of each vertex, where the neighbours are represented as a list of objects whose y attribute gives the index of the neighbouring vertex in the list.

   This data structure is going to be rather awkward to use because (a) this make it difficult to attach extra data to vertices; (b) vertices don't normally come in a numerical order (think of cities in a travelling salesman problem, or people in a social network analysis); (c) the user's data structures probably don't have the necessary y attribute.

   This means that the user needs to figure out some way to assign a range of numbers to the vertices, and also to map every neighbour to an object with a y attribute. A well-designed interface ought to make things simpler for its users, rather than more complicated.

   (I think that if you had tried to write user documentation as recommended in my point #1 above, then this problem would have become clearer to you.)

4. Writing:

   may_enter = lambda v, entered=set(): v not in entered and not entered.add(v)
   

   is unclear: first, you're using the default value for a keyword argument as a way to allocate a local variable, and second, set.add is not documented as returning anything, so why are you testing it as if it is a Boolean? You're relying on the obscure implementation detail that set.add happens to return None, which converts to Boolean as False. It would be clearer (and only a little longer if you count tokens rather than lines) if you kept it simple:

   entered = set()
   def may_enter(v):
       if v in entered:
           return False
       entered.add(v)
       return True
   

5. Similarly, instead of

   cross is not None and cross(e, v)
   

   it would be clearer to write:

   if cross is not None:
       cross(e, v)
   

6. All your algorithms that use Graph.dfs supply the same function for may_enter. This suggests to me that you could refactor this code to reduce duplication. The reason why these algorithms define their own may_enter functions (rather than sharing one implementation) is so that they can access the entered set (topological_sort needs to access it from the main loop; has_cycle needs to access it from its cross function).

   With some refactoring you could avoid the need for the algorithms to define their own may_enter function (for topological_sort, pass the entered set as a parameter to Graph.dfs; for has_cycle, pass it as an argument to cross).

7. Graph.dfs uses the Python stack to maintain its state. But the Python stack is fixed in size and so this will fail for large graphs. You should consider rewriting it to maintain its own stack.

8. The implementation of Edge.__repr__ seems very unclear, especially since this is just a convenience for debugging. A simple implementation like:

   return 'Edge(y={0.y!r}, weight={0.weight!r})'.format(self)
   

   would be perfectly adequate.