For performance tuning, an interface for storing the topological ordering
A factory for
This interface allows specification of a strategy for marking vertices as visited (based on their topological index, so the vertex type isn't part of the interface).
Interface for a factory that vends visited implementations
DirectedAcyclicGraph implements a DAG that can be modified (vertices & edges added and removed), is guaranteed to remain acyclic, and provides fast topological order iteration.
Region is an *inclusive* range of indices.
This implementation, somewhat to my surprise, is slower than the ArrayList version, probably due to its reallocation of the underlying array for every topology reorder that is required.
This implementation seems to offer the best performance in most cases.
This implementation is close to the performance of VisitedArrayListImpl, with 1/8 the memory usage.
This implementation doesn't seem to perform as well, though I can imagine circumstances where it should shine (lots and lots of vertices).
Exception used in dfsF when a cycle is found
Copyright © 2016. All rights reserved.