The current Graph
representation is based on a mutable hash set.
Unfortunately, immutable Graph
s have no separate persistent representation.
In terms of the Big-O notation, operation costs on graphs can be summarized as follows:
Operation | Cost | |
mutable | immutable | |
Instance Creation | O(V + E) |
|
element addition | O(1) |
O(V + E) |
element removal | O(1) |
O(V + E) |
element look-up | O(1) |
|
traversal | O(V + E) |
|
path search | O(V + E) |
|
shortest path search | O(VlogV + E) |
Algorithms are tail recursive so they are guaranteed not to cause any stack overflow.