Using Gremlin and Transaction to Solve the Problem of Maximum Flow
Join the DZone community and get the full member experience.
Join For Freethe 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, and 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.
we’re going to be modeling a simple railway system that needs to transport cargo from california to illinois. a couple of direct routes exist, and additionally a route going through texas. first step is to create our graph:
def create_graph neo = neography::rest.new graph_exists = neo.get_node_properties(1) return if graph_exists && graph_exists['name'] states = [{:name => "california", :coordinates => [-119.355165,35.458606]}, {:name => "illinois", :coordinates => [ -88.380238,41.278216]}, {:name => "texas", :coordinates => [ -97.388631,30.943149]}] commands = states.map{ |n| [:create_node, n]} states.each_index.map do |n| commands << [:add_node_to_index, "states_index", "name", states[n][:name], "{#{n}}"] end commands << [:create_relationship, "connected", "{#{0}}", "{#{1}}", {:capacity => 1}] commands << [:create_relationship, "connected", "{#{0}}", "{#{1}}", {:capacity => 2}] commands << [:create_relationship, "connected", "{#{0}}", "{#{2}}", {:capacity => 1}] commands << [:create_relationship, "connected", "{#{2}}", "{#{1}}", {:capacity => 3}] batch_result = neo.batch *commands end
you’ve seen me do this a few times already, so i won’t spend too much time on it. just notice we’re adding the states names to an index, and using the batch rest command to create it all at once. we’ll write our max_flow method next:
def max_flow neo = neography::rest.new neo.execute_script("source = g.idx('states_index')[[name:'california']].iterator().next(); sink = g.idx('states_index')[[name:'illinois']].iterator().next(); max_flow = 0; g.setmaxbuffersize(0); g.starttransaction(); source.oute.inv.loop(2){ !it.object.equals(sink)}. paths.each{ flow = it.capacity.min(); max_flow += flow; it.findall{ it.capacity}.each{ it.capacity -= flow} }; g.stoptransaction(transactionalgraph.conclusion.failure); max_flow;") end
let’s take a closer look at a few things. we use the index to look up our source (start) and sink (end) nodes, and use iterator().next() to get the first node from the gremlin groovy pipeline returned by the index lookup. we also create a variable max_flow where our answer will go.
source = g.idx('states_index')[[name:'california']].iterator().next(); sink = g.idx('states_index')[[name:'illinois']].iterator().next(); max_flow = 0;
we then set the transaction mode to manual by setting the maxbuffersize to zero and start a new transaction. i’ll explain why in a minute.
g.setmaxbuffersize(0); g.starttransaction();
from our source, we go to a neighboring node looping these two oute.inv steps until we reach the sink node.
source.oute.inv.loop(2){ !it.object.equals(sink)}.
for each path we find the lowest capacity along the edges we traversed using the min() function and add it to the max_flow variable we created earlier.
paths.each{ flow = it.capacity.min(); max_flow += flow;
then we subtract the flow from the capacity property of each of the edges in our path. take note we are actually altering data in this step.
it.findall{ it.capacity}.each{ it.capacity -= flow} };
at the end we return max_flow which has the answer to our question.
max_flow;
if you tried to run this method again, or tried to run a similar method using different sinks and sources that traveled over these nodes you’ll have a problem. the capacities were modified and will most likely be zero or show the residual capacity of the transportation network we built.
so to prevent this we stop the transaction with a failure. the changes we made to capacity are not committed and the graph stays the way it was.
g.stoptransaction(transactionalgraph.conclusion.failure);
we can visualize this example using d3.js and its geo path projections :
as usual, all code is available on github . 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 .
source: http://maxdemarzi.com/2012/02/21/max-flow-with-gremlin-and-transactions/
Opinions expressed by DZone contributors are their own.
Trending
-
How to Format Articles for DZone
-
Observability Architecture: Financial Payments Common Observability Elements
-
Top 10 Pillars of Zero Trust Networks
-
Power BI Report by Pulling Data From SQL Tables
Comments