I have a set of many bi-directional links like
A-B, A-C, B-C, A-D, C-D, D-E, etc.
I need to find a set of many closed chains with a sequence of different vertices (vertex-disjoint cycles). It would be better if I can find them all.
How I solve the problem right now:
- I build a directed graph by these links.
- I take one of the vertices and then go to the others by edges, building walks.
- I take the last walks' vertices one by one and then go to the others vertices except those that have already passed, continue building walks.
- Repeat step 3 for each walk until I reach the start vertex. 4a. If other vertices are over and I could not build a closed chain, I delete the walk.
I apologize for my ignorance of graph theory. Perhaps I am reinventing the wheel? Perhaps there is already a solution to this issue? Please tell me.
- The set of links is about 10,000.
- The directed graph may have unconnected islands of subgraphs.
What problems in my realization I want to solve:
- I have to build many walks that will be deleted sooner or later because they are not closed chains.
- I have to check which vertices have already been passed in order to get the next ones.
For what I want to apply it.
I need to filter out incoming incorrect currency pairs' data by their prices. Every currency pair has two current prices: (best) ask and (best) bid. The currency pair's data will be considered valid if it is possible to build an unprofitable exchanging closed chain (vertex-disjoint cycle) containing at least 4 vertices. (Cycle A-B-A is always valid.)
The closed chain is considered unprofitable when the product of the chain's asks is bigger than 1 and the product of the chain's bids is less than 1.
In this case, each currency pair in the chain is valid.
At the same time, finding an invalid chain is not a consequence of the fact that the data is invalid. Only the failure to find a valid chain will be it.