Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Skiena's DFS
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.