- cycle_detect.py:
- cycle_detection(edges): yields networkx.DiGraph each time when encounter cycle
- edges: [(source, target),]
- time complexity: Õ(m√n)
- cycle_detection(edges): yields networkx.DiGraph each time when encounter cycle
- test.py:
- command arg: #nodes #edges
This is an implementation based on the following published paper：
@inproceedings{Bernstein:2018:ITS:3174304.3175268,
author = {Bernstein, Aaron and Chechik, Shiri},
title = {Incremental Topological Sort and Cycle Detection in [Equation] Expected Total Time},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
series = {SODA '18},
year = {2018},
isbn = {978-1-6119-7503-1},
location = {New Orleans, Louisiana},
pages = {21--34},
numpages = {14},
url = {http://dl.acm.org/citation.cfm?id=3174304.3175268},
acmid = {3175268},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA}, }