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

Question

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.