DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
Securing Your Software Supply Chain with JFrog and Azure
Register Today

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

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

Using Gremlin and Transaction to Solve the Problem of Maximum Flow

Max De Marzi user avatar by
Max De Marzi
·
Feb. 24, 12 · Interview
Like (0)
Save
Tweet
Share
4.69K Views

Join the DZone community and get the full member experience.

Join For Free

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/

Flow (web browser) Gremlin (query language)

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

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com

Let's be friends: