ALGORITHM DFS$($G$)$

$//$Implements a depth$-$first search traversal of a given graph

$//$Input: Graph G $=$ V$,$E

$//$Output: Graph G with its vertices marked with consecutive integers

$//$ in the order they are first encountered by the DFS traversal

mark each vertex in V with $0$ as a mark of being $$unvisited$$

count $0$

for each vertex v in V do

if v is marked with $0$

dfs$($v$)$

dfs$($v$)$

$//$visits recursively all the unvisited vertices connected to vertex v

$//$by a path and numbers them in the order they are encountered

$//$via global variable count

count $$ count $+1$; mark v with count

for each vertex w in V adjacent to v do

if w is marked with $0$

dfs$($w$)$

# graph.py

class Graph:

$"""$ Super class for implementations of Graph

A Graph uses ints $0--($n$-1)$ to represent vertices, but also maintains

data structures to "translate" between vertices and a set of labels.

$>>>$ g $=$ Graph$([\text{'}$a$\text{'},\text{'}$b$\text{'},\text{'}$c$\text{'}])$

$>>>$ g$.$label$[0]$

$\text{'}$a$\text{'}$

$>>>$ g$.$id$[\text{'}$b$\text{'}]$

$1$

This class should be subclassed to create a concrete implementation of

graphs $($e$.$g$.,$ with an adjacency matrix or an adjacency list$).$

$"""$

class Edge:

$"""$ Edge is a record to supply edge information $"""$

def $\_\_$init$\_\_($self$,$ v$1,$ v$2,$ weight$=1)$:

self.v$1=$ v$1$

self.v$2=$ v$2$

self.weight $=$ weight

def $\_\_$repr$\_\_($self$)$:

return f$"$Edge$(\{$self$.$v$1\},\{$self$.$v$2\},\{$self$.$weight$\})"$

def $\_\_$init$\_\_($self$,$ vertex$\_$labels, directed$=$False$)$:

$"""$Create empty graph from list of vertex labels $($strings$)$

$"""$

self.label $=$ vertex$\_$labels

self.id $=\{$label: id for id$,$ label in enumerate$($vertex$\_$labels$)\}$

self.n$\_$verts $=$ len$($vertex$\_$labels$)$

self.n$\_$edges $=0$

self.directed $=$ directed

def verticies$($self$)$:

$"""$Return an iterator for label ids

$"""$

return range$($self$.$n$\_$verts$)$

def add$\_$label$\_$edge$($self$,$ label$1,$ label$2,$ weight$=1)$:

self.add$\_$edge$($self$.$id$[$label$1],$ self.id$[$label$2],$ weight$)$

# below are methods to be implemented in a subclass

def add$\_$edge$($self$,$ v$1,$ v$2,$ weight$=1)$:

$"""$Add the edge from v$1$ to v$2$ to the graph

$"""$

raise NotImplementedError

def edge$($self$,$ v$1,$ v$2)$:

$"""$Returns an Edge object if edge $($v$1,$ v$2)$ is in graph, otherwise None

Can be used as an existence test

e $=$ g$.$edge$($v$,$ v$1)$

if e:

# edge exists

$"""$

raise NotImplementedError

def edges$($self$,$ vertex$=$None$)$:

$"""$Returns an iterator over Edge objects

If vertex is None the iterator supplies all edges of the

graph. When vertex is supplied, it iterates over edges from

that vertex $($i$.$e$.,$ the adjacency list$)$

$"""$

raise NotImplementedError

def delete$\_$edge$($self$,$ v$1,$ v$2)$:

$"""$Deletes the edge. Does nothing if the edge does not exist

$"""$

raise NotImplementedError

# Example start of subclass $($should be in matrixgraph.py$)$

class MatrixGraph$($Graph$)$:

def $\_\_$init$\_\_($self$,$ labels, directed$)$:

super$().\_\_$init$\_\_($labels$,$ directed$)$

# other initialization here