3

I have a partially or entirely cyclic graph for which I want to calculate the cost of each node based on the weighted sum of the costs of preceding nodes. Nodes without incoming edges have a fixed cost assigned to them.

For example, the following graph has each node labeled with its calculated cost (the cost of node 2 is fixed), and each edge is labeled with the weight of the preceding node. Thus, the node 1.33 cost is calculated from 1*0.33 + 0.5*2.

Example Graph

I currently use an iterative approach to calculate the cost of each node to within some epsilon, but am looking for an algorithm that can calculate the costs exactly. The example above is pretty simple, the actual problem deals with ~100 nodes per strongly connected component. Any suggestions for an algorithm that can solve this?

zennehoy
  • 6,405
  • 28
  • 55
  • the part where you wrote "(cycle = strongly connected component)" is quite disturbing, while a cycle is a strongly connected component, the reverse is not always true. So please use the right term. – user2798694 Aug 04 '15 at 09:35
  • @user2798694 sorry, I just wanted to clarify that I was referring to strongly connected components, i.e., the interdependent nodes could have cross edges. Removed the mention of cycles. – zennehoy Aug 04 '15 at 09:42

1 Answers1

5

You can build a system of linear equations and solve them. In the example you gave, node 2 is fixed since it has no incoming edge. Assigning value x to the upper right node, y to the upper left node and z to the lower node, you build the following system of linear equations

x = 0.5*2 + 1*y
y = 0.5*z
z = 0.5*x

Using WolframAlpha, we have 

x=1.33333,   y=0.333333,   z=0.666667
user2798694
  • 1,023
  • 11
  • 26