from Edge import Edge

from DirectedGraph import DirectedGraph

from AdjacencyListVertex import AdjacencyListVertex

class AdjacencyListGraph

$($

DirectedGraph

$)$

:

$$ def

$\_$

$\_$

init

$\_$

$\_$

$($

self

$)$

:

$$ self.vertices

$=$

$[]$

$$ self.adjacency

$\_$

list

$=$

$\{\}$

$$ # 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

$)$

:

$$ if new

$\_$

vertex

$\_$

label in self.adjacency

$\_$

list:

$$ return None # Vertex already exists

$$ new

$\_$

vertex

$=$

$$AdjacencyListVertex

$($

new

$\_$

vertex

$\_$

label

$)$

$$ self.vertices.append

$($

new

$\_$

vertex

$)$

$$ self.adjacency

$\_$

list

$[$

new

$\_$

vertex

$\_$

label

$]$

$=$

$[]$

$$ return new

$\_$

vertex

$$ # 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.

$$ # Otherwise the new edge is added and True is returned.

$$ def add

$\_$

directed

$\_$

edge

$($

self

$,$

$$from

$\_$

vertex, to

$\_$

vertex

$)$

:

$$ if from

$\_$

vertex not in self.adjacency

$\_$

list or to

$\_$

vertex not in self.adjacency

$\_$

list:

$$ return False # One or both vertices do not exist

$$ if to

$\_$

vertex in self.adjacency

$\_$

list

$[$

from

$\_$

vertex

$]$

:

$$ return False # Edge already exists

$$ self.adjacency

$\_$

list

$[$

from

$\_$

vertex

$]$

$.$

append

$($

to

$\_$

vertex

$)$

$$ return True

$$ # Returns a list of edges with the specified from

$\_$

vertex.

$$ def get

$\_$

edges

$\_$

from

$($

self

$,$

$$from

$\_$

vertex

$)$

:

$$ if from

$\_$

vertex not in self.adjacency

$\_$

list:

$$ return

$[]$

$$ # No such vertex

$$ from

$\_$

vertex

$\_$

obj

$=$

$$self$.$get

$\_$

vertex

$($

from

$\_$

vertex

$)$

$$ return

$[$

Edge

$($

from

$\_$

vertex

$\_$

obj, self.get

$\_$

vertex

$($

to

$\_$

vertex

$))$

$$for to

$\_$

vertex in self.adjacency

$\_$

list

$[$

from

$\_$

vertex

$]]$

$$ # Returns a list of edges with the specified to

$\_$

vertex.

$$ def get

$\_$

edges

$\_$

to

$($

self

$,$

$$to

$\_$

vertex

$)$

:

$$ if to

$\_$

vertex not in self.adjacency

$\_$

list:

$$ return

$[]$

$$ # No such vertex

$$ to

$\_$

vertex

$\_$

obj

$=$

$$self$.$get

$\_$

vertex

$($

to

$\_$

vertex

$)$

$$ edges

$\_$

to

$=$

$[]$

$$ for from

$\_$

vertex in self.adjacency

$\_$

list:

$$ if to

$\_$

vertex in self.adjacency

$\_$

list

$[$

from

$\_$

vertex

$]$

:

$$ edges

$\_$

to

$.$

append

$($

Edge

$($

self

$.$

get

$\_$

vertex

$($

from

$\_$

vertex

$)$

$,$

$$to

$\_$

vertex

$\_$

obj

$))$

$$ return edges

$\_$

to

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

$$ def get

$\_$

vertex

$($

self

$,$

$$vertex

$\_$

label

$)$

:

$$ for vertex in self.vertices:

$$ if vertex.get

$\_$

label

$()$

$=$

$=$

$$vertex

$\_$

label:

$$ return vertex

$$ return None

$$ # Returns True if the graph has an edge from from

$\_$

vertex to to

$\_$

vertex

$$ def has

$\_$

edge

$($

self

$,$

$$from

$\_$

vertex, to

$\_$

vertex

$)$

:

$$ if from

$\_$

vertex not in self.adjacency

$\_$

list or to

$\_$

vertex not in self.adjacency

$\_$

list:

$$ return False

$$ return to

$\_$

vertex in self.adjacency

$\_$

list

$[$

from

$\_$

vertex

$]$

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

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.

$$ # Otherwise the new edge is added and True is returned.

$$ def add

$\_$

directed

$\_$

edge

$($

self

$,$

$$from

$\_$

vertex, to

$\_$

vertex

$)$

:

$$ # Your code here

$($

remove placeholder line below

$)$

$$ pass

$$ # Returns a list of edges with the specified from

$\_$

vertex.

$$ def get

$\_$

edges

$\_$

from

$($

self

$,$

$$from

$\_$

vertex

$)$

:

$$ # Your code here

$($

remove placeholder line below

$)$

$$ pass

$$ # Returns a list of edges with the specified to

$\_$

vertex.

$$ def get

$\_$

edges

$\_$

to

$($

self

$,$

$$to

$\_$

vertex

$)$

:

$$ # Your code here

$($

remove placeholder line below

$)$

$$ pass

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

$$ def get

$\_$

vertex

$($

self

$,$

$$vertex

$\_$

label

$)$

:

$$ # Your code here

$($

remove placeholder line below

$)$

$$ pass

$$ # Returns True if self graph has an edge from from

$\_$

vertex to to

$\_$

vertex

$$ def has

$\_$

edge

$($

self

$,$

$$from

$\_$

vertex, to

$\_$

vertex

$)$

:

$$ # Your code here

$($

remove placeholder line below

$)$

$$ pass

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

$$ this code is outputting: AdjacencyListGraph:

PASS: add

$\_$

vertex

$("$

A

$")$

$$returned a vertex

PASS: add

$\_$

vertex

$("$

B

$")$

$$returned a vertex

PASS: get

$\_$

vertex

$("$

C

$")$

$$returned None

PASS: get

$\_$

vertex

$("$

A

$")$

$$returned a vertex with a correct label

PASS: get

$\_$

vertex

$("$

B

$")$

$$returned a vertex with a correct label

PASS: get

$\_$

vertex

$("$

E

$")$ FAIL: ADD from $"$B$"$ to "Cplease modify adjacencylist.graph for it to pass these test. here isdirctggraph.py: