Package org.bigraphs.framework.simulation.encoding

Class BigraphCanonicalForm

java.lang.Object
org.bigraphs.framework.simulation.encoding.BigraphCanonicalForm
All Implemented Interfaces:
BigraphCanonicalFormSupport
public class BigraphCanonicalForm extends Object implements BigraphCanonicalFormSupport
This helper class creates a unique (canonical) label for a place graph of a bigraph such that two isomorphic place graphs have the same label. This is also known as string representation of a graph. With the implemented canonical forms in this class, we create a unique representation for labelled rooted unordered trees, that are, place graphs without sites.

The string representations are the minimal of all these possible breadth-first/depth-first representation according to the lexicographic order (= constraint). This guarantees the uniques of the string representation.

Note: This implementation only considers the first root of a bigraph.

Note on the Implementation: The algorithm used to generate the canonical form is adopted from [1]. The needed top-down BFS is an implementation described in [2] (a sequential bottom-up BFS algorithm).

References

[1] Chi, Y., Yang, Y., Muntz, R.R.: Canonical forms for labelled trees and their applications in frequent subtree mining. Knowl Inf Syst. 8, 203–234 (2005). https://doi.org/10.1007/s10115-004-0180-7.
[2] Beamer, S., Asanović, K., Patterson, D.: Direction-optimizing Breadth-first Search. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. pp. 12:1–12:10. IEEE Computer Society Press, Los Alamitos, CA, USA (2012).

Author:
Dominik Grzelak

  • Method Details

    • createInstance

      public static BigraphCanonicalForm createInstance()

    • createInstance

      public static BigraphCanonicalForm createInstance(boolean withNodeIdentifiers)

    • bfcs

      public <B extends Bigraph<?>> String bfcs(B bigraph)
      Build a breadth-first canonical string (BFCS) for a pure bigraph according to the lexicographic order of the control's labels. The representation is unique.

      // * The bigraph must be prime, i.e., the place graph must only have one root.

      Type Parameters:
      B - the type of the bigraph
      Parameters:
      bigraph - the bigraph
      Returns:
      the BFCS of the place graph of the given bigraph

    • bfcs

      protected String bfcs(ElementaryBigraph<?> elementaryBigraph)

    • isWithNodeIdentifiers

      public boolean isWithNodeIdentifiers()

    • setWithNodeIdentifiers

      public BigraphCanonicalForm setWithNodeIdentifiers(boolean withNodeIdentifiers)

    • isRewriteOpenLinks

      public boolean isRewriteOpenLinks()

    • setRewriteOpenLinks

      public BigraphCanonicalForm setRewriteOpenLinks(boolean rewriteOpenLinks)

    • assertBigraphHasRoots

      public void assertBigraphHasRoots(PureBigraph bigraph)