# Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation

In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes:

As algorithm design paradigms go, a depth-first search isn't particularly intimidating. It is surprisingly subtle, however meaning that its correctness requires getting details right...

In undirected graphs, each edge (x,y) sits in the adjacency lists of vertex x and y... The labelling of edges as tree edges or back edges occurs during the first time the edge is explored... But when we encounter edge (x, y) from x, how can we tell if we have previously traversed the edge from y? The issue is easy if vertex y is undiscovered: (x,y) becomes a tree edge so this must be the first time. The issue is also easy if y has not been completely processed; since we explored the edge when we explored y this must be the second time. But what if y is an ancestor of x, and thus in a discovered state? Careful reflection will convince you that this must be our first traversal unless y is the immediate ancestor of x--ie, (y,x) is a tree edge. This can be established by testing if y == parent[x].

I mostly find Skiena quite a clear and understandable writer, and I'm pretty sure I understand the business with only tree edges/back edges in a DFS on an undirected graph, and I still find that last paragraph confusing as hell.

So I've taken Skiena's C implementation of adjacency-list based graphs + DFS and implemented them in Python 3.

I'm particularly interested in commentary that might help illuminate what's Skiena's trying to get across on pp 172 - 173, as well as Py3k feedback (I've mostly worked in Py2.7 for the past few years), or if I'm made any errors. As Skiena goes on to say: "I find the subtly of depth-first search-based algorithms kicks me in the head whenever I try to implement one."

The test graph I'm using is based off of Skiena's diagram from p.171, but with zero-indexing:

The only 3rd party library used is attrs. (Blame glyph)

from enum import Enum

import attr
from attr.validators import instance_of

@attr.s
class EdgeNode:
"""
An Edge & a Node.

The source node is the index of the head in the Graph's edges list.
"""
y = attr.ib(instance_of(int))
weight = attr.ib(default=1)
next = attr.ib(default=None)

def __str__(self):
return f'EdgeNode(y={self.y}, w={self.weight})'

def __iter__(self):
yield self
while self.next:
yield self.next
self = self.next

def degree(self):
out = 0
while self.next:
out += 1
self = self.next
return out

@attr.s
class Graph:
"""
Based on Skiena's Adjacency List implementation.

A graph is a list of linked lists. Each component of a linked list
is an EdgeNode instance.
"""
nodes = attr.ib(default=attr.Factory(list))
directed = attr.ib(instance_of(bool))
nedges = attr.ib(0)

def __str__(self):
out = []
for index, edgenode in enumerate(self.nodes):
out.append(f'{index}:\n')
while edgenode:
out.append(f'  {edgenode}\n')
edgenode = edgenode.next
return ''.join(out)

@property
def nnodes(self):
return len(self.nodes)

def add_edge(self, x, y, weight=1, directed=False):
while max(x, y) + 1 > len(self.nodes):
self.nodes.append(None)
edgenode = EdgeNode(y=y, weight=weight, next=self.nodes[x])
self.nodes[x] = edgenode
if directed:
self.nedges += 1
else:
self.add_edge(y, x, weight, directed=True)

graph = Graph(directed=False)
graph.add_edge(0, 5)
graph.add_edge(0, 1)
graph.add_edge(1, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
graph.add_edge(4, 0)
assert graph.nnodes == 6
assert graph.nedges == 7

def DFS(graph, start):
class States(Enum):
undiscovered = 0
discovered = 1
processed = 2

time = 0
node_states = [States.undiscovered] * graph.nnodes
node_parents = [None] * graph.nnodes
entry_times = [0] * graph.nnodes
exit_times = [0] * graph.nnodes

def recurse(v):
nonlocal time
time += 1
node_states[v] = States.discovered
entry_times[v] = time
print(f'Processing node #{v:02}')
adjacent_nodes = graph.nodes[v]
for node in adjacent_nodes:
if node_states[node.y] is States.undiscovered:
node_parents[node.y] = v
print(f'    Processing edge ({v:02}, {node.y:02})')
recurse(node.y)

elif node_states[node.y] is States.discovered or graph.directed:
print(f'   Processing edge ({v:02}, {node.y:02})')
print(f'Leaving node #{v:02}')
time += 1
exit_times[v] = time
node_states[v] = States.processed

recurse(start)
print(f'Parents: {node_parents}\nEntry times: {entry_times}\nExit times{exit_times}')

DFS(graph, 0)


Also available as a gist.