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.

4.1 Mutating a graph

4.1.1 Creating vertices and edges

4.1.2 Removing data from our graph

4.1.3 Updating a graph

4.1.4 Extending our graph

4.2 Paths

4.2.1 Cycles in graphs

4.2.2 Finding the simple path

4.3 Traversing and filtering edges

4.3.1 Introducing the E and V steps for traversing edges

4.3.2 Filtering with edge properties

4.3.3 Include edges in path results

4.3.4 Performant edge counts and denormalization

Summary