Introducing: Floyd-Warshall CSV Generator

9 Jun 2024

I built a little Python script called the Floyd-Warshall CSV Generator. It takes a CSV of graph edges as input, and generates a CSV of the edges that are the shortest paths between all pairs of vertices.

The script is a simple wrapper of the SciPy floyd_warshall function, which in turn implements the Floyd-Warshall Algorithm. Hope you find it useful for all your directed (or undirected) weighted graph needs.

Given an input CSV of the following graph edges:

point_a,point_b,cost
a,b,5
b,c,8
c,d,23
d,e,6

When the script is called as follows:

floyd-warshall-csv-generator \
  /path/to/input_data.csv \
  --vertex-i-column-name point_a \
  --vertex-j-column-name point_b \
  --weight-column-name cost \
  --no-directed \
  --max-weight 35

It generates an output CSV that looks like this:

point_a,point_b,cost
a,b,5.0
a,c,13.0
b,c,8.0
b,d,31.0
c,d,23.0
c,e,29.0
d,e,6.0

That is, it generates all the possible (indirect) paths from one point to all other points, based on the (direct) paths that are already known, with duplicate (undirected) paths filtered out, and with paths whose cost is more than max-weight filtered out.

I wrote this script in order to generate the "all edges" data that's shown in the World Locality Transit Graph, which I'll also be blogging about real soon. Let me know if you put this script to any other interesting uses!