A graph is an abstract mathematical construct that is used for modeling a real-world problem by dividing the problem into a set of connected nodes.

• For instance, a subway map can be thought of as a graph representing a transportation network. Each of the dots represents a station, and each of the lines  represents a route between two stations.
• Graphs help us abstractly think about a problem, also let us apply several well-understood and performant search and optimization techniques.
  

Building a graph framework

• The weighted classes in our data model will be subclasses of their unweighted counterparts.
• An Edge is defined as a connection between two vertices, each of which is represented by an integer index.
• The Graph class focuses on the essential role of a graph: associating vertices with edges.
  
  • The _vertices list is the heart of a Graph .
    
    • Each vertex will be stored in the list, but we will later refer to them by their integer index in the list. The vertex itself may be a complex data type, but its index will always be an int , which is easy to work with.
    • On another level, by putting this index between graph algorithms and the _vertices array, it allows us to have two vertices that are equal in the same graph. (Imagine a graph with a country’s cities as vertices, where the country has more than one city named “Springfield.”) Even though they are the same, they will have different integer indexes.
    • There are many ways to implement a graph data structure, but the two most common are to use a vertex matrix or adjacency lists.
      
      • In a vertex matrix, each cell of the matrix represents the intersection of two vertices in the graph, and the value of that cell indicates the connection (or lack thereof) between them.
      • In adjacency lists, every vertex has a list of vertices that it is connected to - Our specific representation uses a list of lists of edges, so for every vertex there is a list of edges via which the vertex is connected to other vertices. _ edges is this list of lists.
        
    • the list _vertices is a list of elements of type V , which can be any Python class. So we have vertices of type V that are stored in the _vertices list.
    • _edges[index] is the adjacency list, the list of edges through which the vertex in question is connected to other vertices
      

NOTE: new feature in Python 3.7: dataclasses. A class marked with the @dataclass decorator saves some tedium by automatically creating an __init__() method that instantiates instance variables for any variables declared with type annotations in the class’s body. Dataclasses can also automatically create other special methods for a class. Which special methods are automatically created is configurable via the decorator.

Real-world applications
A huge amount of our world can be represented using graphs. You have seen in this chapter how effective they are for working with transportation networks, but many other kinds of networks have the same essential optimization problems: telephone
networks, computer networks, utility networks (electricity, plumbing, and so on). As a result, graph algorithms are essential for efficiency in the telecommunications, shipping, transportation, and utility industries.

Retailers must handle complex distribution problems. Stores and warehouses can be thought of as vertices and the distances between them as edges. The algorithms are the same. The internet itself is a giant graph, with each connected device a vertex and each wired or wireless connection being an edge. Whether a business is saving fuel or wire, minimum spanning tree and shortest path problem-solving are useful for more than just games. Some of the world’s most famous brands became successful by optimizing graph problems: think of Walmart building out an efficient distribution network, Google indexing the web (a giant graph), and FedEx finding the right set of hubs to connect the world’s addresses.

Some obvious applications of graph algorithms are social networks and map applications. In a social network, people are vertices, and connections (friendships on Facebook, for instance) are edges. In fact, one of Facebook’s most prominent developer tools is known as the Graph API (https://developers.facebook.com/docs/graph-api). In map applications like Apple Maps and Google Maps, graph algorithms are used to provide directions and calculate trip times.

Several popular video games also make explicit use of graph algorithms. Mini-Metro and Ticket to Ride are two examples of games that closely mimic the problems solved in this chapter.

Exercises

• Add support to the graph framework for removing edges and vertices.
• Add support to the graph framework for directed graphs (digraphs).
• Use this chapter’s graph framework to prove or disprove the classic Bridges of Königsberg problem, as described on Wikipedia: https://en.wikipedia.org/wiki/ Seven_Bridges_of_Königsberg.