temoa
temoa copied to clipboard
Cycle detection in commodity_graph detecting too many cycles
Under certain circumstances a combinatorial problem arises in cycle detection. Example network below:
If I got this right (great way to kill an hour), there are 81 simple cycles through this network (doesn't visit any commodity twice)
| length | combinations | example |
|---|---|---|
| 6 | 36 | 1A2B3C' |
| 5 | 0 | - |
| 4 | 36 | 1A2B' |
| 3 | 0 | - |
| 2 | 9 | 1A' |
| total | 81 |
Put a few of these blocks together and it quickly explodes. We had a case where so many cycles were being output to the log file that the log file size hit 56 GB, couldn't be opened, and slowed the model run to a crawl.
Low priority but possible fixes:
- Check how many simple cycles were found. If it is very large, then just log "N cycles detected [...]". This doesn't avoid the slowdown of actually finding all those cycles though, which I haven't tested yet.
- Have a counter check on the cycle iteration block. Log a few cycles then log like above.
- Have a configuration option to disable just the cycle check, in case the detection itself is very slow and should be skipped but we still want orphan detection.