Package org.bigraphs.framework.core.analysis

Class PureLinkGraphConnectedComponents.UnionFind

java.lang.Object
org.bigraphs.framework.core.analysis.PureLinkGraphConnectedComponents.UnionFind
Enclosing class:
PureLinkGraphConnectedComponents
public static class PureLinkGraphConnectedComponents.UnionFind extends Object
Generic subclass that solves the connectedness problem of a graph. Vertices are integers. This implementation is suited for hypergraphs (see union(Set)).

  • Constructor Details

    • UnionFind

      public UnionFind(int numVertices)

  • Method Details

    • find

      public int find(int x)

    • union

      public void union(Set<Integer> vertices)
      The union method finds the representative (root) of each vertex in the hyperedge, and then merges the sets containing those representatives using the standard Union-Find operations.

      It takes a Set of vertices instead of just two vertices. This allows to handle hyperedges that connect multiple vertices.

      Parameters:
      vertices - the vertices connected to a hyperedge

    • getCount

      public int getCount()

    • getChildParentMap

      public Map<Integer,Integer> getChildParentMap()

    • getRank

      public Map<Integer,Integer> getRank()

    • getRootsOfPartitions

      public Set<Integer> getRootsOfPartitions(Map<Integer,Integer> parentMap)

    • countRoots

      public int countRoots(Map<Integer,Integer> parentMap)