Class Connectivity<V>

java.lang.Object
com.phasmidsoftware.gryphon.java.Connectivity<V>
Type Parameters:
V - the vertex type. Must implement equals and hashCode.

public class Connectivity<V> extends Object
A mutable façade over Gryphon's purely functional disjoint-set implementations, providing a Java-idiomatic API for connectivity queries.

Internally, this class delegates to an immutable Scala AbstractDisjointSet instance, swapping the reference on each mutating operation. From a Java caller's perspective the object behaves as an ordinary mutable data structure.

Two implementations are available via the factory methods:

For most purposes createOptimized is the better choice; createLazy is provided so students can observe the effect of path compression directly. The names match the Scala layer's Connectivity.createLazy and createOptimized, which these delegate to; "lazy" here means without path compression, not lazily evaluated.

Usage example:


 Connectivity<String> c = Connectivity.createOptimized(List.of("A", "B", "C", "D"));
 c.connect("A", "B");
 c.connect("C", "D");
 c.isConnected("A", "B"); // true
 c.isConnected("A", "C"); // false
 c.size();                // 2  (two components)
 
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    connect(V v1, V v2)
    Merges the components containing v1 and v2.
    static <V> Connectivity<V>
    Creates a Connectivity using Weighted Quick Union (O(log n)).
    static <V> Connectivity<V>
    createLazy(V... vs)
    Convenience overload accepting varargs.
    static <V> Connectivity<V>
    Creates a Connectivity using Weighted Quick Union with path compression (amortized near-O(1)).
    static <V> Connectivity<V>
    createOptimized(V... vs)
    Convenience overload accepting varargs, using path compression.
    Returns the representative (root) of the component containing key.
    boolean
    isConnected(V v1, V v2)
    Returns true if v1 and v2 belong to the same component.
    void
    put(V key)
    Adds key as a new singleton component.
    int
    Returns the number of disjoint components (not the number of vertices).
    Returns a human-readable summary of this Connectivity.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Method Details

    • createLazy

      public static <V> Connectivity<V> createLazy(List<V> vs)
      Creates a Connectivity using Weighted Quick Union (O(log n)).
      Type Parameters:
      V - the vertex type.
      Parameters:
      vs - the initial vertices, each placed in its own singleton component.
      Returns:
      a new Connectivity without path compression, containing every vertex of vs.
    • createOptimized

      public static <V> Connectivity<V> createOptimized(List<V> vs)
      Creates a Connectivity using Weighted Quick Union with path compression (amortized near-O(1)).
      Type Parameters:
      V - the vertex type.
      Parameters:
      vs - the initial vertices, each placed in its own singleton component.
      Returns:
      a new Connectivity with path compression, containing every vertex of vs.
    • createLazy

      @SafeVarargs public static <V> Connectivity<V> createLazy(V... vs)
      Convenience overload accepting varargs.
      Type Parameters:
      V - the vertex type.
      Parameters:
      vs - the initial vertices.
      Returns:
      a new Connectivity without path compression, containing every vertex of vs.
    • createOptimized

      @SafeVarargs public static <V> Connectivity<V> createOptimized(V... vs)
      Convenience overload accepting varargs, using path compression.
      Type Parameters:
      V - the vertex type.
      Parameters:
      vs - the initial vertices.
      Returns:
      a new Connectivity with path compression, containing every vertex of vs.
    • connect

      public void connect(V v1, V v2)
      Merges the components containing v1 and v2.

      After this call, isConnected(v1, v2) returns true. If v1 and v2 are already in the same component, this method has no effect.

      Parameters:
      v1 - the first vertex.
      v2 - the second vertex.
    • put

      public void put(V key)
      Adds key as a new singleton component.

      If key is already present, this method has no effect.

      Parameters:
      key - the vertex to add.
    • isConnected

      public boolean isConnected(V v1, V v2)
      Returns true if v1 and v2 belong to the same component.
      Parameters:
      v1 - the first vertex.
      v2 - the second vertex.
      Returns:
      true if connected, false otherwise.
    • size

      public int size()
      Returns the number of disjoint components (not the number of vertices).
      Returns:
      the component count.
    • getComponent

      public V getComponent(V key)
      Returns the representative (root) of the component containing key.

      Two vertices are in the same component if and only if their roots are equal.

      Parameters:
      key - a vertex.
      Returns:
      the root of key's component.
    • toString

      public String toString()
      Returns a human-readable summary of this Connectivity.
      Overrides:
      toString in class Object