Ambiguity in Graph section

[acerekovic]

There is variety of ways to represent graphs, and complexity of graph operations depends on graph representation. However, I am curious how you estimated complexity of edge insertion, which is the same for all graph representations (add Edge, O(1)). What kind of graph implementation you assume hereby? Do you assume that you have a hash_map for vertices in adjacency list, which makes it O(1)? If so, it would be good to update the information.

To depict the issue, one can imagine very simple representation of a graph with vertices that contain strings. In c++ we can represent adjacency list using STL collections, such as:
std::mapstd::string,std::setstd::string adjacency_list;
Now, method to add edge, i.e. addEdge("baby","carrot"), first has to look up for position of the vertex ("baby") in the adjacency list, which is O(logn) in this case.