title: In a graph, how to calculate sum of all nodes which a node can reach efficiently?
body: <p>Given a directed graph, with weight assigned to every node.<br>
  Start from any node A, there will be a set of nodes which could be reached from A.<br>
  Define SUM as total weight of this set.</p>
  
  <p>Question: 
  How to calculate SUM for every node in this graph efficiently?<br>
  The graph may contain millions of nodes.</p>
  
  <p>Update 1:<br>
  The graph data structure is composed of the set of start nodes, and each node have a set of point-to nodes. </p>
  
  <p>What I tried:<br>
  Calculate the descendants of every node recursively, and calculate the SUM according to descendant set. This recursion is very inefficient since I have to do set union, uteration operation for a lot of times. Further, I tried to cache the descendant set at each node. However, it easily runs out of memory.<br>
  So, is there any other solution?</p>
  
  <p>Update 2:<br>
  Example graph, edges are all directed, upper nodes points to lower nodes<br>
  <img src="https://i.stack.imgur.com/y6pCn.png" alt="Sample Graph"><br>
  Result should be<br>
      SUM(1)=55
      SUM(2)=35
      SUM(3)=41
      SUM(4)=19
      SUM(5)=22
      SUM(6)=25
      ...</p>