Package moss

Class Graph

java.lang.Object
moss.Graph
All Implemented Interfaces:
Serializable, Cloneable
Direct Known Subclasses:
NamedGraph

public class Graph extends Object implements Cloneable, Serializable
Class to represent attributed graphs for substructure mining.

An attributed graph is stored as an array of nodes and an array of edges. There is an optional recoder by which the node types may be mapped to other codes to speed up processing.

Since:
2002.03.11
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected Recoder
    an optional node type recoder
    protected boolean
    whether the graph is directed
    protected int
    the current number of edges (may be smaller than the array length)
    protected Edge[]
    the array of edges (may be only partially used)
    protected int
    the current number of nodes (may be smaller than the array length)
    protected Node[]
    the array of nodes (may be only partially used)
    protected Notation
    the notation for describing the graph
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Create/Initialize an empty graph.
    protected
    Turn a fragment into a graph.
    protected
    Graph(Graph graph)
    Create a clone of a graph.
    protected
    Graph(Graph graph, int src, int dst, int edge, int node, boolean reversed)
    Create an extended graph (extended by one edge).
     
    Create a (empty) graph with default array sizes.
     
    Graph(Notation ntn, int nodecnt, int edgecnt)
    Create a (empty) graph with the given array sizes.
     
    Graph(Notation ntn, int nodecnt, int edgecnt, boolean dir)
    Create a (empty) graph with the given array sizes.
     
    Graph(Notation ntn, Recoder coder)
    Create a (empty) graph with default array sizes.
     
    Graph(Notation ntn, Recoder coder, boolean dir)
    Create a (empty) graph with default array sizes.
     
    Graph(Notation ntn, Recoder coder, int nodecnt, int edgecnt)
    Create a (empty) graph with the given array sizes.
     
    Graph(Notation ntn, Recoder coder, int nodecnt, int edgecnt, boolean dir)
    Create a (empty) graph with the given array sizes.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    addEdge(int src, int dst, int type)
    Add an edge to the graph.
    int
    addNode(int type)
    Add a node to the graph, encode type if needed.
    int
    addNodeRaw(int type)
    Add a node to the graph, do not encode the type.
    void
    Clear a graph (remove all nodes and edges).
    Create a clone of the graph.
    protected boolean
    contains(int type)
    Check whether a node type is contained in this graph.
    boolean
    contains(Graph graph)
    Check whether a graph is contained in this graph.
    void
    Decode the node types.
    protected Embedding
    embed(int type)
    Embed a single node into the graph.
    embed(Graph graph)
    Embed a graph structure (find all its embeddings).
    void
    encode(Recoder coder)
    Encode the node types with the given type recoder.
    boolean
    equals(Object graph)
    Check whether another graph is equal to this graph.
    boolean
    Compare the (canonical) code words of two graphs.
    getEdge(int index)
    Get an edge by its index.
    int
    Get the number of edges of the graph.
    int
    getEdgeMark(int index)
    Get the marker of an edge.
    Get the edge type manager of the graph.
    getEdgeName(int index)
    Get the name of an edge.
    int
    getEdgeType(int index)
    Get the type of an edge.
    getNode(int index)
    Get a node by its index.
    int
    Get the number of nodes of the graph.
    int
    getNodeMark(int index)
    Get the marker of a node.
    Get the node type manager of the graph.
    getNodeName(int index)
    Get the name of a node.
    int
    getNodeType(int index)
    Get the type of a node.
    int
    getNodeTypeRaw(int index)
    Get the type of a node.
    Get the notation of the graph.
    Get the recoder for the node types.
    int
    Compute the hash code of the attributed graph.
    boolean
    hasOpenRings(int min, int max)
    Check whether this subgraph has open rings.
    protected void
    Mark all nodes and edges with their index.
    boolean
    Check whether a graph is canonic w.r.t.
    protected int
    isCanonic(CanonicalForm cnf, int fixed)
    Check whether a graph is canonic w.r.t.
    boolean
    Check whether the graph is connected.
    static void
    main(String[] args)
    Main function for testing some basic functionality.
    boolean
    Make a graph canonic w.r.t.
    protected boolean
    makeCanonic(CanonicalForm cnf, int keep)
    Make a graph canonic w.r.t.
    protected void
    Reorganize a graph with a map from a canonical form.
    protected void
    mark(int mark)
    Mark all nodes and edges with a given value.
    int
    Mark all edges that are bridges.
    Embed a graph structure (mark one of its embeddings).
    protected int
    markPseudo(int max)
    Mark pseudo-rings up to a given size.
    int
    markRings(int min, int max)
    Mark rings in a given size range.
    protected int
    markRings(int min, int max, int typeflag)
    Mark rings in a given size range with a given type flag.
    void
    maskTypes(int[] masks)
    Mask the node and edge types.
    void
    Normalize a graph w.r.t.
    protected void
    opt()
    Optimize memory usage.
    void
    Prepare a graph for frequent substructure mining.
    boolean
    Prepare a graph for embedding it into another.
    boolean
    Check whether the graph is simple.
    Create a string description of the graph.
    Create a code word for a given canonical form.
    Create a string description in the given notation.
    protected boolean
    trim(boolean remove)
    Trim a graph based on its encoding recoder.

    Methods inherited from class java.lang.Object

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

    • dir

      protected boolean dir
      whether the graph is directed
    • nodes

      protected Node[] nodes
      the array of nodes (may be only partially used)
    • nodecnt

      protected int nodecnt
      the current number of nodes (may be smaller than the array length)
    • edges

      protected Edge[] edges
      the array of edges (may be only partially used)
    • edgecnt

      protected int edgecnt
      the current number of edges (may be smaller than the array length)
    • coder

      protected Recoder coder
      an optional node type recoder
    • ntn

      protected Notation ntn
      the notation for describing the graph
  • Constructor Details

    • Graph

      protected Graph()
      Create/Initialize an empty graph.

      This constructor is needed internally for turning graphs into named graphs.

      Since:
      2007.06.29 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn)
      Create a (empty) graph with default array sizes.
      Parameters:
      ntn - the notation of the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, Recoder coder)
      Create a (empty) graph with default array sizes.
      Parameters:
      ntn - the notation of the graph
      coder - the node type recoder of the graph
      Since:
      2010.01.21 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, Recoder coder, boolean dir)
      Create a (empty) graph with default array sizes.
      Parameters:
      ntn - the notation of the graph
      coder - the node type recoder of the graph
      dir - whether the graph is directed
      Since:
      2021.10.07 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, int nodecnt, int edgecnt)
      Create a (empty) graph with the given array sizes.

      The graph is created in such a way that it can contain, without resizing any arrays, nodecnt nodes and edgecnt edges. Nevertheless more nodes and edges may be added later. The parameters only serve the purpose to set the proper sizes if they are already known in advance.

      Parameters:
      ntn - the notation of the graph
      nodecnt - the expected number of nodes
      edgecnt - the expected number of edges
      Since:
      2002.03.11 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, int nodecnt, int edgecnt, boolean dir)
      Create a (empty) graph with the given array sizes.

      The graph is created in such a way that it can contain, without resizing any arrays, nodecnt nodes and edgecnt edges. Nevertheless more nodes and edges may be added later. The parameters only serve the purpose to set the proper sizes if they are already known in advance.

      Parameters:
      ntn - the notation of the graph
      nodecnt - the expected number of nodes
      edgecnt - the expected number of edges
      dir - whether the graph is directed
      Since:
      2022.09.27 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, Recoder coder, int nodecnt, int edgecnt)
      Create a (empty) graph with the given array sizes.

      The graph is created in such a way that it can contain, without resizing any arrays, nodecnt nodes and edgecnt edges. Nevertheless more nodes and edges may be added later. The parameters only serve the purpose to set the proper sizes if they are already known in advance.

      Parameters:
      ntn - the notation of the graph
      coder - the node type recoder of the graph
      nodecnt - the expected number of nodes
      edgecnt - the expected number of edges
      Since:
      2002.03.11 (Christian Borgelt)
    • Graph

      public Graph(Notation ntn, Recoder coder, int nodecnt, int edgecnt, boolean dir)
      Create a (empty) graph with the given array sizes.

      The graph is created in such a way that it can contain, without resizing any arrays, nodecnt nodes and edgecnt edges. Nevertheless more nodes and edges may be added later. The parameters only serve the purpose to set the proper sizes if they are already known in advance.

      Parameters:
      ntn - the notation of the graph
      coder - the node type recoder of the graph
      nodecnt - the expected number of nodes
      edgecnt - the expected number of edges
      dir - whether the graph is directed
      Since:
      2010.01.21/2002.03.11 (Christian Borgelt)
    • Graph

      protected Graph(Graph graph)
      Create a clone of a graph.

      This function creates a clone without changing anything in the original graph (not even the node markers, which are only changed temporarily and restored on completion).

      Parameters:
      graph - the graph to clone
      Since:
      2003.08.04 (Christian Borgelt)
    • Graph

      protected Graph(Graph graph, int src, int dst, int edge, int node, boolean reversed)
      Create an extended graph (extended by one edge).

      This function creates a clone without changing anything in the original graph (not even the node markers, which are only changed temporarily and restored on completion).

      Parameters:
      graph - the graph to clone
      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 is reversed
      Since:
      2010.01.23/2003.08.04 (Christian Borgelt)
    • Graph

      protected Graph(Fragment frag)
      Turn a fragment into a graph.

      This function is needed for unembedding/reembedding and the functions isCanonic() and makeCanonic() in the class Fragment. Turning a fragment into a graph does not change anything in any underlying graph (not even the node markers, which are only changed temporarily in one underlying graph and restored on completion).

      Parameters:
      frag - the fragment to turn into a graph
      Since:
      2002.03.11 (Christian Borgelt)
  • Method Details

    • clone

      public Object clone()
      Create a clone of the graph.

      This function simply returns new Graph(this). It is intended mainly for debugging purposes.

      Overrides:
      clone in class Object
      Returns:
      a clone of this graph
      Since:
      2006.10.23 (Christian Borgelt)
      See Also:
    • clear

      public void clear()
      Clear a graph (remove all nodes and edges).
      Since:
      2007.06.22 (Christian Borgelt)
    • equals

      public boolean equals(Object graph)
      Check whether another graph is equal to this graph.

      For this function to work properly, the argument graph must either have been processed with the function prepareEmbed(), or it must have been created from a fragment that itself was generated in the search process, so that the edges are sorted in a specific way (so that source nodes are always already numbered). In addition, the graph to which the argument graph is compared (object on which this function is called) must be prepared by calling the function prepare() on it.

      Overrides:
      equals in class Object
      Parameters:
      graph - the graph to compare to
      Returns:
      whether the given graph is equal to this graph
      Since:
      2006.11.02 (Christian Borgelt)
      See Also:
    • hashCode

      public int hashCode()
      Compute the hash code of the attributed graph.

      For subgraphs this function should yield the same value as the corresponding function Embedding.hashCode().

      Note that the hash value of a graph changes when the node types are encoded with a Recoder.

      Overrides:
      hashCode in class Object
      Returns:
      the hash code of the graph
      Since:
      2006.11.02 (Christian Borgelt)
    • getNotation

      public Notation getNotation()
      Get the notation of the graph.
      Returns:
      the notation of the graph
      Since:
      2007.06.29 (Christian Borgelt)
    • getNodeMgr

      public TypeMgr getNodeMgr()
      Get the node type manager of the graph.
      Returns:
      the node type manager of the graph
      Since:
      2007.06.30 (Christian Borgelt)
    • getEdgeMgr

      public TypeMgr getEdgeMgr()
      Get the edge type manager of the graph.
      Returns:
      the edge type manager of the graph
      Since:
      2007.06.30 (Christian Borgelt)
    • getRecoder

      public Recoder getRecoder()
      Get the recoder for the node types.
      Returns:
      the recoder currently used for the node types, or null if no recoder is used
      Since:
      2006.06.28 (Christian Borgelt)
      See Also:
    • addNodeRaw

      public int addNodeRaw(int type)
      Add a node to the graph, do not encode the type.

      Even if the graph contains a node type recoder, the node type is stored exactly as it is given.

      Parameters:
      type - the type of the node to add
      Returns:
      the index of the node in the graph
      Since:
      2002.03.11 (Christian Borgelt)
      See Also:
    • addNode

      public int addNode(int type)
      Add a node to the graph, encode type if needed.

      If the graph contains a node type recoder, the given node type is automatically encoded with it.

      Parameters:
      type - the type of the node to add
      Returns:
      the index of the node in the graph
      Since:
      2010.01.19 (Christian Borgelt)
      See Also:
    • getNodeCount

      public int getNodeCount()
      Get the number of nodes of the graph.
      Returns:
      the number of nodes of the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • getNode

      public Node getNode(int index)
      Get a node by its index.
      Parameters:
      index - the index of the node to retrieve
      Returns:
      the index-th node of the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • getNodeType

      public int getNodeType(int index)
      Get the type of a node.

      If the graph contains a recoder for the node types, the node type is automatically decoded.

      Parameters:
      index - the index of the node
      Returns:
      the type of the index-th node of the graph
      Since:
      2007.06.20 (Christian Borgelt)
      See Also:
    • getNodeTypeRaw

      public int getNodeTypeRaw(int index)
      Get the type of a node.

      Even if the graph contains a recoder for the node types, the node type is not decoded, but returned as it is stored.

      Parameters:
      index - the index of the node
      Returns:
      the type of the index-th node of the graph
      Since:
      2010.01.19 (Christian Borgelt)
      See Also:
    • getNodeMark

      public int getNodeMark(int index)
      Get the marker of a node.
      Parameters:
      index - the index of the node
      Returns:
      the marker of the index-th node of the graph
      Since:
      2020.10.04 (Christian Borgelt)
    • getNodeName

      public String getNodeName(int index)
      Get the name of a node.

      If the graph contains a recoder for the node types, the node type is automatically decoded. Then the node name is retrieved from the node type manager of the notation.

      Parameters:
      index - the index of the node
      Returns:
      the name of the index-th node of the graph
      Since:
      2020.10.04 (Christian Borgelt)
    • addEdge

      public int addEdge(int src, int dst, int type)
      Add an edge to the graph.
      Parameters:
      src - the index of the source node of the edge
      dst - the index of the destination node of the edge
      type - the type of the edge to add
      Returns:
      the index of the edge in the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • getEdgeCount

      public int getEdgeCount()
      Get the number of edges of the graph.
      Returns:
      the number of edges of the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • getEdge

      public Edge getEdge(int index)
      Get an edge by its index.
      Parameters:
      index - the index of the edge to retrieve
      Returns:
      the index-th edge of the graph
      Since:
      2002.03.11 (Christian Borgelt)
    • getEdgeType

      public int getEdgeType(int index)
      Get the type of an edge.

      Since edge types are currently not encoded, there is no need to distinguish getEdgeType and getEdgeTypeRaw.

      Parameters:
      index - the index of the edge
      Returns:
      the type of the index-th edge of the graph
      Since:
      2007.06.20 (Christian Borgelt)
    • getEdgeMark

      public int getEdgeMark(int index)
      Get the marker of an edge.
      Parameters:
      index - the index of the edge
      Returns:
      the marker of the index-th edge of the graph
      Since:
      2020.10.04 (Christian Borgelt)
    • getEdgeName

      public String getEdgeName(int index)
      Get the name of an edge.

      Then the edge name is retrieved from the edge type manager of the notation.

      .
      Parameters:
      index - the index of the edge
      Returns:
      the name of the index-th edge of the graph
      Since:
      2020.10.04 (Christian Borgelt)
    • opt

      protected void opt()
      Optimize memory usage.

      This function shrinks the node array and the edge array to the minimal size that is necessary to hold the current number of nodes and edges and thus tries to reduce the memory consumption.

      Since:
      2002.03.11 (Christian Borgelt)
    • mark

      protected void mark(int mark)
      Mark all nodes and edges with a given value.
      Parameters:
      mark - the value with which to mark nodes and edges.
      Since:
      2002.04.14 (Christian Borgelt)
    • index

      protected void index()
      Mark all nodes and edges with their index.
      Since:
      2002.04.14 (Christian Borgelt)
    • simple

      public boolean simple()
      Check whether the graph is simple.

      In a simple graph any two node are connected by at most one edge, not multiple edges.

      This function indexes the nodes of the graph.

      Returns:
      whether the graph is simple
      Since:
      2021.10.06 (Christian Borgelt)
    • encode

      public void encode(Recoder coder)
      Encode the node types with the given type recoder.

      The given type recoder is stored in the graph and may be retrieved with the function getRecoder().

      Parameters:
      coder - the type recoder to use
      Since:
      2005.06.21 (Christian Borgelt)
      See Also:
    • decode

      public void decode()
      Decode the node types.

      Calling this function has no effect if the nodes have not been encoded with Graph.encode() before. Otherwise the original types of the nodes are restored and the stored recoder is removed.

      Since:
      2005.06.21 (Christian Borgelt)
      See Also:
    • maskTypes

      public void maskTypes(int[] masks)
      Mask the node and edge types.

      The types of all nodes and edges of the graph are logically anded with the masks in a given array of masks.

      Parameters:
      masks - an array with 4 elements, which refer to
      0: nodes outside rings
      1: edges outside rings
      2: nodes in rings
      3: edges in rings
      Since:
      2005.07.20 (Christian Borgelt)
    • trim

      protected boolean trim(boolean remove)
      Trim a graph based on its encoding recoder.

      All nodes with types that are marked as excluded (in the recoder used to encode the node types) as well as all incident edges are removed. Removal consists in specifically marking these nodes and edges if the parameter remove is false. Only if this parameter is true, the nodes and edges are actually removed from the graph.

      Parameters:
      remove - whether the nodes and edges are actually to be removed (true) or only to be marked (false)
      Returns:
      whether nodes were removed in the trimming process
      Since:
      2005.07.22 (Christian Borgelt)
    • isConnected

      public boolean isConnected()
      Check whether the graph is connected.
      Returns:
      whether the graph is connected.
      Since:
      2007.03.23 (Christian Borgelt)
    • markBridges

      public int markBridges()
      Mark all edges that are bridges.

      This function marks all edges, the removal of which increases the number of connected components of the graph (bridges).
      The bridge finding algorithm employed here is adapted from:
      R.E. Tarjan.
      Depth-First Search and Linear Graph Algorithms.
      SIAM Journal of Computing 1(2):146--160.
      Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 1972

      Returns:
      the number of edges that have been marked
      Since:
      2005.06.07 (Christian Borgelt)
    • markRings

      public int markRings(int min, int max)
      Mark rings in a given size range.

      This function marks all edges and nodes that are part of a ring in the given size range with a default type flag.

      If not all rings could be marked (because there is an edge that is part of more rings than there are possible rings flags), the return value is negative (but its absolute value nevertheless is the number of rings that have been marked).

      Parameters:
      min - the smallest ring size (number of edges/nodes)
      max - the largest ring size (number of edges/nodes)
      Returns:
      the number of rings that have been marked (negative if not all rings could be marked)
      Since:
      2003.07.31 (Christian Borgelt)
    • markRings

      protected int markRings(int min, int max, int typeflag)
      Mark rings in a given size range with a given type flag.

      This function marks all edges and nodes that are part of a ring in the given size range with the given type flag. If the ring should not be marked in the type (or an existing type flag should be kept) and only the rings flags of the edges should be set, this function may be called with typeflag == 0.

      Parameters:
      min - the smallest ring size (number of edges/nodes)
      max - the largest ring size (number of edges/nodes)
      typeflag - the type flag to use for marking
      Returns:
      the number of rings that have been marked
      Since:
      2003.07.31 (Christian Borgelt)
    • markPseudo

      protected int markPseudo(int max)
      Mark pseudo-rings up to a given size.

      Pseudo-rings are rings that are smaller than the rings marked with the function markRings() (which must have been called before) and consist only of already marked ring edges. They are needed for a proper treatment of rings in connection with canonical form pruning.

      Parameters:
      max - the maximal size of a pseudo-ring
      Returns:
      the number of marked pseudo-rings
      Since:
      2006.06.04 (Christian Borgelt)
    • hasOpenRings

      public boolean hasOpenRings(int min, int max)
      Check whether this subgraph has open rings.

      This function checks whether there are edges in this subgraph that are part of a ring in the underlying graphs, but is not part of a ring in this subgraph. It is used for filtering if only substructures with complete rings are desired.

      Parameters:
      min - the smallest ring size (number of edges/nodes)
      max - the largest ring size (number of edges/nodes)
      Returns:
      whether the subgraph contains an open ring
      Since:
      2006.05.16 (Christian Borgelt)
    • prepare

      public void prepare()
      Prepare a graph for frequent substructure mining.

      This function sorts the edges for each node w.r.t. their type and the type of the other incident node. This is necessary for seed embedding and frequent substructure mining, because the order of the edges is exploited to simplify and restrict the search (search tree pruning, leaving loops early).

      Since:
      2002.03.21 (Christian Borgelt)
    • prepareEmbed

      public boolean prepareEmbed()
      Prepare a graph for embedding it into another.

      For this function to work properly, the graph must be connected (a single connected component). It is prepared by sorting the edges of all nodes and by reordering the nodes and edges into a breadth-first search order (to simplify the embedding).

      This function is not called in embed(), so that a graph that has to be embedded into several other graphs is not prepared in this way over and over again.

      Returns:
      whether the graph is connected (and thus preparation succeeded)
      Since:
      2002.03.21 (Christian Borgelt)
    • embed

      protected Embedding embed(int type)
      Embed a single node into the graph.
      Parameters:
      type - the type of the node to embed
      Returns:
      a list of embeddings of the node
      Since:
      2002.03.11 (Christian Borgelt)
    • embed

      public Embedding embed(Graph graph)
      Embed a graph structure (find all its embeddings).

      This function embeds a given graph in all possible ways and returns a list of all found embeddings. For this function to work properly, the graph to embed must either have been processed with the function prepareEmbed(), or it must have been created from a fragment that itself was generated in the search process (class Miner), so that the edges are sorted in a specific way (so that source nodes are always already numbered). In addition, the graph into which to embed must be prepared by calling the function prepare() on it.

      Parameters:
      graph - the graph to embed
      Returns:
      a list of all embeddings of the graph
      Since:
      2002.03.21 (Christian Borgelt)
    • markEmbed

      public Embedding markEmbed(Graph graph)
      Embed a graph structure (mark one of its embeddings).

      This function embeds a given graph in one possible way and and marks the corresponding embedding (if one exists). For this function to work properly, the graph to embed must either have been processed with the function prepareEmbed(), or it must have been created from a fragment that itself was generated in the search process (class Miner), so that the edges are sorted in a specific way (so that source nodes are always already numbered). In addition, the graph into which to embed must be prepared by calling the function prepare() on it.

      Parameters:
      graph - the graph to embed
      Returns:
      the constant CONTAINED or null
      Since:
      2020.10.03 (Christian Borgelt)
    • contains

      protected boolean contains(int type)
      Check whether a node type is contained in this graph.
      Parameters:
      type - the type of the node to check for
      Returns:
      a list of embeddings of the node
      Since:
      2010.01.21 (Christian Borgelt)
    • contains

      public boolean contains(Graph graph)
      Check whether a graph is contained in this graph.

      This function tries to embed a given graph and returns as soon as one embedding is found (in contrast to the function embed(Graph), which tries to find all embeddings). For this function to work properly, the graph to embed must either have been processed with the function prepareEmbed(), or it must have been created from a fragment that itself was generated in the search process, so that the edges are sorted in a specific way (so that source nodes are always already numbered). In addition, the graph into which to embed the argument graph must be prepared by calling the function prepare() on it.

      Parameters:
      graph - the graph to embed
      Returns:
      whether the given graph is contained in this graph
      Since:
      2002.03.21 (Christian Borgelt)
      See Also:
    • isCanonic

      public boolean isCanonic(CanonicalForm cnf)
      Check whether a graph is canonic w.r.t. a given canonical form.

      This function checks whether the current order of the nodes and edges of the graph yields the smallest code word w.r.t. the canonical form that is specified by a given canonical form.

      Parameters:
      cnf - the canonical form
      Returns:
      whether the graph is canonical
      Since:
      2006.05.03 (Christian Borgelt)
    • isCanonic

      protected int isCanonic(CanonicalForm cnf, int fixed)
      Check whether a graph is canonic w.r.t. a given canonical form.
      Parameters:
      cnf - the canonical form
      fixed - the number of fixed edges
      Returns:
      whether the graph is canonic -1, if the graph differs from the canonical form in the first fixed edges, 0, if it is not canonical, but does not differ in the first fixed edges, +1, if the graph is canonical.
      Since:
      2006.05.03 (Christian Borgelt)
    • makeCanonic

      public boolean makeCanonic(CanonicalForm cnf)
      Make a graph canonic w.r.t. a given canonical form.

      This function brings the nodes and edges of the graph into the order that yields the smallest code word w.r.t. a given canonical form.

      Parameters:
      cnf - the extension object defining the canonical form
      Returns:
      whether the graph was modified
      Since:
      2006.05.03 (Christian Borgelt)
    • makeCanonic

      protected boolean makeCanonic(CanonicalForm cnf, int keep)
      Make a graph canonic w.r.t. a given canonical form.

      This function brings the nodes and edges of the graph into the order that yields the smallest code word w.r.t. the canonical form that is specified by a given extension object. However, the first keep edges as well as the nodes incident to these edges are not moved. Hence the result may not be in canonical form, but may differ in these first keep edges from the canonical form.

      Parameters:
      cnf - the canonical form
      keep - the number of edges to keep at the beginning of the graph/code word
      Returns:
      whether the graph was modified
      Since:
      2006.05.03 (Christian Borgelt)
    • normalize

      public void normalize(CanonicalForm cnf)
      Normalize a graph w.r.t. a given canonical form.

      This function brings the nodes and edges of the graph into the order that yields the smallest code word w.r.t. a given canonical form. It also sorts all edges per node accordingly, so that the output (in basically any notation) is unique.

      Parameters:
      cnf - the canonical form
      Since:
      2007.03.19 (Christian Borgelt)
    • map

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

      This function carries out the reordering that was determined with one of the functions CanonicalForm.makeCanonic() or CanonicalForm.adaptRing() and was stored in internal arrays of the canonical form.

      Parameters:
      cnf - the canonical form providing the map
      Since:
      2006.10.24 (Christian Borgelt)
    • equalsCanonic

      public boolean equalsCanonic(Graph graph)
      Compare the (canonical) code words of two graphs.

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

      This function is equivalent to equals(Object) provided the two graphs compared have both been made canonical with the function makeCanonic(CanonicalForm). The function is independent of the used canonical form, because it only checks for equality and not for an order relationship of the code words.

      Parameters:
      graph - the graph 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 graph.
      Overrides:
      toString in class Object
      Returns:
      a string description of the graph
      Since:
      2006.10.24 (Christian Borgelt)
    • toString

      public String toString(Notation ntn)
      Create a string description in the given notation.
      Parameters:
      ntn - the notation in which to create the description
      Returns:
      a string description of the graph
      Since:
      2007.06.29 (Christian Borgelt)
    • toString

      public String toString(CanonicalForm cnf)
      Create a code word for a given canonical form.

      The code word is created in the form prescribed by the given canonical form. However, it need not be the canonical code word for this graph, since it uses the current order of the nodes and edges of the graph. In order to obtain the canonical code word, the graph first has to be made canonic by calling the function makeCanonic(CanonicalForm) on it.

      Parameters:
      cnf - the canonical form
      Returns:
      a code word for the given canonical form
      Since:
      2006.05.08 (Christian Borgelt)
    • main

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

      It is tried to parse the first command line argument as a SMILES, SLN, or LiNoG description of a graph (in this order). If parsing suceeds, the graph is normalized and printed together with its breadth-first and depth-first spanning tree canonical code words.

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