public class Embedding
extends java.lang.Object
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).
Modifier and Type | Field and Description |
---|---|
protected Edge[] |
edges
the array of edges (only references to the underlying graph)
|
protected Graph |
graph
the graph referred to
|
protected Node[] |
nodes
the array of nodes (only references to the underlying graph)
|
protected Embedding |
succ
the next embedding in a list of embeddings
|
Modifier | Constructor and Description |
---|---|
protected |
Embedding()
Dummy constructor.
|
protected |
Embedding(CanonicalForm cnf)
Create an embedding from a canonical form.
|
protected |
Embedding(Embedding emb,
Edge edge)
Extend a given embedding with a given edge.
|
protected |
Embedding(Graph graph,
int index)
Create a single node embedding.
|
protected |
Embedding(Graph graph,
Node[] nodes,
Edge[] edges)
Create an embedding from node and edge references.
|
Modifier and Type | Method and Description |
---|---|
protected int |
common(Embedding emb)
Find the (maximum) length of a common edge array prefix.
|
boolean |
equals(java.lang.Object emb)
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(java.lang.String[] args)
Main function for testing the overlap functions.
|
protected void |
mark(int mark)
Mark all nodes and edges with a given value.
|
protected boolean |
overlaps(Embedding emb)
Check whether this embedding overlaps another.
|
protected boolean |
overlaps(Embedding emb,
boolean harmful)
Check whether this embedding overlaps another.
|
protected boolean |
overlapsHarmfully(Embedding emb)
Check whether this embedding overlaps another harmfully.
|
protected Embedding succ
protected Graph graph
protected Node[] nodes
protected Edge[] edges
protected Embedding()
This constructor is only needed to create the dummy object
CONTAINED
in the class Graph
, which
is used as a special parameter and as a special return value
for the function Graph.embed()
in order to save
a recursion parameter.
protected Embedding(Graph graph, int index)
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
).
graph
- the graph into which to embedindex
- the index of the node in the graphprotected Embedding(Graph graph, Node[] nodes, Edge[] edges)
This function is used when embedding a seed structure. The given node and edge arrays are copied.
graph
- the graph referred tonodes
- the nodes of the substructureedges
- the edges of the substructureprotected Embedding(CanonicalForm cnf)
This function is called if a created extension is only needed as an embedding (in contrast to a fragment).
cnf
- the canonical form holding the extensionprotected Embedding(Embedding emb, Edge 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()
.
emb
- the embedding to extendedge
- the edge by which to extend the embeddingextend(int,int,int,int)
public boolean equals(java.lang.Object emb)
This method is overridden only to avoid certain warnings.
equals
in class java.lang.Object
emb
- the embedding to compare topublic int hashCode()
This function should yield the same value as the corresponding
function Graph.hashCode()
.
hashCode
in class java.lang.Object
protected int getGroup()
protected void mark(int mark)
mark
- the value with which to mark nodes and edgesprotected void index()
protected int common(Embedding emb)
emb
- the embedding to compare to-1
if not even the root node coincidesprotected Embedding extend(int src, int dst, int edge, int node)
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.
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 nodeprotected boolean overlaps(Embedding emb, boolean harmful)
emb
- the embedding to check for an overlapharmful
- whether to check for a harmful overlapprotected boolean overlaps(Embedding emb)
emb
- the embedding to check for an overlapprotected boolean overlapsHarmfully(Embedding emb)
It is assumed that the two embeddings refer to the same fragment and thus have the same number of nodes and edges.
emb
- the embedding to check for an overlappublic static void main(java.lang.String[] args)
args
- the command line arguments