Core User Guide: Run-time Characteristics

Currently Graphs are represented by mutable.ArraySet and mutable.HashSet. Unfortunately, immutable.Graph has no persistent representation yet.

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)
addition or removal of a single element O(1) O(V + E)
bulk addition or removal of n elements O(n) O(V + E + n)
element look-up O(1)
full traversal O(V + E)
path search in connected graph O(V + E)
shortest path search in connected graph O(VlogV + E)

Algorithms

All algorithms are tail recursive, so they are guaranteed not to cause any stack overflow however big your graph is.

Best practices

Like with all Scala collections, it is thread safe to use the mutable variant in the following situations:

  1. The collection is instantiated and used solely in the scope of a function, so it's only accessible on the stack.
  2. It is known or ensured that the collection will never be accessed concurrently. For instance, a collection defined in an Actor is ensured not to be accessed concurrently because Akka sequentializes message processing.

In any of the above use cases, you are recommended using mutable.Graph.

When using the immutable implementation, try to minimize CPU usage:

  1. Initialize your graph by calling a single method like Graph.from. This is because it is optimized for populating the Graph with all the elements passed. It would be far less efficient to add elements by calling + repeatedly.
  2. Same applies to element addition and removal: Whenever you need to add/remove several elements, prefer calling a single method like ++ or --.