title: Maximum flow with min cost that doesn't satisfy all demands
body: <p>I'm using <a href="http://networkx.github.io/" rel="nofollow noreferrer">NetworkX</a> to solve a maximum-flow problem with more than one source and sink. I found a function that works relatively well in NetworkX called <a href="https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.min_cost_flow.html#networkx.algorithms.flow.min_cost_flow" rel="nofollow noreferrer"><code>max_cost_flow</code></a> however the issue I'm having is that it requires that the net demand be zero, in other words no sink should get less than it needs, otherwise an error is raised.</p>
  <p>What can I use (or how can I modify this algorithm) to allow it to calculate the best possible flow and not necessarily the one satisfies all conditions?</p>
  <p>Per kraskevich's suggestion:</p>
  <pre><code>import networkx as nx
  
  def convert(graph):
  
      allNodes = graph.nodes()
  
      newSource = len(allNodes) + 1
      newSink = len(allNodes) + 2
  
      graph.add_node(newSource)
      graph.add_node(newSink)
  
  
      for currentNode in allNodes:
  
          demand = graph.node[currentNode]['demand']
  
          if demand &lt; 0 :
              graph.add_edge(newSource, currentNode, weight=0, capacity=demand)
  
  
          if demand &gt; 0:
              graph.add_edge(newSink, currentNode, weight=0, capacity=demand)
  
      return graph
  
  
  
  g = nx.DiGraph()
  
  g.add_node(1, demand = 1)
  g.add_node(2, demand = -2)
  g.add_node(3, demand = 2)
  g.add_node(4, demand = -4)
  
  g.add_edge(1, 2, weight=4, capacity=100)
  g.add_edge(1, 4, weight=3, capacity=100)
  g.add_edge(3, 2, weight=5, capacity=100)
  g.add_edge(3, 4, weight=2, capacity=100)
  g.add_edge(3, 1, weight=1)
  newGraph = convert(g)
  print(nx.max_flow_min_cost(g, newGraph.nodes()[-2],newGraph.nodes()[-1]))
  </code></pre>