DisjointSet

com.phasmidsoftware.gryphon.adjunct.DisjointSet
trait DisjointSet[V, +This <: DisjointSet[V, This]]

Trait to model the behavior of a disjoint set. Thus, we provide put, connect, getDisjointSet, and size in addition to isConnected (from the super-trait).

The purpose of having a disjoint set representation of a "graph" is so that we can answer connectivity questions in close to O(1) time, rather than the O(n + m) time required for a full traversal of an edge-connected graph. The most typical application of this trait is Kruskal's MST algorithm.

The most typical concrete implementation of this trait is the ConnectivityLazy class (usually known as Union-Find).

The type parameter This is the F-bounded self-type, ensuring that put and connect return the concrete subtype rather than DisjointSet[V].

Type parameters

This

the concrete subtype (F-bounded polymorphism).

V

the underlying object type.

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any
Known subtypes
class AbstractDisjointSet[V, W, This]
class ConnectivityASP[V]
class ConnectivityLazy[V]
trait Connectivity[V]
Show all

Members list

Value members

Abstract methods

def connect(v1: V, v2: V): This

Merges the sets containing the given elements v1 and v2. After the operation the two elements belong to the same set.

Merges the sets containing the given elements v1 and v2. After the operation the two elements belong to the same set.

Value parameters

v1

the first element to be connected.

v2

the second element to be connected.

Attributes

Returns

the updated disjoint set with the connection established.

def getDisjointSet(key: V): V

Returns the root (representative) of the component containing key.

Returns the root (representative) of the component containing key.

Value parameters

key

a key.

Attributes

Returns

the root of the component tree to which key belongs.

def put(key: V): This

Adds the specified key to the disjoint set data structure and initializes it as a new singleton set if it does not already exist.

Adds the specified key to the disjoint set data structure and initializes it as a new singleton set if it does not already exist.

Value parameters

key

the element to be added to the disjoint set.

Attributes

Returns

the updated disjoint set containing the newly added key.

def size: Int

The number of disjoint sets (components), not the number of objects.

The number of disjoint sets (components), not the number of objects.

Attributes

Returns

the number of disjoint sets.