Convert weighted direct cyclic graph to equivalent acyclic graph

Question

I have a cyclic weighted directed graph and the goal is to remove the cycle present in the path.

eg: the paths are as below,

from | to | weight
------------------
a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

the cycle in the graph is introduced by the path d -> a. Can anyone suggest an algorithm to remove the cycle d -> a by adjusting the weights of the other nodes. The resulting acyclic graph to be equivalent in terms of passing on the weights to the end nodes e, f.

Thanks, Vivek

Answer 1

Sleator–Tarjan call this the acyclic flow problem and describe an O(m log n)-time solution on page 389 of their first paper on dynamic trees. If you don't need the fastest algorithm, repeatedly use depth-first search to find one flow cycle and then send in reverse the minimum amount of flow that cancels one or more arcs.

On your graph:

a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

DFS finds a cycle a -0.5> b -1> d -0.25> a. Send -0.25 on that same cycle.

a    -> b | 0.5 - 0.25 = 0.25
a    -> c | 0.5
c    -> e | 1
b    -> d | 1 - 0.25 = 0.75
d    -> f | 0.75

We delete

d    -> a | 0.25 - 0.25 = 0

The flow is acyclic, so we stop.

Answer 2

From your comment to David's answer and from the weights of the graph, it looks to me like the weights are probabilities to move from one node to the other (or percentage of a unit that moves from on node to another, either way the math is the same). If so, this can be modeled as a Markov chain, and more specifically as an absorbing Markov chain. But first, we need to add two paths to fit the formal definition:

e -> e | 1.0
f -> f | 1.0

I'm not sure if you need a general algorithm for multiple graphs similar to this one or this is the only graph you need to solve. I'll give an overview of the math involved for this particular graph, and hopefully you can generalize it into an algorithm if you need it.

_{The arithmetic is pretty cumbersome, follow along on the absorbing Markov chain link.}

First, we need the adjacency matrix, more commonly called the state transition matrix when dealing with Markov chains:

  |  a     b     c     d  |  e     f
--+-----------------------+------------
a |  0     0.5   0.5   0  |  0     0
b |  0     0     0     1  |  0     0
c |  0     0     0     0  |  1     0
d |  0.25  0     0     0  |  0     0.75
--+-----------------------+------------
e |  0     0     0     0  |  1     0
f |  0     0     0     0  |  0     1

The top left portion of the matrix are the transitions between the transient (non-ending) states (symbolized by Q), the bottom right are the absorbing states. The top right will be symbolized by R.

The fundamental matrix, is calculated as N = (I - Q)^-1. While the absorbing probabilities (i.e. given infinite time, the percentage that will end up in each of the absorbing states) is given as B = NR. Using my best ASCII matrices, the numbers for this graph are:

         +-          -+             +-    -+  
         | 8  4  4  4 |             | 4  3 |
         | 2  8  1  8 |             | 1  6 |
N = (1/7)| 0  0  7  0 |    B = (1/7)| 7  0 |
         | 2  1  1  8 |             | 1  6 |
         +-          -+             +-    -+ 

The top row of the B matrix is read, starting from state a, there's a 4/7 (approx. 0.5714) chance of ending up in state e, and a 3/7 (approx. 0.4286) chance of ending up in state f. You can ignore the other three rows, since those are the probabilities when starting in states b, c, and d.

Therefore if you want an equivalent graph where the end chance of ending up in states e and f are the same, but without the cycle, you can remove the d -> a path, and use the following weights:

a -> b | 0.4286
a -> c | 0.5714