import sys

from AdjacencyListGraph import AdjacencyListGraph

from AdjacencyMatrixGraph import AdjacencyMatrixGraph

from GraphCommands import $*$

def main$()$:

graph$1=$ AdjacencyListGraph$()$

graph$2=$ AdjacencyMatrixGraph$()$

# Test AdjacencyListGraph first

print$("$AdjacencyListGraph: $")$

adj$\_$pass $=$ test$\_$graph$($sys$.$stdout, graph$1)$

print$()$

# Test AdjacencyMatrixGraph second

print$("$AdjacencyMatrixGraph: $")$

mat$\_$pass $=$ test$\_$graph$($sys$.$stdout, graph$2)$

print$($f$"""$

Summary:

AdjacencyListGraph: $\{"$PASS$"$ if adj$\_$pass else "FAIL"$\}$

AdjacencyMatrixGraph: $\{"$PASS$"$ if mat$\_$pass else "FAIL"$\}""",$

$)$

def test$\_$graph$($test$\_$feedback, graph$)$:

commands $=($

AddVertexCommand$("$A$",$ True$),$

AddVertexCommand$("$B$",$ True$),$

# exist, C$,$ D$,$ E

GetVertexCommand$("$C$",$ False$),$

GetVertexCommand$("$A$",$ True$),$

GetVertexCommand$("$B$",$ True$),$

GetVertexCommand$("$E$",$ False$),$

GetVertexCommand$("$D$",$ False$),$

# vertices

AddVertexCommand$("$C$",$ True$),$

AddVertexCommand$("$D$",$ True$),$

AddVertexCommand$("$E$",$ True$),$

# edges

AddEdgeCommand$("$B$","$C$",$ True$),$

AddEdgeCommand$("$C$","$A$",$ True$),$

AddEdgeCommand$("$C$","$D$",$ True$),$

AddEdgeCommand$("$C$","$E$",$ True$),$

AddEdgeCommand$("$D$","$C$",$ True$),$

AddEdgeCommand$("$E$","$A$",$ True$),$

AddEdgeCommand$("$E$","$D$",$ True$),$

# fail

AddEdgeCommand$("$C$","$E$",$ False$),$

AddEdgeCommand$("$D$","$C$",$ False$),$

VerifyEdgesFromCommand$("$A$",()),$

VerifyEdgesFromCommand$("$B$",("$C$")),$

VerifyEdgesFromCommand$("$C$",("$A$","$D$","$E$")),$

VerifyEdgesFromCommand$("$D$",("$C$")),$

VerifyEdgesFromCommand$("$E$",("$A$","$D$")),$

VerifyEdgesToCommand$("$A$",("$C$","$E$")),$

VerifyEdgesToCommand$("$B$",()),$

VerifyEdgesToCommand$("$C$",("$B$","$D$")),$

VerifyEdgesToCommand$("$D$",("$C$","$E$")),$

VerifyEdgesToCommand$("$E$",("$C$")),$

# edges

HasEdgeCommand$("$A$","$C$",$ False$),$

HasEdgeCommand$("$A$","$E$",$ False$),$

HasEdgeCommand$("$B$","$C$",$ True$),$

HasEdgeCommand$("$C$","$A$",$ True$),$

HasEdgeCommand$("$C$","$B$",$ False$),$

HasEdgeCommand$("$C$","$D$",$ True$),$

HasEdgeCommand$("$C$","$E$",$ True$),$

HasEdgeCommand$("$D$","$C$",$ True$),$

HasEdgeCommand$("$E$","$A$",$ True$),$

HasEdgeCommand$("$E$","$C$",$ False$),$

HasEdgeCommand$("$E$","$D$",$ True$)$

$)$

# command, fails

for command in commands:

if not command.execute$($test$\_$feedback, graph$)$:

return False

return True

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

main$()$

class Vertex:

def $\_\_$init$\_\_($self$,$ vertex$\_$label$)$:

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

def set$\_$label$($self$,$ new$\_$label$)$:

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

def get$\_$label$($self$,)$:

return self.vertex$\_$label

# Prints self vertex's label

def print$($self$,$ output$)$:

print$($self$.$vertex$\_$label, file$=$output, end$=\text{'}\text{'})$

from Vertex import Vertex

class Edge:

def $\_\_$init$\_\_($self$,$ from$\_$vertex, to$\_$vertex$)$:

self.from$\_$vertex $=$ from$\_$vertex

self.to$\_$vertex $=$ to$\_$vertex

def equals$($self$,$ other$)$:

return $($self$.$from$\_$vertex $==$ other.from$\_$vertex and

self.to$\_$vertex $==$ other.to$\_$vertex$)$

# Prints self edge in the form $"$A to B$",$ where $"$A$"$ is the from$\_$vertex's label

# and $"$B$"$ is the to$\_$vertex's label.

def print$($self$,$ output$)$:

self.from$\_$vertex.print$($output$)$

print$("$ to $",$ file$=$output, end$=\text{'}\text{'})$

self.to$\_$vertex.print$($output$)$

from abc import ABC, abstractmethod

# class for a directed, unweighted graph

class DirectedGraph:

# Creates and adds a new vertex to the graph, provided a vertex with the

# same label doesn't already exist in the graph. Returns the new vertex on

# success, None on failure.

def add$\_$vertex$($self$,$ new$\_$vertex$\_$label$)$:

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

# Adds a directed edge from the first to the second vertex. No change is made

# and false is returned if the edge already exists in the graph. Otherwise the

# new edge is added and True is returned.

@abstractmethod

def add$\_$directed$\_$edge$($self$,$ from$\_$vertex, to$\_$vertex$)$:

pass

# Returns a list of edges with the specified from$\_$vertex.

@abstractmethod

def get$\_$edges$\_$from$($from$\_$vertex$)$:

pass

# Returns a list of edges with the specified to$\_$vertex

@abstractmethod

def get$\_$edges$\_$to$($to$\_$vertex$)$:

pass

# Returns a vertex with a matching label, or None if no such vertex exists

@abstractmethod

def get$\_$vertex$($self$,$ vertex$\_$label$)$:

pass

# Returns True if this graph has an edge from from$\_$vertex to to$\_$vertex, False otherwise

@abstractmethod

def has$\_$edge$($self$,$ from$\_$vertex, to$\_$vertex$)$:

pass

from Vertex import Vertex

class AdjacencyListVertex$($Vertex$)$:

# List of vertices adjacent to this vertex. For each vertex V in this list, V is

# adjacent to this vertex, meaning an edge from this vertex to V exists in the graph.

def $\_\_$init$\_\_($self$,$ label$)$:

super$().\_\_$init$\_\_($label$)$

self.adjacent $=[]$

from Edge import Edge

from DirectedGraph import DirectedGraph

from AdjacencyListVertex import AdjacencyListVertex

class AdjacencyListGraph$($DirectedGraph$)$:

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

self.vertices $=[]$

# Creates and adds a new vertex to the graph, provided a vertex with the

# same label doesn't already exist in the graph. Returns the new vertex on

# success, None on failure.

def add$\_$vertex$($self$,$ new$\_$vertex$\_$label$)$:

# Your code here $($remove placeholder line below$)$

pass

# Adds a directed edge from the first to the second vertex. If the edge

# already exists in the graph, no change is made and False is returned.

# Other