November 3, 2022TUTORIAL · MACHINE-LEARNING

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 mathimport 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: boolclass Edge(pw.Schema): u: Vertex v: 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_int(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.apply_with_type( lambda x: 0 if x else math.inf, float, vertices.is_source ) ) 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 graphvertices = pw.debug.table_from_markdown( """ | key | is_source1 | 1 | True2 | 2 | False3 | 3 | False4 | 4 | False5 | 5 | False6 | 6 | False7 | 7 | False""").with_id_from(pw.this.key)edges = pw.debug.table_from_markdown( """ | u | v | dist11 | 1 | 2 | 10012 | 1 | 3 | 20013 | 1 | 4 | 30014 | 3 | 5 | 10015 | 3 | 6 | 50016 | 5 | 6 | 10017 | 6 | 3 | -50""").update_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))`

```
| key | dist_from_source
^04VMVCM... | 1 | 0
^GFBMT58... | 2 | 100
^TT1GT7R... | 3 | 200
^86W6AGV... | 4 | 300
^W788BTV... | 5 | 300
^CR88CHY... | 6 | 400
^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:

- Define I/O data types
- Define transformations on tables
- Iterate the transformation until a fixed point is reached
- usually transforms the data by a simple one-liner.
- for example
`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.

Related articles

- developers / showcases / lshPart 1: Realtime classification in Pathway with Nearest NeighborsOlivier Ruas2022-10-25machine-learning
- developers / showcases / lshPart 2: Realtime classification in Pathway with Nearest NeighborsOlivier Ruas2022-10-26machine-learning
- developers / showcasesRealtime Twitter Analysis App with PathwayMateusz Lewandowski2022-10-31machine-learningshowcase

Pathway Team

Table of Contents

Table of Contents