Skiena's DFS

adjacency_list.py

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:
    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)