Package moss

Class Fragment

java.lang.Object
moss.Fragment
All Implemented Interfaces:
Serializable

public class Fragment extends Object implements Serializable
Class for graph fragments (subgraphs and their embeddings).

A graph fragment is a part of a graph. It consists of a list of embeddings that indicate where the fragment can be found in different graphs. In addition, a fragment contains information about the extension edge (and maybe extension node) by which it was constructed from a smaller fragment.

Since:
2002.03.11
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int
    flag for an adapted fragment; this flag is set when a fragment gets adapted, so that the adaptation is not repeated
    protected Fragment
    the base fragment (which was extended)
    protected Embedding
    the current base embedding (which was extended)
    protected static final int
    flag for the result of an extension that is a chain start
    protected int
    the number of variable length chains
    protected static final int
    flag for a closed fragment (no super-fragment has the same support)
    protected int
    the number of embeddings/graphs for the current graph
    static final int
    group identifier: complement
    protected NamedGraph[]
    the graph cover of the fragment
    protected Embedding
    the current embedding (cursor)
    protected static final int
    default flags that are set when a fragment is created
    protected boolean
    whether the fragment is directed
    protected int
    the index of the destination node of the (first) new edge
    protected int
    the property flags of the embedding (e.g.
    static final int
    group identifier: focus
    protected Graph
    the fragment as a graph
    static final int
    support type: number of graphs that contain an embedding
    static final int
    support type flag: whether to use the greedy MIS algorithm
    protected int
    the index of the (first) new edge
    protected Embedding
    the list of embeddings of the fragment
    protected int
    the maximal number of embeddings per graph
    static final int
    support type: minimum number of different nodes mapped to
    static final int
    support type: maximum independent set of harmful overlap graph
    static final int
    support type: maximum independent set of normal overlap graph
    protected static final int
    flag for valid orbit identifiers in the fragment graph
    protected static final int
    flag for a packed list of embeddings
    protected static final int
    flag for a perfect extension; set if the fragment was created by a perfect extension of its base fragment
    protected static final int
    flag for reverted extension information
    protected int[]
    the indices of the nodes of new ring edges
    protected static final int
    flag for possible equivalent siblings
    protected int
    the number of nodes in a ring or chain (positive: ring, negative: chain)
    protected int
    the index of the source node of the (first) new edge
    protected int[]
    the support and embedding counters for focus and complement
    static final int
    the support type mask
    protected Embedding
    the tail of the embedding list
    protected static final int
    flag for a valid fragment; invalid fragments can occur in ring mining with canonical form pruning: they are non-canonical fragments that have to processed nevertheless
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Create an empty fragment.
    protected
    Fragment(boolean dir)
    Create an empty fragment.
    protected
    Fragment(int max)
    Create an empty fragment with an embedding limit.
    protected
    Fragment(int max, boolean dir)
    Create an empty fragment with an embedding limit.
    protected
    Create a fragment from an extension.
    protected
    Fragment(Fragment frag, int src, int dst, int edge, int node, boolean reversed)
    Create an extended fragment.
    protected
    Fragment(Graph graph)
    Create a fragment from a graph.
    protected
    Fragment(Graph graph, int max)
    Create a fragment with an embedding limit from a graph.
    protected
    Fragment(Graph graph, int max, boolean dir)
    Create a fragment with an embedding limit from a graph.
    protected
    Fragment(Graph graph, Graph sub)
    Create a fragment from a graph and a subgraph.
    protected
    Fragment(Graph graph, Graph sub, int max)
    Create a fragment from a graph and a subgraph.
  • Method Summary

    Modifier and Type
    Method
    Description
    protected boolean
    adapt(CanonicalForm cnf, boolean check)
    Adapt the fragment (limited reordering of the edges and nodes).
    protected boolean
    Add an extension (as an embedding) to the fragment.
    protected void
    Add an embedding (list) to the fragment.
    void
    Add a graph to the cover of the fragment.
    protected boolean
    Check whether all variable length chains are valid.
    void
    computeSupport(int type)
    Compute the support of the fragment.
    boolean
    equals(Object frag)
    Check whether two fragments are equal.
    boolean
    Compare the (canonical) code words of two fragments.
    protected boolean
    Check whether a fragments can have equivalent siblings.
    protected Embedding
    Get the first embedding of the fragment.
    Get the first graph containing the fragment.
    int
    Get the number of embeddings in the complement.
    int
    Get the complement support of a fragment.
    int
    Get the number of embeddings (in both groups together).
    int
    getEmbCount(int group)
    Get the number of embeddings in the given group.
    int
    Get the number of embeddings in the focus.
    int
    Get the focus support of a fragment.
    Get the fragment as a (sub-)graph.
    int
    Get the support of a fragment (in both groups together).
    int
    getSupport(int group)
    Get the support of a fragment in the given group.
    int
    Compute the hash code of the fragment.
    protected boolean
    hasOpenRings(int min, int max)
    Check whether the fragment has open rings.
    protected boolean
    Check whether the fragment has node orbit identifiers.
    protected boolean
    Check whether the fragment has unclosable rings.
    protected boolean
    Check whether the fragment is in canonical form.
    protected int
    isCanonic(CanonicalForm cnf, boolean partial)
    Check whether the fragment is in canonical form.
    protected boolean
    Check whether the fragment is closed.
    protected boolean
    Check whether two fragments are equivalent.
    protected boolean
    isPerfect(boolean chain)
    Check whether an extension is perfect.
    protected boolean
    Check whether the fragment is the result of an extension by a ring edge.
    protected boolean
    Check whether the fragment is the result of a ring extension.
    protected boolean
    Check whether the valid flag is set.
    static void
    main(String[] args)
    Main function for testing some basic functionality.
    protected boolean
    Make the fragment canonic (minimize the code word).
    protected boolean
    makeCanonic(CanonicalForm cnf, int keep)
    Make the fragment canonic (minimize the code word).
    protected void
    Reorganize the fragment with a map from a canonical form.
    protected int
    mergeExts(Fragment[] exts, int cnt)
    Merge ring extensions that have the same initial edge.
    protected Embedding
    Get the next embedding of the fragment.
    Get the next graph containing the fragment.
    void
    Pack the list of embeddings.
    void
    pack(int max)
    Pack the list of embeddings.
    protected void
    Reembed a fragment, that is, recreate its embedding list.
    protected void
    Revert the extension information of the fragment.
    protected void
    setClosed(boolean closed)
    Set the flag for a closed fragment.
    protected void
    setValid(boolean valid)
    Set or clear the valid flag.
    protected int
    Get the size of the fragment.
    Create a string description of the fragment.
    Create the code word of the fragment.
    Create a string description of the fragment.
    protected void
    Unembed a fragment, that is, remove all embeddings.
    void
    Unpack the list of embeddings.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait
  • Field Details

    • FOCUS

      public static final int FOCUS
      group identifier: focus
      See Also:
    • COMPL

      public static final int COMPL
      group identifier: complement
      See Also:
    • GRAPHS

      public static final int GRAPHS
      support type: number of graphs that contain an embedding
      See Also:
    • MIS_OLAP

      public static final int MIS_OLAP
      support type: maximum independent set of normal overlap graph
      See Also:
    • MIS_HARM

      public static final int MIS_HARM
      support type: maximum independent set of harmful overlap graph
      See Also:
    • MIN_IMAGE

      public static final int MIN_IMAGE
      support type: minimum number of different nodes mapped to
      See Also:
    • SUPPMASK

      public static final int SUPPMASK
      the support type mask
      See Also:
    • GREEDY

      public static final int GREEDY
      support type flag: whether to use the greedy MIS algorithm
      See Also:
    • VALID

      protected static final int VALID
      flag for a valid fragment; invalid fragments can occur in ring mining with canonical form pruning: they are non-canonical fragments that have to processed nevertheless
      See Also:
    • CLOSED

      protected static final int CLOSED
      flag for a closed fragment (no super-fragment has the same support)
      See Also:
    • CHAIN

      protected static final int CHAIN
      flag for the result of an extension that is a chain start
      See Also:
    • SIBLINGS

      protected static final int SIBLINGS
      flag for possible equivalent siblings
      See Also:
    • PERFECT

      protected static final int PERFECT
      flag for a perfect extension; set if the fragment was created by a perfect extension of its base fragment
      See Also:
    • REVERTED

      protected static final int REVERTED
      flag for reverted extension information
      See Also:
    • ADAPTED

      protected static final int ADAPTED
      flag for an adapted fragment; this flag is set when a fragment gets adapted, so that the adaptation is not repeated
      See Also:
    • ORBITS

      protected static final int ORBITS
      flag for valid orbit identifiers in the fragment graph
      See Also:
    • PACKED

      protected static final int PACKED
      flag for a packed list of embeddings
      See Also:
    • DEFAULT

      protected static final int DEFAULT
      default flags that are set when a fragment is created
      See Also:
    • dir

      protected boolean dir
      whether the fragment is directed
    • graph

      protected Graph graph
      the fragment as a graph
    • base

      protected Fragment base
      the base fragment (which was extended)
    • bemb

      protected Embedding bemb
      the current base embedding (which was extended)
    • cover

      protected NamedGraph[] cover
      the graph cover of the fragment
    • list

      protected Embedding list
      the list of embeddings of the fragment
    • tail

      protected Embedding tail
      the tail of the embedding list
    • curr

      protected Embedding curr
      the current embedding (cursor)
    • max

      protected int max
      the maximal number of embeddings per graph
    • cnt

      protected int cnt
      the number of embeddings/graphs for the current graph
    • chcnt

      protected int chcnt
      the number of variable length chains
    • idx

      protected int idx
      the index of the (first) new edge
    • src

      protected int src
      the index of the source node of the (first) new edge
    • dst

      protected int dst
      the index of the destination node of the (first) new edge
    • size

      protected int size
      the number of nodes in a ring or chain (positive: ring, negative: chain)
    • flags

      protected int flags
      the property flags of the embedding (e.g. PERFECT)
    • supp

      protected int[] supp
      the support and embedding counters for focus and complement
    • ris

      protected int[] ris
      the indices of the nodes of new ring edges
  • Constructor Details

    • Fragment

      protected Fragment()
      Create an empty fragment.
      Since:
      2002.03.11 (Christian Borgelt)
    • Fragment

      protected Fragment(boolean dir)
      Create an empty fragment.
      Parameters:
      dir - whether the fragment is directed
      Since:
      2021.10.07 (Christian Borgelt)
    • Fragment

      protected Fragment(Graph graph)
      Create a fragment from a graph.
      Parameters:
      graph - the subgraph representing the fragment
      Since:
      2002.03.11 (Christian Borgelt)
    • Fragment

      protected Fragment(int max)
      Create an empty fragment with an embedding limit.
      Parameters:
      max - the maximum number of embeddings per graph
      Since:
      2002.03.11 (Christian Borgelt)
    • Fragment

      protected Fragment(int max, boolean dir)
      Create an empty fragment with an embedding limit.
      Parameters:
      max - the maximum number of embeddings per graph
      dir - whether the fragment is directed
      Since:
      2021.10.07 (Christian Borgelt)
    • Fragment

      protected Fragment(Graph graph, int max)
      Create a fragment with an embedding limit from a graph.
      Parameters:
      graph - the subgraph representing the fragment
      max - the maximum number of embeddings per graph
      Since:
      2002.03.11 (Christian Borgelt)
    • Fragment

      protected Fragment(Graph graph, int max, boolean dir)
      Create a fragment with an embedding limit from a graph.
      Parameters:
      graph - the subgraph representing the fragment
      max - the maximum number of embeddings per graph
      dir - whether the graphs are directed
      Since:
      2002.03.11 (Christian Borgelt)
    • Fragment

      protected Fragment(Graph graph, Graph sub)
      Create a fragment from a graph and a subgraph.
      Parameters:
      graph - the graph into which to embed the subgraph
      sub - the subgraph to embed into the graph
      Since:
      2007.10.25 (Christian Borgelt)
    • Fragment

      protected Fragment(Graph graph, Graph sub, int max)
      Create a fragment from a graph and a subgraph.
      Parameters:
      graph - the graph into which to embed the subgraph
      sub - the subgraph to embed into the graph
      max - the maximum number of embeddings
      Since:
      2007.10.25 (Christian Borgelt)
    • Fragment

      protected Fragment(Fragment frag, int src, int dst, int edge, int node, boolean reversed)
      Create an extended fragment.

      A fragment is created from a base fragment and information about a single edge extension, which is the common first edge of the fragments to be merged into it.

      Parameters:
      frag - the base fragment which was extended by rings
      src - the source node index of the edge to add
      dst - the destination node index of the edge to add
      edge - the edge type of the edge to add
      node - the destination node type of the edge to add
      reversed - whether the edge direction is reversed
      Since:
      2010.01.23 (Christian Borgelt)
    • Fragment

      protected Fragment(CanonicalForm cnf)
      Create a fragment from an extension.

      This function is called if there is no fragment that is equivalent to a created extension and thus a new fragment has to be created.

      Parameters:
      cnf - the canonical form from which to create the fragment
      Since:
      2002.03.11 (Christian Borgelt)
  • Method Details

    • equals

      public boolean equals(Object frag)
      Check whether two fragments are equal.

      This method is overridden only to avoid certain warnings.

      Overrides:
      equals in class Object
      Parameters:
      frag - the fragment to compare to
      Returns:
      whether the two fragments are equal
      Since:
      2007.11.06 (Christian Borgelt)
    • hashCode

      public int hashCode()
      Compute the hash code of the fragment.
      Overrides:
      hashCode in class Object
      Returns:
      the hash code of the fragment
      Since:
      2006.11.11 (Christian Borgelt)
    • size

      protected int size()
      Get the size of the fragment.

      The size of the fragment is the number of nodes in an output (or a created subgraph), which is why the number of chains, each of which will be represented as a pseudo-node, has to be added to the number of nodes of an embedding.

      Returns:
      the size of the fragment
      Since:
      2003.02.21 (Christian Borgelt)
    • getGraph

      public Graph getGraph()
      Get the fragment as a (sub-)graph.

      For this function to work the fragment must be created from a subgraph or an extension or at least one embedding must have been added to it. Otherwise the (sub-)graph representing the fragment is undefined.

      Returns:
      the fragment as a (sub-)graph
      Since:
      2002.03.11 (Christian Borgelt)
    • addEmb

      protected void addEmb(Embedding emb)
      Add an embedding (list) to the fragment.

      This function is meant for adding the embeddings of the seed structure into some graph to the seed fragment. It is assumed that, if multiple embeddings are added with one call (that is, if a list of embeddings is added), they all refer to the same graph. On the other hand, the function may be called several times with different lists of embbedings all of which refer to the same graph.

      If the fragment is limited w.r.t. the number of embeddings that may be stored per graph, the embedding(s) may not actually be stored, but will be regenerated on demand.

      Parameters:
      emb - the embedding to add to the fragment
      Since:
      2002.03.11 (Christian Borgelt)
    • addEmb

      protected boolean addEmb(CanonicalForm cnf)
      Add an extension (as an embedding) to the fragment.

      This function is called if a created extension is equivalent to the fragment and thus only an embedding has to be added. It assumes that the extension is equal to the fragment, that is, that cnf.compareTo(this) yields 0.

      Parameters:
      cnf - the canonical form describing the embedding to add
      Returns:
      whether the embedding was added (duplicate check)
      Since:
      2002.03.11 (Christian Borgelt)
    • pack

      public void pack()
      Pack the list of embeddings.

      Pack the list of embeddings with the maximum number of embeddings per graph that was specified when this fragment was created.

      Since:
      2007.08.14 (Christian Borgelt)
    • pack

      public void pack(int max)
      Pack the list of embeddings.
      Parameters:
      max - the maximum number of embeddings per graph
      Since:
      2007.08.14 (Christian Borgelt)
    • unpack

      public void unpack()
      Unpack the list of embeddings.
      Since:
      2007.08.14 (Christian Borgelt)
    • firstEmb

      protected Embedding firstEmb()
      Get the first embedding of the fragment.

      Together with the function next() this function allows to traverse the list of embeddings without having to pay attention to the fact that due to a limit for the number of embeddings that may be stored per graph, some embeddings have been packed and thus are not available directly. Rather these two functions regenerate the embeddings from a packed embedding by reembedding the subgraph representing the fragment into the corresponding graph.

      Note that this function, just as the accompanying function next(), modifies the tail pointer, which is reused as a cursor for packed embeddings, and thus it is impossible to add embeddings after this function has been called.

      Returns:
      the first embedding of the fragment or null if there is no embedding
      Since:
      2005.08.17 (Christian Borgelt)
      See Also:
    • nextEmb

      protected Embedding nextEmb()
      Get the next embedding of the fragment.
      Returns:
      the next embedding of the fragment or null if there is no next embedding
      Since:
      2005.08.17 (Christian Borgelt)
      See Also:
    • addGraph

      public void addGraph(NamedGraph graph)
      Add a graph to the cover of the fragment.
      Parameters:
      graph - the graph to add to the cover
      Since:
      2010.01.23 (Christian Borgelt)
    • firstGraph

      public Graph firstGraph()
      Get the first graph containing the fragment.

      Together with the function nextGraph() this function allows to traverse the list of graphs containing this fragment without having to pay attention to the fact that the fragment may have several embeddings into the same graph.

      Returns:
      the first graph containing the fragment or null if there is no such graph
      Since:
      2002.03.11 (Christian Borgelt)
      See Also:
    • nextGraph

      public Graph nextGraph()
      Get the next graph containing the fragment.
      Returns:
      the next graph containing the fragment or null if there is no next graph
      Since:
      2002.03.11 (Christian Borgelt)
      See Also:
    • computeSupport

      public void computeSupport(int type)
      Compute the support of the fragment.

      The support of the fragment in both graph groups, that is, FOCUS and COMPL, is computed. The computed values can then be accessed with the functions getSupport(int), getFocusSupport(), and getComplSupport().

      Parameters:
      type - the type of support to compute
      Since:
      2007.06.21 (Christian Borgelt)
    • getSupport

      public int getSupport()
      Get the support of a fragment (in both groups together).
      Returns:
      the (total) support of a fragment
      Since:
      2007.10.24 (Christian Borgelt)
      See Also:
    • getSupport

      public int getSupport(int group)
      Get the support of a fragment in the given group.
      Parameters:
      group - the group for which to get the support
      Returns:
      the support of a fragment in the given group
      Since:
      2007.08.09 (Christian Borgelt)
      See Also:
    • getFocusSupport

      public int getFocusSupport()
      Get the focus support of a fragment.
      Returns:
      the focus support of a fragment
      Since:
      2007.06.12 (Christian Borgelt)
      See Also:
    • getComplSupport

      public int getComplSupport()
      Get the complement support of a fragment.
      Returns:
      the complement support of a fragment
      Since:
      2007.06.12 (Christian Borgelt)
      See Also:
    • getEmbCount

      public int getEmbCount()
      Get the number of embeddings (in both groups together).
      Returns:
      the (total) number of embeddings
      Since:
      2007.10.24 (Christian Borgelt)
    • getEmbCount

      public int getEmbCount(int group)
      Get the number of embeddings in the given group.
      Parameters:
      group - the group for which to get the number of embeddings
      Returns:
      the number of embeddings in the given group
      Since:
      2007.08.09 (Christian Borgelt)
    • getFocusEmbCount

      public int getFocusEmbCount()
      Get the number of embeddings in the focus.
      Returns:
      the number of embeddings in the focus
      Since:
      2007.08.09 (Christian Borgelt)
    • getComplEmbCount

      public int getComplEmbCount()
      Get the number of embeddings in the complement.
      Returns:
      the number of embeddings in the complement
      Since:
      2007.08.09 (Christian Borgelt)
    • unembed

      protected void unembed()
      Unembed a fragment, that is, remove all embeddings.

      The embeddings of fragments that correspond to nodes in the search tree that are siblings of nodes on the current path in the search tree can temporarily be removed. They can recreated from the embeddings of their base fragments when recursion returns and the fragment is actually processed.

      Since:
      2005.08.17 (Christian Borgelt)
    • reembed

      protected void reembed()
      Reembed a fragment, that is, recreate its embedding list.

      As long as sibling fragments are processed, the embeddings of a fragment need not be avaiblable and thus can temporarily be removed. They are recreated when the fragment is actually processed. This is done by extending their base embeddings or, if this is impossible, by reembedding the fragment.

      Since:
      2005.08.17 (Christian Borgelt)
    • setValid

      protected void setValid(boolean valid)
      Set or clear the valid flag.

      By default a fragment is valid. The valid flag is cleared for a fragment that is not canonical (and thus must not be reported), but nevertheless has to be kept and processed. Such fragments can occur when ring extensions are combined with canonical form pruning.

      Parameters:
      valid - whether to set or clear the valid flag
      Since:
      2006.06.23 (Christian Borgelt)
    • isValid

      protected boolean isValid()
      Check whether the valid flag is set.

      If the valid flag is cleared, the fragment need not be reported, because it is non-canonical and thus a duplicate.

      Returns:
      whether the valid flag is set
      Since:
      2006.06.23 (Christian Borgelt)
    • isRingExt

      protected boolean isRingExt()
      Check whether the fragment is the result of a ring extension.
      Returns:
      whether the fragment is the result of a ring extension
      Since:
      2003.08.06 (Christian Borgelt)
    • isRingEdgeExt

      protected boolean isRingEdgeExt()
      Check whether the fragment is the result of an extension by a ring edge.
      Returns:
      whether the fragment is the result of an extension by a ring edge
      Since:
      2006.05.16 (Christian Borgelt)
    • isPerfect

      protected boolean isPerfect(boolean chain)
      Check whether an extension is perfect.

      An extension is perfect if it can be applied to all base embeddings. If this is the case, all search tree branches to the right of the perfect extension can be pruned (partial perfect extension pruning), since no closed frequent fragment can be contained in these branches, or even all search tree branches other than the perfect extension branch can be pruned (full perfect extension pruning).

      In order to avoid certain problems with rings, such pruning must be restricted to extension edges that are bridges in all graphs or that close a ring (in all graphs). Ring edges that do not close a ring can lead to problems if they are part of rings of different sizes in the underlying graphs and thus are not considered as candidates for perfect extensions. Furthermore, if chain extensions are considered, an edge that could be the start of a chain is also not taken into account as a candidate for a perfect extension.

      If a fragment is found to have resulted from a perfect extension, it is marked as perfect, so that a second call to this function does not repeat the checks.

      Parameters:
      chain - whether there are sibling chain extensions
      Returns:
      whether the extension that created the fragment is perfect
      Since:
      2003.08.01 (Christian Borgelt)
    • revert

      protected void revert()
      Revert the extension information of the fragment.

      If a perfect extension is followed as the only branch and there are search tree branches to the left of this branch (where "to the left" means "referring to fragments with lexicographically smaller code words"), the extension information must be reset to that of the base fragment, so that no fragments are lost.

      Since:
      2003.08.08 (Christian Borgelt)
    • equivSiblings

      protected boolean equivSiblings()
      Check whether a fragments can have equivalent siblings.

      If extensions have been filtered with node orbits, a fragment can have equivalent siblings only if it is the result of a ring or chain extension or the result of an edge extension that closes a ring. If no orbit filtering was carried out, any fragment may possess equivalent siblings.

      Returns:
      whether the fragment can have equivalent siblings
      Since:
      2011.02.18 (Christian Borgelt)
    • isEquivTo

      protected boolean isEquivTo(Fragment frag)
      Check whether two fragments are equivalent.

      Two fragments are equivalent if they refer to the same nodes and edges, although maybe in a different way. To check this, it is tried to find an equivalent embedding of the two fragments for one graph. Technically this is done by marking one embedding of one fragment in the graph referred to and then checking whether any embedding of the other fragment into the same graph is fully marked.

      Parameters:
      frag - the fragment to compare to
      Returns:
      whether the given fragment is equivalent
      Since:
      2002.07.15 (Christian Borgelt)
    • setClosed

      protected void setClosed(boolean closed)
      Set the flag for a closed fragment.

      In the search it may be possible to determine, without an explicit test, that a fragment is not closed, namely if one of the extensions of the fragment that are considered in the search has the same support. In this case the fragments closed flag is cleared, so that the test function isClosed() returns immediately with a negative result. By default the closed flag is set for a fragment.

      Parameters:
      closed - whether to set or clear the closed flag
      Since:
      2006.06.22 (Christian Borgelt)
    • isClosed

      protected boolean isClosed(CanonicalForm cnf)
      Check whether the fragment is closed.

      A fragment is closed if no superstructure has the same support, that is, occurs in the same number of graphs in the database. Closed fragments are not reported.

      The basic idea of the test is to form a list of all possible extensions of the embeddings into the first graph and then trying to do the same extensions on embeddings into the remaining graphs. Whenever an extension cannot be done on some embedding, the extension is removed from the list. That is, the list always contains the extensions that are possible in all already processed graphs. If this list gets empty during the process, there is no extension that is possible in all graphs and consequently the fragment is closed. If, on the other hand, the list contains at least one element after all graphs have been processed, the fragment is not closed, since each of the extensions that remain in the list can be done in all graphs and thus lead to a superstructure with the same support.

      Parameters:
      cnf - the canonical form defining which extensions must be considered
      Returns:
      whether the fragment is closed
      Since:
      2005.07.23 (Christian Borgelt)
    • isCanonic

      protected boolean isCanonic(CanonicalForm cnf)
      Check whether the fragment is in canonical form.
      Parameters:
      cnf - the canonical form
      Returns:
      whether the fragment is in canonical form
      Since:
      2005.07.24 (Christian Borgelt)
    • isCanonic

      protected int isCanonic(CanonicalForm cnf, boolean partial)
      Check whether the fragment is in canonical form.

      The test may be executed in a partial form, in which only the edges up to the last added edge are seen as fixed, while the rest can be reordered freely to achieve canonical form.

      Parameters:
      cnf - the canonical form
      partial - whether to carry out a partial test
      Returns:
      whether the fragment is in canonical form -1, if the fragment differs from the canonical form in the fixed edges, 0, if it is not canonical, but does not differ in the fixed edges, +1, if the fragment is canonical.
      Since:
      2005.07.24 (Christian Borgelt)
    • map

      protected void map(CanonicalForm cnf)
      Reorganize the fragment with a map from a canonical form.

      The reorganization consists in reordering the nodes and edges of the subgraph representing the fragment as well as reordering the node and edge references of all embeddings. This function is called in makeCanonic() and in adapt() to carry out the changes determined by the corresponding canonical form.

      Parameters:
      cnf - the canonical form containing the map
      Since:
      2002.03.11 (Christian Borgelt)
    • makeCanonic

      protected boolean makeCanonic(CanonicalForm cnf)
      Make the fragment canonic (minimize the code word).
      Parameters:
      cnf - the canonical form
      Returns:
      whether the fragment was changed
      Since:
      2006.05.03 (Christian Borgelt)
    • makeCanonic

      protected boolean makeCanonic(CanonicalForm cnf, int keep)
      Make the fragment canonic (minimize the code word).

      In the process of trying to minimize the code word, the first keep edges of the fragment are left untouched. Hence the result may or may not be the overall minimal code word.

      Parameters:
      cnf - the canonical form
      keep - the number of edges to keep
      Returns:
      whether the fragment was changed
      Since:
      2006.05.03 (Christian Borgelt)
    • hasOrbits

      protected boolean hasOrbits()
      Check whether the fragment has node orbit identifiers.
      Returns:
      whether the fragment has node orbit identifiers
      Since:
      2011.02.21 (Christian Borgelt)
    • hasOpenRings

      protected boolean hasOpenRings(int min, int max)
      Check whether the fragment has open rings.
      Parameters:
      min - minimum ring size (number of nodes/edges)
      max - maximum ring size (number of nodes/edges)
      Returns:
      whether the fragment has open rings
      Since:
      2006.05.16 (Christian Borgelt)
    • hasUnclosableRings

      protected boolean hasUnclosableRings(CanonicalForm cnf)
      Check whether the fragment has unclosable rings.

      If the output is restricted to fragments containing only closed rings, the restricted extensions (as they can be derived from a canonical form) render certain nodes unextendable. If such an node has only one incident ring edge, the ring of which this edge is part cannot be closed by future extensions. Hence neither this fragment nor any of its extensions can produce output and thus it can be pruned.

      Parameters:
      cnf - the canonical form defining the unextendable nodes
      Returns:
      whether the fragment has unclosable rings
      Since:
      2006.05.16 (Christian Borgelt)
    • mergeExts

      protected int mergeExts(Fragment[] exts, int cnt)
      Merge ring extensions that have the same initial edge.

      This function does not work with packed embeddings lists due to ordering problems. However, the fact that the set of embeddings is reduced would also lead to a considerable loss of information if embeddings were discarded and recreated by reembedding.

      Parameters:
      exts - the array of ring extension fragments to merge
      cnt - the number of fragments to consider
      Returns:
      the number of fragments in exts after merging
      Since:
      2006.05.16 (Christian Borgelt)
    • adapt

      protected boolean adapt(CanonicalForm cnf, boolean check)
      Adapt the fragment (limited reordering of the edges and nodes).

      For full perfect extension pruning and for combining ring extensions with canonical form pruning it is necessary to allow for a (strictly limited) reorganization of a fragment (a certain reordering of the edges and nodes), so that certain edges, which may have be added in a wrong order (w.r.t. the canonical form), are brought into the proper order. The core idea is to split the list of edges into to parts: a fixed prefix part and a volatile suffix part. Only the volatile suffix part is adapted in this function.

      Parameters:
      cnf - the canonical form
      check - whether to check for a valid ring order
      Returns:
      whether the adaptation was successful
      Since:
      2006.04.11 (Christian Borgelt)
    • chainsValid

      protected boolean chainsValid()
      Check whether all variable length chains are valid.

      A variable length chain is valid if it actually represents chains of different length in the underlying graphs. If, however, a chain has the same length in all underlying graphs, it is not valid, as it could be represented explicitly.

      Returns:
      whether all variable length chains are valid
      Since:
      2006.11.03 (Christian Borgelt)
    • equalsCanonic

      public boolean equalsCanonic(Fragment frag)
      Compare the (canonical) code words of two fragments.

      This function determines whether the code words of two fragments (the fragment the function is called on and the argument fragment), as they are implicitly represented by the order of their nodes and edges, are equal.

      Parameters:
      frag - the fragment to compare to
      Returns:
      whether the (canonical) code words are equal
      Since:
      2011.02.18 (Christian Borgelt)
    • toString

      public String toString()
      Create a string description of the fragment.
      Overrides:
      toString in class Object
      Returns:
      a string description of the fragment
      Since:
      2002.03.14 (Christian Borgelt)
    • toString

      public String toString(Notation ntn)
      Create a string description of the fragment.
      Parameters:
      ntn - the notation to use for the description
      Returns:
      a string description of the fragment
      Since:
      2002.03.14 (Christian Borgelt)
    • toString

      public String toString(CanonicalForm cnf)
      Create the code word of the fragment.
      Parameters:
      cnf - the canonical form defining the code word form
      Returns:
      a string description of the code word
      Since:
      2006.05.10 (Christian Borgelt)
    • main

      public static void main(String[] args)
      Main function for testing some basic functionality.

      It is tried to parse the first two command line arguments as SMILES, SLN, or LiNoG descriptions of graph (in this order). If parsing suceeds, the second graph is embedded into the first and the number of embeddings is printed..

      Parameters:
      args - the command line arguments
      Since:
      2007.10.25 (Christian Borgelt)