Module $11$ Homework $-$ Graphs

Overview

Implement data structure dependent methods for a directed, non$-$weighted graph in AdjacencySetGraph

and EdgeSetGraph classes. Then implement a parent class Graph with methods that are independent of the

underlying data structures:

The Graph class is a convenient way to factor out common functionality, but should not be used on it$$s own $-$

users should specify an AdjacencySetGraph or EdgeSetGraph. We explicitly raise a NotImplementedError

in Graph.init to ensure this.

AdjacencySetGraph

Store a dictionary of vertex:set$($vertices$)$ pairs, to allow fast iteration over neighbors.

$$ Inherits from Graph

$\_\_$init$\_\_($V$,$ E$)-$ initialize a graph with a set of vertices and a set of edges $($we$$ll use tuples as edges,

so E should be a set of tuples$).$ Both parameters should be optional $-$ a user should be able to use asg

$=$ AdjacencySetGraph$()$ to create an empty graph.

$1$

$\_\_$iter$\_\_()-$ returns an iterator over all vertices in the graph

$$ add$\_$vertex$($v$)-$ adds vertex to graph

$$ add$\_$edge$($u$,$ v$)-$ adds edge $($u$,$ v$)$ to graph

$$ neighbors$($v$)-$ returns an iterator over all out$-$neighbors of v$.$

EdgeSetGraph

Adhere to and implement all of the above bullets, but use an edge set instead of an adjacency set $($store a set

of vertices and a set of edges instead of a dictionary of vertex:set$($neighbors$)$ pairs$).$

Graph Methods

Methods whose implementations that do not depend on the underlying data structure $($though the running

times could differ$)$ are factored out here.

$$ connected$($v$1,$ v$2)-$ returns True $($False$)$ if there is $($is not$)$ a path from v$1$ to v$2.$

$$ bfs$($v$)-$ returns a valid breadth$-$first search tree $($see below for details$).$

$$ Be careful about efficiency here: use an efficient queue.

$$ Note there could be multiple valid BFS trees based on the same graph. As long as your tree

represents a valid BFS traversal, you will receive full credit.

$$ dfs$($v$)-$ returns a valid depth$-$first search tree $($see below for details$).$

$$ Be careful about efficiency here: use an efficient stack.

$$ Note there could be multiple valid DFS trees based on the same graph. As long as your tree

represents a valid DFS traversal, you will receive full credit.

$$ shortest$\_$path$($v$1,$ v$2)-$ returns a tuple of the minimum distance between v$1$ and v$2$ and a list

containing the edges of a minimal distance path from v$1$ to v$2($the edges should be in the proper order

to traverse from v$1$ to v$2).$ If there is no path from v$1$ to v$2,$ return $($float$("$inf$"),$ None$).$

$$ has$\_$cycle$()-$ returns a tuple of True and a list of edges that comprise a cycle if the graph has a cycle

$($the edges should be in the proper order to traverse the cycle completely$).$ Returns $($False$,$ None$)$

otherwise.

BFS$/$DFS Trees

For both bfs and dfs$,$ you must return a corresponding tree in a dictionary. Refer to lecture slides or Chapter

$21$ in the textbook for more info.

Some Example Behavior

$>>>$ V $=\{\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$C$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'},\text{'}$F$\text{'}\}$

$>>>$ E $=\{(\text{'}$A$\text{'},\text{'}$B$\text{'}),(\text{'}$A$\text{'},\text{'}$C$\text{'}),$

$(\text{'}$B$\text{'},\text{'}$C$\text{'}),(\text{'}$B$\text{'},\text{'}$D$\text{'}),$

$(\text{'}$C$\text{'},\text{'}$E$\text{'}),$

$(\text{'}$D$\text{'},\text{'}$F$\text{'}),$

$(\text{'}$E$\text{'},\text{'}$D$\text{'}),$

$(\text{'}$F$\text{'},\text{'}$E$\text{'})\}$

$2$

$>>>$ g $=$ AdjacencySetGraph$($V$,$ E$)$

$>>>$ g$.$connected$(\text{'}$A$\text{'},\text{'}$E$\text{'})$

True

$>>>$ g$.$bfs$(\text{'}$A$\text{'})$

$\{\text{'}$A$\text{'}$: None, $\text{'}$B$\text{'}$: $\text{'}$A$\text{'},\text{'}$C$\text{'}$: $\text{'}$A$\text{'},\text{'}$D$\text{'}$: $\text{'}$B$\text{'},\text{'}$E$\text{'}$: $\text{'}$C$\text{'},\text{'}$F$\text{'}$: $\text{'}$D$\text{'}\}$

$>>>$ g$.$dfs$(\text{'}$B$\text{'})$

$\{\text{'}$B$\text{'}$: None, $\text{'}$C$\text{'}$: $\text{'}$B$\text{'},\text{'}$E$\text{'}$: $\text{'}$C$\text{'},\text{'}$D$\text{'}$: $\text{'}$E$\text{'},\text{'}$F$\text{'}$: $\text{'}$D$\text{'}\}$

$>>>$ g$.$has$\_$cycle$()$

$($True$,[(\text{'}$D$\text{'},\text{'}$F$\text{'}),(\text{'}$F$\text{'},\text{'}$E$\text{'}),(\text{'}$E$\text{'},\text{'}$D$\text{'})])$

$>>>$ g$.$shortest$\_$path$(\text{'}$A$\text{'},\text{'}$F$\text{'})$

$(3,[(\text{'}$A$\text{'},\text{'}$B$\text{'}),(\text{'}$B$\text{'},\text{'}$D$\text{'}),(\text{'}$D$\text{'},\text{'}$F$\text{'})])$

Imports

No imports allowed on this assignment, with the following exceptions:

$$ Any modules you have written yourself

$$ Queue from the queue$2050.$py file distributed with the starter code

$$ Stack from the stack$2050.$py file distributed with the starter code

$$ typing $-$ this is not required, but some students have requested it