public class Node extends java.lang.Object implements java.lang.Comparable<Node>
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.
Modifier and Type | Field and Description |
---|---|
static int |
CHAIN
the flag for a chain node (representing several equal nodes)
|
protected int |
deg
the current number of incident edges (node degree)
|
protected Edge[] |
edges
the array of incident edges (may not be fully used)
|
static int |
FLAGMASK
the mask for the node flags (wildcard and chain)
|
protected int |
mark
a marker for internal use (e.g.
|
protected int |
orbit
the representative of the orbit of the node
|
protected int |
type
the type (attribute/label) of a node (including flags)
|
static int |
TYPEMASK
the mask for the base type
|
static int |
WILDCARD
the special code for a wildcard type
|
Modifier | Constructor and 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.
|
Modifier and Type | Method and Description |
---|---|
protected void |
addEdge(Edge edge)
Add an edge to a node.
|
int |
compareTo(Node obj)
Compare two nodes (w.r.t.
|
void |
decode(Recoder coder)
Decode the node type.
|
void |
encode(Recoder coder)
Encode the node type.
|
int |
getBaseType()
Get the base type (attribute/label) of a node.
|
int |
getDegree()
Get the degree of the node.
|
Edge |
getEdge(int index)
Get an edge of the node.
|
int |
getType()
Get the full type (attribute/label) of a node.
|
boolean |
isChain()
Check whether this is a chain node.
|
boolean |
isSpecial()
Check whether this is a special node (wildcard or chain).
|
boolean |
isWildcard()
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 |
sortEdges()
Sort the edges that are incident to the node.
|
public static final int TYPEMASK
public static final int FLAGMASK
public static final int WILDCARD
public static final int CHAIN
protected int type
protected int mark
protected int orbit
protected int deg
protected Edge[] edges
protected Node(int type)
type
- the type of the node to createprotected Node(int type, int 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.
type
- the type of the node to createsize
- the expected number of edgespublic int getType()
public int getBaseType()
public void maskType(int mask)
mask
- the mask for the node typepublic boolean isSpecial()
public boolean isWildcard()
public boolean isChain()
public void encode(Recoder coder)
coder
- the recoder to encode the node type withpublic void decode(Recoder coder)
coder
- the recoder to decode the node type withpublic int getDegree()
protected void addEdge(Edge edge)
It is not checked whether the source or the destination of the edge coincide with this node (as it should be).
edge
- the edge to be added to the nodepublic Edge getEdge(int index)
index
- the index of the edge (w.r.t. the node)protected void opt()
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.
protected void mark(int mark)
mark
- the value with which to mark the nodespublic int compareTo(Node obj)
This function is needed in NamedGraph.split()
(indirectly through Arrays.sort()).
compareTo
in interface java.lang.Comparable<Node>
obj
- the node to compare to-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 argumentprotected void sortEdges()
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.