concept graph in category python

appears as: graph, graphs, The graph, A graph, A graph, graph
Math for Programmers: 3D graphics, machine learning, and simulations with Python

This is an excerpt from Manning's book Math for Programmers: 3D graphics, machine learning, and simulations with Python.

Stocks are types of financial assets that represent ownership stakes in companies. When the market perceives a company is doing well, its stock price goes up: buying the stock becomes more costly and selling it becomes more rewarding. Stock prices change erratically and in real time. Figure 1.1 shows how a graph of a stock price over a day of trading might look.

Figure 11.16: Three pictures of a scalar field: a heatmap, a graph, and a contour map
Classic Computer Science Problems in Python

This is an excerpt from Manning's book Classic Computer Science Problems in Python.

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. We call each of the nodes a vertex and each of the connections an edge. 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. In graph terminology, we would call the stations “vertices” and the routes “edges.”

The Graph class focuses on the essential role of a graph: associating vertices with edges. Again, we want to let the actual types of the vertices be whatever the user of the framework desires. This lets the framework be used for a wide range of problems without needing to make intermediate data structures that glue everything together. For example, in a graph like the one for Hyperloop routes, we might define the type of the vertices to be str, because we would use strings like “New York” and “Los Angeles” as the vertices. Let’s begin the Graph class.

Listing 4.2. graph.py
from typing import TypeVar, Generic, List, Optional
from edge import Edge

V = TypeVar('V') # type of the vertices in the graph


class Graph(Generic[V]):
    def __init__(self, vertices: List[V] = []) -> None:
        self._vertices: List[V] = vertices
        self._edges: List[List[Edge]] = [[] for _ in vertices]


!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":4}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":4}],[{\"line\":0,\"ch\":12},{\"line\":0,\"ch\":18}],[{\"line\":1,\"ch\":10},{\"line\":1,\"ch\":16}],[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":4}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":4}],[{\"line\":0,\"ch\":12},{\"line\":0,\"ch\":18}],[{\"line\":1,\"ch\":10},{\"line\":1,\"ch\":16}],[{\"line\":3,\"ch\":12},{\"line\":3,\"ch\":15}],[{\"line\":6,\"ch\":0},{\"line\":6,\"ch\":5}],[{\"line\":7,\"ch\":4},{\"line\":7,\"ch\":7}],[{\"line\":7,\"ch\":50},{\"line\":7,\"ch\":54}],[{\"line\":9,\"ch\":44},{\"line\":9,\"ch\":52}]]"}
!@%STYLE%@!

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. Our graph data structure uses adjacency lists. In this graph representation, 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.

A tree is a special kind of graph that has one, and only one, path between any two vertices. This implies that there are no cycles in a tree (which is sometimes called acyclic). A cycle can be thought of as a loop: if it is possible to traverse a graph from a starting vertex, never repeat any edges, and get back to the same starting vertex, then it has a cycle. Any graph that is not a tree can become a tree by pruning edges. Figure 4.6 illustrates pruning an edge to turn a graph into a tree.

Figure 4.6. In the left graph, a cycle exists between vertices B, C, and D, so it is not a tree. In the right graph, the edge connecting C and D has been pruned, so the graph is a tree.

A connected graph is a graph that has some way of getting from any vertex to any other vertex. (All of the graphs we are looking at in this chapter are connected.) A spanning tree is a tree that connects every vertex in a graph. A minimum spanning tree is a tree that connects every vertex in a weighted graph with the minimum total weight (compared to other spanning trees). For every weighted graph, it is possible to efficiently find its minimum spanning tree.

4.1. A map as a graph

In this chapter, we won’t work with a graph of subway stations, but instead cities of the United States and potential routes between them. Figure 4.1 is a map of the continental United States and the 15 largest metropolitan statistical areas (MSAs) in the country, as estimated by the U.S. Census Bureau.[1]