Skip to content

#583 Generalize controller-check cycle finder

Albert Hofkamp requested to merge 583-generalize-dfs-cycle-search-2b into develop

I need a simple cycle finder (a simple cycle is a cyclic sequence of nodes that does not cross itself) for sequencing, and decided to generalize the cycle finder in the finite response controller check. It's not the fastest thing but at least it's simple and stable (giving the same results under permutation of the vertices).

Reading by each commit individually is best.

It starts by duplicating the cycle finder and stripping the comments from the generic version, and then slowly refactoring towards a proper generic cycle finder for directed graphs and its controller check application. The second to last commit moves event expansion of an edge from before the search to after detecting a cycle, which can be a big performance gain. The final commit move the generic class to common.java.

Closes #583 (closed)

Merge request reports