figure contains implementations of the classes digraph and graph one important decision is the choice of data structure used to represent digraph one common representation is an adjacency matrixwhere is the number of nodes in the graph each cell of the matrix contains information ( weightsabout the edges connecting the pair of nodes if the edges are unweightedeach entry is true if and only if there is an edge from to another common representation is an adjacency listwhich we use here class digraph has two instance variables the variable nodes is python list containing the names of the nodes in the digraph the connectivity of the nodes is represented using an adjacency list implemented as dictionary the variable edges is dictionary that maps each node in the digraph to list of the children of that node class graph is subclass of digraph it inherits all of the methods of digraph except addedgewhich it overrides (this is not the most space-efficient way to implement graphsince it stores each edge twiceonce for each direction in the digraph but it has the virtue of simplicity class digraph(object)#nodes is list of the nodes in the graph #edges is dict mapping each node to list of its children def __init__(self)self nodes [self edges {def addnode(selfnode)if node in self nodesraise valueerror('duplicate node'elseself nodes append(nodeself edges[node[def addedge(selfedge)src edge getsource(dest edge getdestination(if not(src in self nodes and dest in self nodes)raise valueerror('node not in graph'self edges[srcappend(destdef childrenof(selfnode)return self edges[nodedef hasnode(selfnode)return node in self nodes def __str__(self)result 'for src in self nodesfor dest in self edges[src]result result src getname('->'dest getname('\nreturn result[:- #omit final newline class graph(digraph)def addedge(selfedge)digraph addedge(selfedgerev edge(edge getdestination()edge getsource()digraph addedge(selfrevfigure classes graph and digraph