This article explains step-by-step how the Bellman–Ford algorithm may be implemented in Pathway.
The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all the other vertices in a weighted graph. A weighted graph is composed of a set of points, called vertices, which are connected via edges. Each edge is associated to a value, called either weight or distance. For instance, the set of all the cities and the roads which connect them form such a graph. In that example, the Bellman-Ford algorithm would help to find the fastest way, in terms of distance, to go from a given city to another.
This article is also a perfect place to familiarize yourself with several constructs used in Pathway.
First things first - imports 🙂
import math
import pathway as pw
The input is a weighted graph so it is natural to split representation of the data into two parts: Vertices and Edges. Their schemas:
class Vertex(pw.Schema):
is_source: bool
class Edge(pw.Schema):
u: pw.Pointer[Vertex]
v: pw.Pointer[Vertex]
dist: int
These schemas have a natural interpretation. You can think of the Edge
schema as of
a blueprint of a table that has 3 columns: u
, v
(foreign keys) and dist
.
The output schema:
class DistFromSource(pw.Schema):
dist_from_source: int
Note: The schemas inherit from pw.Schema
special class.
Note: You might wonder why output schema has only one column dist_from_source
.
Actually, you can join schemas together to create a new one. And so, the output schema
is Vertex + DistFromSource
. (Look for that type annotation later in the code.)
The Bellman-Ford algorithm performs some number of relaxations until it reaches a fixed point.
Each node checks if a path via it would make any so-far-optimal path to some other node shorter.
def bellman_ford_step(
vertices_dist: pw.Table[DistFromSource], edges: pw.Table[Edge]
) -> pw.Table[DistFromSource]:
relaxed_edges = edges + edges.select(
dist_from_source=vertices_dist.ix(edges.u).dist_from_source + edges.dist
)
vertices_dist = vertices_dist.update_rows(
relaxed_edges.groupby(id=relaxed_edges.v).reduce(
dist_from_source=pw.reducers.min(relaxed_edges.dist_from_source),
)
)
return vertices_dist
The relaxations are iterated until a fixed point is reached. In this case, reaching a fixed point means that no new (shorter) path was found in the last iteration.
def bellman_ford(vertices: pw.Table[Vertex], edges: pw.Table[Edge]):
vertices_dist: pw.Table[DistFromSource] = vertices.select(
dist_from_source=pw.if_else(vertices.is_source, 0.0, math.inf)
)
fixed_point = pw.iterate(
lambda iterated, edges: dict(
iterated=bellman_ford_step(vertices_dist=iterated, edges=edges)
),
# The `pw.iterate_universe` stanza informs iterate that `vertices_dist` grows with each loop iteration. Without it, the system assumes that iterations don't change the set of indices of a table.
iterated=pw.iterate_universe(vertices_dist),
edges=edges,
).iterated
return fixed_point.join(vertices, fixed_point.id == vertices.id).select(
vertices.key, fixed_point.dist_from_source
)
Now, let's see the code in action. The following test case runs Bellman-Ford algorithm on a graph depicted below.
# a directed graph
vertices = pw.debug.table_from_markdown(
"""
| key | is_source
1 | 1 | True
2 | 2 | False
3 | 3 | False
4 | 4 | False
5 | 5 | False
6 | 6 | False
7 | 7 | False
"""
).with_id_from(pw.this.key)
edges = pw.debug.table_from_markdown(
"""
| u | v | dist
11 | 1 | 2 | 100
12 | 1 | 3 | 200
13 | 1 | 4 | 300
14 | 3 | 5 | 100
15 | 3 | 6 | 500
16 | 5 | 6 | 100
17 | 6 | 3 | -50
"""
).with_columns(
u=vertices.pointer_from(pw.this.u),
v=vertices.pointer_from(pw.this.v),
)
Pathway automatically reindexes the tables, so we need a key column of the vertices
table and we need ask Pathway to reindex the table using those.
In practice, Pathway uses pointers so the keys are automatically converted into pointers.
For the edges, we have to convert the keys into their references in order to be able to use vertices_dist.ix(edges.u)
as ix
only works with pointers.
pw.debug.compute_and_print(bellman_ford(vertices, edges))
[2023-12-08T16:29:49]:INFO:Preparing Pathway computation
| key | dist_from_source
^04VMVCM... | 1 | 0.0
^GFBMT58... | 2 | 100.0
^TT1GT7R... | 3 | 200.0
^86W6AGV... | 4 | 300.0
^W788BTV... | 5 | 300.0
^CR88CHY... | 6 | 400.0
^YCS0SGG... | 7 | inf
That was a simple introduction to writing code and tests in Pathway.
Feel free to take this code and experiment with it 🙂 Do you see any possibility to improve the code? (What happens when there is a negative cycle in the graph?)
The code above follows a pattern that is quite frequent when working with Pathway:
iterate(lambda foo, bar: {foo=fn(foo, bar), bar=bar}, foo=input_table_1, bar=input_table2).foo
Note: It is also possible to define transformations from the perspective of a row and not of a table. Curious? Take a look at the transformer class tutorial or some of our other cookbooks, like this one on Pagerank.
Pathway Team