Solve the Widest Path Problem in Cypher

widest_path.adoc

Solve the Widest Path Problem in Cypher

The widest path problem has a number of applications in many domains, including networking, shipping, and emergency response. Assuming the relationships between nodes in a graph are weighted by a capacity of some sort, the widest path problem involves finding the path between two nodes that maximizes the minimum capacity in the path.

Below, each node is a router in a city and the relationships between the routers have a bandwidth property indicating the bandwidth capacity of the two routers' connection. The direction of the connection is arbitrary.

CREATE (r1:Router {name:'Maldon'}),
	   (r2:Router {name:'Feering'}),
	   (r3:Router {name:'Tiptree'}),
	   (r4:Router {name:'Clacton'}),
	   (r5:Router {name:'Blaxhall'}),
	   (r6:Router {name:'Harwich'}),
	   (r7:Router {name:'Dunwich'}),

	   (r1)-[:CONNECTED_TO {bandwidth:11}]->(r2),
	   (r1)-[:CONNECTED_TO {bandwidth:8}]->(r3),
	   (r1)-[:CONNECTED_TO {bandwidth:40}]->(r4),
	   (r2)-[:CONNECTED_TO {bandwidth:3}]->(r3),
	   (r2)-[:CONNECTED_TO {bandwidth:46}]->(r5),
	   (r3)-[:CONNECTED_TO {bandwidth:29}]->(r4),
	   (r3)-[:CONNECTED_TO {bandwidth:31}]->(r6),
	   (r4)-[:CONNECTED_TO {bandwidth:17}]->(r6),
	   (r5)-[:CONNECTED_TO {bandwidth:40}]->(r6),
	   (r5)-[:CONNECTED_TO {bandwidth:15}]->(r7),
	   (r6)-[:CONNECTED_TO {bandwidth:53}]->(r7)

Finding the widest path between any two routers is easy in Cypher. And obviously, I’ll make use of our awesome new function UNWIND. The following query finds the widest path between Maldon and Feering.

MATCH p = (r1:Router {name:'Maldon'})-[:CONNECTED_TO*]-(r2:Router {name:'Feering'})
WITH p, EXTRACT(c IN RELATIONSHIPS(p) | c.bandwidth) AS bandwidths
UNWIND(bandwidths) AS b
WITH p, MIN(b) AS Bandwidth
ORDER BY Bandwidth DESC
RETURN NODES(p) AS `Widest Path`, Bandwidth
LIMIT 1

The path given above maximizes the bandwidth capacity between Maldon and Feering at 29 by avoiding low-bandwidth connections. The query is pretty straight-forward:

Find all paths of any length between Maldon and Feering.

MATCH p = (r1:Router {name:'Maldon'})-[:CONNECTED_TO*]-(r2:Router {name:'Feering'})

For each path, collect the bandwidths along the path.

WITH p, EXTRACT(c IN RELATIONSHIPS(p) | c.bandwidth) AS bandwidths

Unwind the collection of bandwidths so that you can find the minimum with MIN().

UNWIND(bandwidths) AS b

For each path, find its minimum bandwidth.

WITH p, MIN(b) AS Bandwidth

Order the paths by their minimum bandwidth descending and return the top path, which is the path with the maximum minimum bandwidth.

ORDER BY Bandwidth DESC
RETURN NODES(p) AS `Widest Path`, Bandwidth
LIMIT 1