python implementation in this sectionwe provide an implementation of the graph adt our implementation will support directed or undirected graphsbut for ease of explanationwe first describe it in the context of an undirected graph we use variant of the adjacency map representation for each vertex vwe use python dictionary to represent the secondary incidence map (vhoweverwe do not explicitly maintain lists and eas originally described in the edge list representation the list is replaced by top-level dictionary that maps each vertex to its incidence map ( )note that we can iterate through all vertices by generating the set of keys for dictionary by using such dictionary to map vertices to the secondary incidence mapswe need not maintain references to those incidence maps as part of the vertex structures alsoa vertex does not need to explicitly maintain reference to its position in dbecause it can be determined in ( expected time this greatly simplifies our implementation howevera consequence of our design is that some of the worst-case running time bounds for the graph adt operationsgiven in table become expected bounds rather than maintain list ewe are content with taking the union of the edges found in the various incidence mapstechnicallythis runs in ( mtime rather than strictly (mtimeas the dictionary has keyseven if some incidence maps are empty our implementation of the graph adt is given in code fragments through classes vertex and edgegiven in code fragment are rather simpleand can be nested within the more complex graph class note that we define the hash method for both vertex and edge so that those instances can be used as keys in python' hash-based sets and dictionaries the rest of the graph class is given in code fragments and graphs are undirected by defaultbut can be declared as directed with an optional parameter to the constructor internallywe manage the directed case by having two different top-level dictionary instancesoutgoing and incomingsuch that outgoing[vmaps to another dictionary representing iout ( )and incoming[vmaps to representation of iin (vin order to unify our treatment of directed and undirected graphswe continue to use the outgoing and incoming identifiers in the undirected caseyet as aliases to the same dictionary for conveniencewe define utility named is directed to allow us to distinguish between the two cases for methods degree and incident edgeswhich each accept an optional parameter to differentiate between the outgoing and incoming orientationswe choose the appropriate map before proceeding for method insert vertexwe always initialize outgoing[vto an empty dictionary for new vertex in the directed casewe independently initialize incoming[vas well for the undirected casethat step is unnecessary as outgoing and incoming are aliases we leave the implementations of methods remove vertex and remove edge as exercises ( - and -