Package es.urjc.etsii.grafo.util.collections

Class DisjointSet

java.lang.Object
es.urjc.etsii.grafo.util.collections.DisjointSet
public class DisjointSet extends Object
UnionFind/Disjoint sets implementation

  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointSet(int n)
    Create a Disjoint set where the n elements are initially all disjoint
    DisjointSet(int n, int offset)
    Create a Disjoint set where the n elements are initially all disjoint
    DisjointSet(DisjointSet original)
    Clone a DisjointSet

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    areJoined(int a, int b)
    Check if two nodes are in the same set
    int
    find(int n)
    Find the set id of a given element
    int
    size(int n)
    Returns the size of set/cluster the given points is part of
    boolean
    union(int a, int b)
    Join the sets a and b are members of

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • DisjointSet

      public DisjointSet(int n, int offset)
      Create a Disjoint set where the n elements are initially all disjoint
      Parameters:
      n - number of elements to hold
      offset - Offset elements by an index ex 1 wil be 0-9 → 1-10

    • DisjointSet

      public DisjointSet(DisjointSet original)
      Clone a DisjointSet
      Parameters:
      original - original disjointSet

    • DisjointSet

      public DisjointSet(int n)
      Create a Disjoint set where the n elements are initially all disjoint
      Parameters:
      n - number of elements to hold

  • Method Details

    • size

      public int size(int n)
      Returns the size of set/cluster the given points is part of
      Parameters:
      n - node to check
      Returns:
      size of the cluster n is part of

    • find

      public int find(int n)
      Find the set id of a given element
      Parameters:
      n - element
      Returns:
      set id

    • areJoined

      public boolean areJoined(int a, int b)
      Check if two nodes are in the same set
      Parameters:
      a - first node to check
      b - second node to check
      Returns:
      true if the two nodes are in the same set/cluster, false otherwise

    • union

      public boolean union(int a, int b)
      Join the sets a and b are members of
      Parameters:
      a - any element from set A
      b - any element from set B
      Returns:
      true if the sets have been joined, false if they were already part of the same set