0 Replies Latest reply: Aug 22, 2010 11:53 PM by 843853 RSS

    Algorithms for finding cycles in a non-simple Wieghted Directed Graph

    843853
      Hi all,

      I was hoping someone could advise me on this. I have this network flow/path problem where each node represents a bank and the edges represent financial obligations between each of the banks in the clearing house. Each edge is directed and has a weight which is a function of the ratio of contract owed the bank and those the bank owed to other banks and the ratio of the content of the edge and the capacity of the edge (which is the predefined maximum block size of any one collection of trades so if a contract is worth $1mil and the block size is $10mil then Bank A can process upto 10 of the $1mil contracts throw any given edge to Bank B).

      What I am trying to do is find the minimum amount of cash that each bank or the clearinghouse as a whole will need to make sure that even if bank A fails all the money it owes to others will still be paid so that contracts don't need to be torn up. Theoretically, I thought if I can find cycles where whatever Bank A pays out (even if less than the capacity of the edge/block size) comes back to it at the end of the cycle, this means that money can be recycled through the network. The more unique cycles that are found, the less money the network requires.

      The network does contain pure source and sink nodes, but the edge weights are setup in such a way that the edges with these pure source and sink nodes will only be picked last (i.e. they will have the largest weights).

      I am completely new to graph theory and don't know where to start. I'm not even sure I have formulated the problem properly in terms of graph theory. For instance I have parallel edges one for each trade block. I thought this made sense because I could remove these edges from the graph create a subgraph of this path/cycle with those edges and look for more cycles with the edges left over on the original graph. however I'm not sure if this is the correct way to do this.

      Also, I've been reading up on the Eulerian cycle, Hamilton Cycle, Chinese Postman, the Edmond's Algorithm and Minimum Spanning/branching Trees but I'm now getting confused and not sure which of these actually is the best to use. I don't need to cycles to include all the nodes though the more nodes that are covered by each cycle the better. The key thing is that the edge leaving the root node of the cycle should have the same content as the one entering it. My implementation is in Java using the JUNG2 library.

      Any advise or direction on how to find the cycles will be greatly appreciated.

      many thanks in advance