title: Finding minimum weighted matching in sink source graph
body: <p>I have three lists of nodes. sources, sinks, and pipes.
  there is a directed weighted graph from sources to pipes to sinks.
  Sources are only connected to pipes and pipes only to sinks. But sources are not directly connected to sinks. Pipes are zero-sum, meaning that the sum of the weights that come to each pipe from sources is equal to the sum of the edges that go from that pipe to sinks.</p>
  
  <p>I would like to add the minimum number of edges to this graph from sinks back to sources so that sinks and sources also become zero-sum. I know this problem is np-complete I'm interested to see if there is any good polynomial approximation to this problem that would work in real life.</p>
  
  <p><strong>In simpler words:</strong>
  I have a list of sinks and sources. Each sink has a negative number and each source has a positive number so that the sum of all the numbers in the nodes of the graph are zero(no edges so far). I would like to add the minimum number of edges to this graph so that the sum of the weights of the edges going out/in to each node becomes equal to the number on that node.</p>
  
  <p><strong>Here is a sample Code for testing if a graph summarizes another graph</strong>:</p>
  
  <pre><code>from functools import reduce
  from collections import Counter
  
  source_edges = {
      "a0": {"p0": 1, "p2": 5}, 
      "a1": {"p0": 2}, 
      "a2": {"p1": 3}
  }
  sink_edges = {
      "b0": {"p0": 1},
      "b1": {"p0": 1, "p1": 1},
      "b2": {"p0": 1, "p1": 2, "p2": 5},
  }
  res = {
      "a0": {"b0": 1, "b2": 5}, 
      "a1": {"b1": 2}, 
      "a2": {"b2": 3}
  }
  
  sink_degs1 = {k: sum(v.values()) for k, v in sink_edges.items()} 
  sink_degs2 = dict(reduce(lambda x, y: x + y, (Counter(v) for v in res.values())))
  source_degs1 ={k: sum(v.values()) for k, v in res.items()} 
  source_degs2 ={k: sum(v.values()) for k, v in source_edges.items()}
  
  if sink_degs1 == sink_degs2 and source_degs1 == source_degs2:
      print('res summerizes the graph')
  else:
      print('res does not summerize this graph')
  </code></pre>
  
  <p>And a visualization of this graph:</p>
  
  <p><a href="https://i.stack.imgur.com/SOl4T.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/SOl4T.png" alt="graph image"></a></p>