Package moss

Class Node

java.lang.Object
moss.Node
All Implemented Interfaces:
Serializable, Comparable<Node>

public class Node extends Object implements Comparable<Node>, Serializable
Class for nodes of an attributed (labeled/typed) graph.

A node records its type (attribute/label) and all edges that are incident to it in the graph it is part of.

Note that only 30 bits are actually available for the type of the node. The two most significant bits are reserved as flags for special purposes, for example, for marking chain nodes.

Since:
2002.03.11
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    the flag for a chain node (representing several equal nodes)
    protected int
    the current number of incident edges (node degree)
    protected Edge[]
    the array of incident edges (may not be fully used)
    static final int
    the mask for the node flags (wildcard and chain)
    protected int
    a marker for internal use (e.g.
    protected int
    the representative of the orbit of the node
    protected int
    the type (attribute/label) of a node (including flags)
    static final int
    the mask for the base type
    static final int
    the special code for a wildcard type
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Node(int type)
    Create a node with a given type (attribute/label).
    protected
    Node(int type, int size)
    Create a node of a given type and given edge array size.
  • Method Summary

    Modifier and Type
    Method
    Description
    protected void
    addEdge(Edge edge)
    Add an edge to a node.
    int
    Compare two nodes (w.r.t.
    void
    decode(Recoder coder)
    Decode the node type.
    void
    encode(Recoder coder)
    Encode the node type.
    int
    Get the base type (attribute/label) of a node.
    int
    Get the degree of the node.
    getEdge(int index)
    Get an edge of the node.
    int
    Get the full type (attribute/label) of a node.
    boolean
    Check whether this is a chain node.
    boolean
    Check whether this is a special node (wildcard or chain).
    boolean
    Check whether this is a wildcard node.
    protected void
    mark(int mark)
    Recursive function to mark a connected component.
    void
    maskType(int mask)
    Mask the edge type with the given mask.
    protected void
    opt()
    Optimize memory usage.
    protected void
    Sort the edges that are incident to the node.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • TYPEMASK

      public static final int TYPEMASK
      the mask for the base type
      See Also:
    • FLAGMASK

      public static final int FLAGMASK
      the mask for the node flags (wildcard and chain)
      See Also:
    • WILDCARD

      public static final int WILDCARD
      the special code for a wildcard type
      See Also:
    • CHAIN

      public static final int CHAIN
      the flag for a chain node (representing several equal nodes)
      See Also:
    • type

      protected int type
      the type (attribute/label) of a node (including flags)
    • mark

      protected int mark
      a marker for internal use (e.g. for a substructure)
    • orbit

      protected int orbit
      the representative of the orbit of the node
    • deg

      protected int deg
      the current number of incident edges (node degree)
    • edges

      protected Edge[] edges
      the array of incident edges (may not be fully used)
  • Constructor Details

    • Node

      protected Node(int type)
      Create a node with a given type (attribute/label).
      Parameters:
      type - the type of the node to create
      Since:
      2002.03.11 (Christian Borgelt)
    • Node

      protected Node(int type, int size)
      Create a node of a given type and given edge array size.

      The node is created in such a way that it can accomodate references to deg edges. Nevertheless more edges may be added later. The parameter only serves the purpose to set the proper size if it is already known in advance.

      Parameters:
      type - the type of the node to create
      size - the expected number of edges
      Since:
      2002.03.11 (Christian Borgelt)
  • Method Details

    • getType

      public int getType()
      Get the full type (attribute/label) of a node.
      Returns:
      the type of the node
      Since:
      2002.03.11 (Christian Borgelt)
    • getBaseType

      public int getBaseType()
      Get the base type (attribute/label) of a node.
      Returns:
      the type of the node
      Since:
      2009.08.13 (Christian Borgelt)
    • maskType

      public void maskType(int mask)
      Mask the edge type with the given mask.
      Parameters:
      mask - the mask for the node type
      Since:
      2002.03.11 (Christian Borgelt)
    • isSpecial

      public boolean isSpecial()
      Check whether this is a special node (wildcard or chain).
      Returns:
      whether this is a special node
      Since:
      2006.10.31 (Christian Borgelt)
    • isWildcard

      public boolean isWildcard()
      Check whether this is a wildcard node.
      Returns:
      whether this is a wildcard node
      Since:
      2007.06.25 (Christian Borgelt)
    • isChain

      public boolean isChain()
      Check whether this is a chain node.
      Returns:
      whether this is a chain node
      Since:
      2006.10.31 (Christian Borgelt)
    • encode

      public void encode(Recoder coder)
      Encode the node type.
      Parameters:
      coder - the recoder to encode the node type with
      Since:
      2006.11.16 (Christian Borgelt)
    • decode

      public void decode(Recoder coder)
      Decode the node type.
      Parameters:
      coder - the recoder to decode the node type with
      Since:
      2006.11.16 (Christian Borgelt)
    • getDegree

      public int getDegree()
      Get the degree of the node.
      Returns:
      the degree of the node
      Since:
      2007.11.05 (Christian Borgelt)
    • addEdge

      protected void addEdge(Edge edge)
      Add an edge to a node.

      It is not checked whether the source or the destination of the edge coincide with this node (as it should be).

      Parameters:
      edge - the edge to be added to the node
      Since:
      2002.03.11 (Christian Borgelt)
    • getEdge

      public Edge getEdge(int index)
      Get an edge of the node.
      Parameters:
      index - the index of the edge (w.r.t. the node)
      Returns:
      the edge with the given index
      Since:
      2007.11.05 (Christian Borgelt)
    • opt

      protected void opt()
      Optimize memory usage.

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

      Since:
      2002.03.11 (Christian Borgelt)
    • mark

      protected void mark(int mark)
      Recursive function to mark a connected component.
      Parameters:
      mark - the value with which to mark the nodes
      Since:
      2007.03.23 (Christian Borgelt)
    • compareTo

      public int compareTo(Node obj)
      Compare two nodes (w.r.t. their marker values).

      This function is needed in NamedGraph.split() (indirectly through Arrays.sort()).

      Specified by:
      compareTo in interface Comparable<Node>
      Parameters:
      obj - the node to compare to
      Returns:
      the sign of the difference of the node markers, that is, -1, 0, or +1 as the marker of this node is less than, equal to, or greater than the marker of the node given as an argument
      Since:
      2007.06.14 (Christian Borgelt)
    • sortEdges

      protected void sortEdges()
      Sort the edges that are incident to the node.

      The edges are sorted w.r.t. their type, the type of the node they lead to, and the marker of the edge. This order is exploited in several functions to terminate loops early (by removing the need to check all edges that are incident to a node).

      Since in normal molecules there should be no more than four edges, insertion sort is the fastest method. However, for more than 12 edges the standard function Arrays.sort() is used, so that it is reasonably fast for general graphs.

      Since:
      2002.03.11 (Christian Borgelt)