Using Gremlin and Transaction to Solve the Problem of Maximum Flow

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.

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/