Class Embedding
- All Implemented Interfaces:
Serializable
An embedding of a substructure is represented by referring to the nodes and edges of a graph, namely by simply listing the nodes and edges (from the graph) that form the substructure. An embedding must contain at least one node, i.e., it cannot be empty. It need not contain any edges, though.
If the edges array has a positive length, then usually
edges[edges.length-1]
contains the edge added last
(perfect extensions and ring extensions may lead to exceptions
from this rule, especially after adaptation).
The nodes in the nodes array are usually sorted in the order in which they have been added in the extension process (perfect extensions and ring extensions may lead to exceptions from this rule, especially after adaptation).
- Since:
- 2002.03.11
- See Also:
-
Field Summary
Fields -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
Dummy constructor.protected
Embedding
(CanonicalForm cnf) Create an embedding from a canonical form.protected
Extend a given embedding with a given edge.protected
Create a single node embedding.protected
Create an embedding from node and edge references. -
Method Summary
Modifier and TypeMethodDescriptionprotected int
Find the (maximum) length of a common edge array prefix.boolean
Check whether two embeddings are equal.protected Embedding
extend
(int src, int dst, int edge, int node) Create all extensions of a given type of this embedding.protected int
getGroup()
Get the group of the underlying graph.int
hashCode()
Compute the hash code of the subgraph described by the embedding.protected void
index()
Mark all nodes and edges with their index.static void
Main function for testing the overlap functions.protected void
mark
(int mark) Mark all nodes and edges with a given value.protected boolean
Check whether this embedding overlaps another.protected boolean
Check whether this embedding overlaps another.protected boolean
Check whether this embedding overlaps another harmfully.
-
Field Details
-
succ
the next embedding in a list of embeddings -
graph
the graph referred to -
nodes
the array of nodes (only references to the underlying graph) -
edges
the array of edges (only references to the underlying graph)
-
-
Constructor Details
-
Embedding
protected Embedding()Dummy constructor.This constructor is only needed to create the dummy object
CONTAINED
in the classGraph
, which is used as a special parameter and as a special return value for the functionGraph.embed()
in order to save a recursion parameter.- Since:
- 2006.08.28 (Christian Borgelt)
-
Embedding
Create a single node embedding.The node referred to is given by its index in the graph. The edges array is initialized to an array of zero size (not
null
).- Parameters:
graph
- the graph into which to embedindex
- the index of the node in the graph- Since:
- 2002.03.11 (Christian Borgelt)
-
Embedding
Create an embedding from node and edge references.This function is used when embedding a seed structure. The given node and edge arrays are copied.
- Parameters:
graph
- the graph referred tonodes
- the nodes of the substructureedges
- the edges of the substructure- Since:
- 2002.03.11 (Christian Borgelt)
-
Embedding
Create an embedding from a canonical form.This function is called if a created extension is only needed as an embedding (in contrast to a fragment).
- Parameters:
cnf
- the canonical form holding the extension- Since:
- 2002.03.11 (Christian Borgelt)
-
Embedding
Extend a given embedding with a given edge.This function assumes that the nodes of the embedding to extend are marked (with non-negative values) in the underlying graph. It is only needed for
Embedding.extend()
.- Parameters:
emb
- the embedding to extendedge
- the edge by which to extend the embedding- Since:
- 2002.03.11 (Christian Borgelt)
- See Also:
-
-
Method Details
-
equals
Check whether two embeddings are equal.This method is overridden only to avoid certain warnings.
-
hashCode
public int hashCode()Compute the hash code of the subgraph described by the embedding.This function should yield the same value as the corresponding function
Graph.hashCode()
. -
getGroup
protected int getGroup()Get the group of the underlying graph.- Returns:
- the group of the underlying graph
- Since:
- 2007.08.10 (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)
-
common
Find the (maximum) length of a common edge array prefix.- Parameters:
emb
- the embedding to compare to- Returns:
- the number of edges that are common to the embeddings,
or
-1
if not even the root node coincides - Since:
- 2007.10.23 (Christian Borgelt)
-
extend
Create all extensions of a given type of this embedding.The type of the extension is described by the index of the source node (index in the embedding), the index of the destination node (which may be negative in order to indicate that the node is not yet part of the embedding), the type of the edge and the type of the destination node of the edge to add.
- Parameters:
src
- the index of the source nodedst
- the index of the destination node (or -1 if it is not yet part of the embedding)edge
- the type of the extension edgenode
- the type of the destination node- Returns:
- a list of created embeddings
- Since:
- 2002.03.11 (Christian Borgelt)
-
overlaps
Check whether this embedding overlaps another.- Parameters:
emb
- the embedding to check for an overlapharmful
- whether to check for a harmful overlap- Returns:
- whether the embeddings overlap each other
- Since:
- 2007.06.14 (Christian Borgelt)
-
overlaps
Check whether this embedding overlaps another.- Parameters:
emb
- the embedding to check for an overlap- Returns:
- whether the embeddings overlap each other
- Since:
- 2007.06.12 (Christian Borgelt)
-
overlapsHarmfully
Check whether this embedding overlaps another harmfully.It is assumed that the two embeddings refer to the same fragment and thus have the same number of nodes and edges.
- Parameters:
emb
- the embedding to check for an overlap- Returns:
- whether the embeddings overlap each other harmfully
- Since:
- 2007.06.13 (Christian Borgelt)
-
main
Main function for testing the overlap functions.- Parameters:
args
- the command line arguments- Since:
- 2007.06.12 (Christian Borgelt)
-