4 Pathfinding traversals and mutating graphs
This chapter covers
- Writing traversals to add, modify, and delete vertices, edges, and properties
- Finding the paths that connect two vertices
- Refining pathfinding traversals using edges and edge properties
Getting lost has itself become a “lost art” since the advent of GPS devices and smartphones. Long gone are the days of stopping at a local service station to ask for directions. But while we may fear that our direction-finding skills are atrophying in the real world, in the data domain, graph’s pathfinding algorithms come to the rescue—or maybe these precipitated the digitization of this real-world skill.
We emphasized in the last chapter how critical it is to know your location in the graph at all times in the traversal-writing process. In this chapter, we take that concept a step further with pathfinding algorithms. A path is a listing of the vertices and edges visited from the beginning vertex to the ending vertex of a traversal. Paths tell us not only that two vertices are connected, but also show us all of the intermediate elements in between. Paths are the turn-by-turn directions between two points in a graph. But because there aren’t a lot of pathfinding options in a graph with four vertices, we’ll begin by mutating our graph to add some more data. Mutating simply means changing the graph by adding, modifying, or deleting vertices, edges, and/or properties.