TemoaProject
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.
maybe a fail early so that it exits after first detected cycle? I figure those who care about cycles care about all of them and those who don't have just one log to ignore
A quick drive-by. We got cycle detection 'for free' when we put the network stuff into Network X pkg for graphing. It was an add-on at the time. The one case where you really want it is if there are any cost arcs that are negative. Possibly via linked techs or in some area where modeler might be clever and trying to credit the capture or generation of something with a negative variable cost. (or fixed ??). Anyhow, those situations can cause havoc if there is any loop with a net negative cost for semi-obvious reasons. There may be others...not sure would have to think about it if there are any dangers absent a negative cost---in theory there should be no "additional" unneeded activity in a demand satisfaction model with all positive costs, but it may still be nice to know about loops (if it doesn't bust the construction). So, as you go forward, perhaps screening the loops for any that involve tech with negative cost would be 1 filtering idea....
