A graph models relationships as vertices and edges: G = (V, E), where V contains distinct entities and E connects a source vertex to a destination vertex. Unlike a drawing, an abstract graph does not require geometric placement. section 14.1 section 15.1.1
Choose the graph variant that matches the relationships being modeled:
- Use a simple graph when loops and multiple edges between the same pair of vertices are disallowed. section 14.1
- Use directed edges when travel or influence has a source-to-destination direction; represent a two-way relationship with two directed edges. section 14.1 section 14.3.1
- Use a weighted graph, also called a network, when each edge carries a numeric cost such as distance. section 14.1
- Represent the structure programmatically with vertex and edge objects plus an adjacency list mapping each vertex to its outgoing edges. section 14.1.3
Finding a delivery route
Map each road intersection to a vertex and each permitted road movement to a directed edge. With equal-sized blocks, route length can be measured by counting traversed blocks; one-way streets create detours. This model supports searching for minimum-distance routes, including Dijkstra’s and A* algorithms. section 14.3.1 section 14.0
Listing 14.1 The Graph class
class Vertex
#type string
label
class Edge
#type Vertex
source
#type Vertex
dest
#type double
weight
#type string
label
class Graph
#type List[Vertices]
vertices
#type HashTable[Vertex->List[Edge]]
adjacencyList
function Graph()
adjacencyList ← new HashTable()
function addVertex(v)
throw-if v in vertices
vertices.insert(v) #1
adjacencyList[v] ← [] #2
function addEdge(v, u, weight=0, label=””)
throw-if not (v in vertices and u in vertices)
if areAdjacent(v, u) then #3
removeEdge(v, u) #4
adjacencyList[v].insert(new Edge(v, u, weight, label)) #5
function areAdjacent(v, u)
throw-if not (v in vertices and u in vertices)
for e in adjacencyList[v] do #6
if e.dest == u then #7
return true
return false
Inspect the Graph class pseudocode to see vertices, weighted labeled edges, adjacency lists, and basic validation operations assembled into an implementation. section 14.1.3
Figure 14.10 Building a graph on the map in figure 14.8. We added a vertex to each road intersection (some vertices are, however, omitted for better readability) and edges connect adjacent intersections connected by a one-way street (two-way streets are modeled with a couple of edges).
Follow the translation from a street map to a directed graph, including vertices at intersections and edges for one-way or two-way streets. section 14.3.1
A graph can also be drawn, but the drawing adds placement and intersection constraints. A planar graph is one that has a planar embedding; not every abstract graph is planar. section 15.1.1
