Max Flow with Gremlin and Transactions
Max De Marzi writes:
The maximum flow problem was formulated by T.E. Harris as follows:
Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, a nd a maximal flow from one given city to the other.
Back in the mid 1950s the US Military had an interest in finding out how much capacity the Soviet railway network had to move cargo from the Western Soviet Union to Eastern Europe. This lead to the Maximum Flow problem and the Ford–Fulkerson algorithm to solve it.
If you’ve been reading the Neo4j Gremlin Plugin documentation, you’ll remember it has a section on Flow algorithms with Gremlin. Let’s add a couple of things and bring this example to life.
If that sounds like an out-dated Cold War problem, consider Max’s conclusion:
The max flow and related problems manifest in many ways. Water or sewage through underground pipes, passengers on a subway system, data through a network (the internet is just a series of tubes!), roads and highway planning, airline routes, even determining which sports teams have been eliminated from the playoffs.
What else can be modeled as max flow or related problems? Drug/weapons smuggling? Oil/gas/electricity transport? Others?