graph algorithm for (economic) share graph
<p>Hi to all graph theory experts :)</p>

<p>I'm currently facing an algorithmic problem which I cannot solve myself.</p>

<p>I have to find all indirect shares for each company to each other in a directed graph already containing the direct shares (see the image for a very simple example).</p>

<p>I have to start with a directed graph where the nodes are the companies and the edges the direct shares between these companies. The algorithm now has to append the indirect shares between all nodes to the edges (this includes adding new edges to the graph during the algorithm).</p>

<p>An indirect share is defined as the product of all intermediate direct shares. If there would be just nodes A, B and C in the graph, There would be only one indirect share, the one from A to C.</p>

<p>INDIRECT(A, C) = 100% * 80% = 1 * 0.8 = 0.8 = 80%</p>

<p>Now I need an algorithm that computes those shares for the whole graph. There is no specific starting point in the graph, and it may contain a variety of circles of each size (in the example there is only one "direct" circle between C and D) and multiple paths between a pair of nodes (like the paths from C to E). </p>

<p>It would be very helpful if anyone could help me out with some pseudo code or description of a possible algorithm. I already searched for algorithms in graph theory books and on the internet, but everything I can find is the standard algorithms for finding the shortest path, all paths, or visiting all nodes of a graph. But I cannot find a mechanism to calculate this kind of mathematical combination of the graph edge weights.</p>

<p><a href="http://i.stack.imgur.com/S7nZB.png" rel="nofollow">example share graph</a></p>