paths
Given an adjacency list of sources, targets, and weights that results in a graph, this directive produces a list of all possible paths in tabular format. It requires the sub-directive path operation.
pebblestream:paths(source, target, weight)
pebblestream:paths-operation(operator, header)
Use the paths directive to transform graph relationships into a tabular format more conducive to spreadsheet processing. Like other transformative directives, the "from" directive is required to work.
Path operations
The paths directive is a powerful feature that facilitates applying powerful graph traversal operations. Here is the complete list of all the path operations you can use.
path
| path operation | description |
|---|---|
| + | The "+" path operation adds all the weights for each discovered path. |
| - | Like the "+" path operation, the "-" path operation subtracts all the weights for each discovered path. |
| * | The "*" path operation multiplies all the weights for each discovered path. |
| / | Like the "*" path operation, the "/" path operation divides all the weights for each discovered path. |
| first | The "first" path operation will return the first node on each discovered path. |
| second | The "second" path operation will return the second node on each discovered path. |
| penultimate | The "penultimate" path operation will return the node just before the last node on each discovered path. |
| last | The "last" path operation will return the last node on each discovered path. |
| length | The "length" path operation will return a path's total number of hops (edges). |
| min | The "min" path operator will return the minimum weight on each discovered path. |
| max | Like the "min", this path operator will return the maximum weight on each discovered path. |
| avg | The "avg" path operator will compute the average of all weights of each discovered path. |
Use Case
Let's work through an example. Consider the worksheet Stations detailing train station connections.
| start | end | distance |
|---|---|---|
| Washington DC | Baltimore | 35 |
| Baltimore | Philadelphia | 110 |
| Philadelphia | Newark | 150 |
| Newark | New York | 25 |
Let's use the paths and paths-operation directives to extract information from the Stations worksheet into the Trips worksheet.
First, let's detail every possible trip from every station going north. And let's include the trip's total distance. Here is the PebbleScript for that.
pebblestream:from("Stations")
pebblestream:paths("start", "end", "distance")
pebblestream:paths-operation("+", "trip distance")
The paths directive will scan the Stations worksheet and find all possible paths from one city to another. For each path found, the paths-operation directive will repeatedly apply an operation to each of the values associated with each step in the path. In this case, we are using the "+" operation to add up all the distances between each station on the trip. We label this value "trip distance." The following worksheet shows the result.
| start | trip distance | end |
|---|---|---|
| Washington DC | 35 | Baltimore |
| Washington DC | 145 | Philadelphia |
| Washington DC | 295 | Newark |
| Washington DC | 320 | New York City |
| Baltimore | 110 | Philadelphia |
| Baltimore | 260 | Newark |
| Baltimore | 285 | New York City |
| Philadelphia | 150 | Newark |
| Philadelphia | 175 | New York City |
| Newark | 25 | New York City |
This result shows that the longest trip is from Washington, DC, to New York City, and the shortest is from Newark to New York City.
Multiple path operations can be applied at once to a paths directive.
Use the paths operation "length" to count the number of stops on each trip. Add this path operation to show the stops.
pebblestream:from("Stations")
pebblestream:paths("start", "end", "distance")
pebblestream:paths-operation("+", "trip distance")
pebblestream:paths-operation("length", "stops")
which results in the new column "stops" added to the worksheet.
| start | trip distance | stops | end |
|---|---|---|---|
| Washington DC | 35 | 1 | Baltimore |
| Washington DC | 145 | 2 | Philadelphia |
| Washington DC | 295 | 3 | Newark |
| Washington DC | 320 | 4 | New York City |
| Baltimore | 110 | 1 | Philadelphia |
| Baltimore | 260 | 2 | Newark |
| Baltimore | 285 | 3 | New York City |
| Philadelphia | 150 | 1 | Newark |
| Philadelphia | 175 | 2 | New York City |
| Newark | 25 | 1 | New York City |
Use the "min" paths operation to find the smallest hop on each path. Once again, add the new paths-operation to achieve this.
pebblestream:from("Stations")
pebblestream:paths("start", "end", "distance")
pebblestream:paths-operation("+", "trip distance")
pebblestream:paths-operation("length", "stops")
pebblestream:paths-operation("min", "shortest hop")
This results in the worksheet below
| start | trip distance | shortest hop | stops | end |
|---|---|---|---|---|
| Washington DC | 35 | 35 | 1 | Baltimore |
| Washington DC | 145 | 35 | 2 | Philadelphia |
| Washington DC | 295 | 35 | 3 | Newark |
| Washington DC | 320 | 25 | 4 | New York City |
| Baltimore | 110 | 110 | 1 | Philadelphia |
| Baltimore | 260 | 110 | 2 | Newark |
| Baltimore | 285 | 25 | 3 | New York City |
| Philadelphia | 150 | 150 | 1 | Newark |
| Philadelphia | 175 | 25 | 2 | New York City |
| Newark | 25 | 25 | 1 | New York City |
Let's add a column to find the stop just before the final stop in the trip. We will use the "penultimate" paths operation. Let's remove the "shortest hop" column for clarity.
pebblestream:from("Stations")
pebblestream:paths("start", "end", "distance")
pebblestream:paths-operation("+", "trip distance")
pebblestream:paths-operation("length", "stops")
pebblestream:paths-operation("penultimate", "get ready!")
This results in the following worksheet, with the "get ready!" column showing the penultimate stop on a trip.
| start | trip distance | stops | get ready! | end |
|---|---|---|---|---|
| Washington DC | 35 | 1 | Washington DC | Baltimore |
| Washington DC | 145 | 2 | Baltimore | Philadelphia |
| Washington DC | 295 | 3 | Philadelphia | Newark |
| Washington DC | 320 | 4 | Newark | New York City |
| Baltimore | 110 | 1 | Baltimore | Philadelphia |
| Baltimore | 260 | 2 | Philadelphia | Newark |
| Baltimore | 285 | 3 | Newark | New York City |
| Philadelphia | 150 | 1 | Philadelphia | Newark |
| Philadelphia | 175 | 2 | Newark | New York City |
| Newark | 25 | 1 | Newark | New York City |
Finally, use the paths operation "id" to label each path with a unique number. We will put this in the "path id" column.
pebblestream:from("Stations")
pebblestream:paths("start", "end", "distance")
pebblestream:paths-operation("+", "trip distance")
pebblestream:paths-operation("length", "stops")
pebblestream:paths-operation("penultimate", "get ready!")
pebblestream:paths:operation("id", "path id")
This results in the following worksheet.
| path id | start | trip distance | stops | get ready! | end |
|---|---|---|---|---|---|
| 0 | Washington DC | 35 | 1 | Washington DC | Baltimore |
| 1 | Washington DC | 145 | 2 | Baltimore | Philadelphia |
| 2 | Washington DC | 295 | 3 | Philadelphia | Newark |
| 3 | Washington DC | 320 | 4 | Newark | New York City |
| 4 | Baltimore | 110 | 1 | Baltimore | Philadelphia |
| 5 | Baltimore | 260 | 2 | Philadelphia | Newark |
| 6 | Baltimore | 285 | 3 | Newark | New York City |
| 7 | Philadelphia | 150 | 1 | Philadelphia | Newark |
| 8 | Philadelphia | 175 | 2 | Newark | New York City |
| 9 | Newark | 25 | 1 | Newark | New York City |
The paths directives will report an error if the provided sources and targets result in a graph with cycles.
Updated 7 days ago