Package org.bigraphs.framework.core.analysis

Class PureLinkGraphConnectedComponents

java.lang.Object
org.bigraphs.framework.core.analysis.PureLinkGraphConnectedComponents
All Implemented Interfaces:
BigraphDecompositionStrategy<PureBigraph>
public class PureLinkGraphConnectedComponents extends Object implements BigraphDecompositionStrategy<PureBigraph>
This class implements the Union-Find-Algorithm to check whether a graph is connected or not. The number of connected components is computed as well.

This implementation is suited for hypergraphs (i.e., link graphs). See the note below for trees and forests. Each hyperedge is treated as a set of vertices that are "unioned" together in the algorithm.

Complexity: O(E * α(V)), where E is the number of hyperedges, V is the number of vertices, and α the inverse of the Ackermann function.

Note: A tree is a connected, acyclic graph, which means every pair of nodes in a tree is connected by exactly one path, and there are no cycles. Given these properties, we do not have to handle connected components in trees. For forests, we just need to identify and count each tree as a connected component.

Author:
Dominik Grzelak

  • Constructor Details

    • PureLinkGraphConnectedComponents

      public PureLinkGraphConnectedComponents()

  • Method Details

    • getDecompositionStrategyType

      public BigraphDecompositionStrategy.DecompositionStrategy getDecompositionStrategyType()
      Specified by:
      getDecompositionStrategyType in interface BigraphDecompositionStrategy<PureBigraph>

    • decompose

      public void decompose(PureBigraph linkGraph)
      Entrypoint of the algorithm. Computes the number of connected components of a link graph. It can be used to determine whether it is connected or not.
      Specified by:
      decompose in interface BigraphDecompositionStrategy<PureBigraph>
      Parameters:
      linkGraph - the bigraph

    • getPartitions

      public Map<Integer,List<BigraphEntity<?>>> getPartitions()
      Returns a map of partitions and their entities (which can be nodes and inner names). Method decompose(PureBigraph) must be called before.

      The unique key signifies not only that it's a unique partition, but the integer value also refers to the "representative" of this partition as determined by the Union-Find algorithm. It can be identified via the idMap.

      Returns:
      partitions

    • getConnectedComponents

      public List<PureBigraph> getConnectedComponents()
      Get the connected component as disjoint bigraphs. They can be composed from left to right. Therefore, a linked list is returned that determines the order. Otherwise, the interfaces have to be checked manually.

      The bigraphs are separated according to the link graph structure. If the bigraph is just a tree, or if there is a single path through all nodes w.r.t. the link graph, then the tree will be returned. That is, the number of connected components is 1.

      Returns:
      the connected components as bigraphs

    • getChildrenForRoot

      public static Set<Integer> getChildrenForRoot(Map<Integer,Integer> idMap, int rootIndex)

    • getIdMap

      public Map<BigraphEntity<?>,Integer> getIdMap()
      Get the map from BigraphEntity to simple Integer labels. For the Union-Find algorithm, the original bigraph nodes and edges are assigned a simple integer label for identification.
      Returns:
      the map from bigraph entities to simple integer labels

    • getUnionFindDataStructure

      public PureLinkGraphConnectedComponents.UnionFind getUnionFindDataStructure()
      Returns the abstract data structure to solve the Union-Find problem.
      Returns:
      the data structure

    • vertexLabelSupplier

      protected Supplier<String> vertexLabelSupplier()

    • edgeLabelSupplier

      protected Supplier<String> edgeLabelSupplier()