public class Graph
extends java.lang.Object
implements java.lang.Cloneable
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.
Modifier and Type | Field and Description |
---|---|
protected Recoder |
coder
an optional node type recoder
|
protected int |
edgecnt
the current number of edges
(may be smaller than the array length)
|
protected Edge[] |
edges
the array of edges (may be only partially used)
|
protected int |
nodecnt
the current number of nodes
(may be smaller than the array length)
|
protected Node[] |
nodes
the array of nodes (may be only partially used)
|
protected Notation |
ntn
the notation for describing the graph
|
Modifier | Constructor and Description |
---|---|
protected |
Graph()
Create/Initialize an empty graph.
|
protected |
Graph(Fragment frag)
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)
Create an extended graph (extended by one edge).
|
|
Graph(Notation ntn)
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,
Recoder coder)
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.
|
Modifier and Type | Method and 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()
Clear a graph (remove all nodes and edges).
|
java.lang.Object |
clone()
Create a clone of the graph.
|
boolean |
contains(Graph graph)
Check whether a graph is contained in this graph.
|
protected boolean |
contains(int type)
Check whether a node type is contained in this graph.
|
void |
decode()
Decode the node types.
|
Embedding |
embed(Graph graph)
Embed a graph structure (find all its embeddings).
|
protected Embedding |
embed(int type)
Embed a single node into the graph.
|
void |
encode(Recoder coder)
Encode the node types with the given type recoder.
|
boolean |
equals(java.lang.Object graph)
Check whether another graph is equal to this graph.
|
boolean |
equalsCanonic(Graph graph)
Compare the (canonical) code words of two graphs.
|
Edge |
getEdge(int index)
Get an edge by its index.
|
int |
getEdgeCount()
Get the number of edges of the graph.
|
TypeMgr |
getEdgeMgr()
Get the edge type manager of the graph.
|
int |
getEdgeType(int index)
Get the type of an edge.
|
Node |
getNode(int index)
Get a node by its index.
|
int |
getNodeCount()
Get the number of nodes of the graph.
|
TypeMgr |
getNodeMgr()
Get the node type manager of the graph.
|
int |
getNodeType(int index)
Get the type of a node.
|
int |
getNodeTypeRaw(int index)
Get the type of a node.
|
Notation |
getNotation()
Get the notation of the graph.
|
Recoder |
getRecoder()
Get the recoder for the node types.
|
int |
hashCode()
Compute the hash code of the attributed graph.
|
boolean |
hasOpenRings(int min,
int max)
Check whether this subgraph has open rings.
|
protected void |
index()
Mark all nodes and edges with their index.
|
boolean |
isCanonic(CanonicalForm cnf)
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 |
isConnected()
Check whether the graph is connected.
|
static void |
main(java.lang.String[] args)
Main function for testing some basic functionality.
|
boolean |
makeCanonic(CanonicalForm cnf)
Make a graph canonic w.r.t.
|
protected boolean |
makeCanonic(CanonicalForm cnf,
int keep)
Make a graph canonic w.r.t.
|
protected void |
map(CanonicalForm cnf)
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 |
markBridges()
Mark all edges that are bridges.
|
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(CanonicalForm cnf)
Normalize a graph w.r.t.
|
protected void |
opt()
Optimize memory usage.
|
void |
prepare()
Prepare a graph for frequent substructure mining.
|
boolean |
prepareEmbed()
Prepare a graph for embedding it into another.
|
java.lang.String |
toString()
Create a string description of the graph.
|
java.lang.String |
toString(CanonicalForm cnf)
Create a code word for a given canonical form.
|
java.lang.String |
toString(Notation ntn)
Create a string description in the given notation.
|
protected boolean |
trim(boolean remove)
Trim a graph based on its encoding recoder.
|
protected Node[] nodes
protected int nodecnt
protected Edge[] edges
protected int edgecnt
protected Recoder coder
protected Notation ntn
protected Graph()
This constructor is needed internally for turning graphs into named graphs.
public Graph(Notation ntn)
ntn
- the notation of the graphpublic Graph(Notation ntn, Recoder coder)
ntn
- the notation of the graphpublic Graph(Notation ntn, int nodecnt, int edgecnt)
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.
ntn
- the notation of the graphnodecnt
- the expected number of nodesedgecnt
- the expected number of edgespublic Graph(Notation ntn, Recoder coder, int nodecnt, int edgecnt)
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.
ntn
- the notation of the graphcoder
- the node type recoder of the graphnodecnt
- the expected number of nodesedgecnt
- the expected number of edgesprotected Graph(Graph 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).
graph
- the graph to cloneprotected Graph(Graph graph, int src, int dst, int edge, int node)
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).
graph
- the graph to clonesrc
- the source node index of the edge to adddst
- the destination node index of the edge to addedge
- the edge type of the edge to addnode
- the destination node type of the edge to addprotected Graph(Fragment frag)
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).
frag
- the fragment to turn into a graphpublic java.lang.Object clone()
This function simply returns new Graph(this)
.
It is intended mainly for debugging purposes.
clone
in class java.lang.Object
Graph(Graph)
public void clear()
public boolean equals(java.lang.Object 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.
equals
in class java.lang.Object
graph
- the graph to compare tocontains(Graph)
public int hashCode()
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
.
hashCode
in class java.lang.Object
public Notation getNotation()
public TypeMgr getNodeMgr()
public TypeMgr getEdgeMgr()
public Recoder getRecoder()
null
if no recoder is usedencode(Recoder)
public int addNodeRaw(int type)
Even if the graph contains a node type recoder, the node type is stored exactly as it is given.
type
- the type of the node to addaddNodeRaw(int)
public int addNode(int type)
If the graph contains a node type recoder, the given node type is automatically encoded with it.
type
- the type of the node to addaddNode(int)
public int getNodeCount()
public Node getNode(int index)
index
- the index of the node to retrieveindex
-th node of the graphpublic int getNodeType(int index)
If the graph contains a recoder for the node types, the node type is automatically decoded.
index
- the index of the nodeindex
-th node of the graphgetNodeTypeRaw(int)
public int getNodeTypeRaw(int index)
Even if the graph contains a recoder for the node types, the node type is not decoded, but returned as it is stored.
index
- the index of the nodeindex
-th node of the graphgetNodeType(int)
public int addEdge(int src, int dst, int type)
src
- the index of the source node of the edgedst
- the index of the destination node of the edgetype
- the type of the edge to addpublic int getEdgeCount()
public Edge getEdge(int index)
index
- the index of the edge to retrieveindex
-th edge of the graphpublic int getEdgeType(int index)
Since edge types are currently not encoded,
there is no need to distinguish getEdgeType
and getEdgeTypeRaw
.
index
- the index of the edgeindex
-th edge of the graphprotected void opt()
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.
protected void mark(int mark)
mark
- the value with which to mark nodes and edges.protected void index()
public void encode(Recoder coder)
The given type recoder is stored in the graph and may be
retrieved with the function getRecoder()
.
coder
- the type recoder to usedecode()
,
getRecoder()
public void decode()
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.
encode(Recoder)
,
getRecoder()
public void maskTypes(int[] masks)
The types of all nodes and edges of the graph are logically anded with the masks in a given array of masks.
masks
- an array with 4 elements, which refer toprotected boolean trim(boolean remove)
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.
remove
- whether the nodes and edges are actually to be
removed (true
) or only to be marked
(false
)public boolean isConnected()
public int markBridges()
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
public int markRings(int min, int max)
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).
min
- the smallest ring size (number of edges/nodes)max
- the largest ring size (number of edges/nodes)protected int markRings(int min, int max, int typeflag)
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
.
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 markingprotected int markPseudo(int max)
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.
max
- the maximal size of a pseudo-ringpublic boolean hasOpenRings(int min, int max)
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.
min
- the smallest ring size (number of edges/nodes)max
- the largest ring size (number of edges/nodes)public void prepare()
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).
public boolean prepareEmbed()
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.
protected Embedding embed(int type)
type
- the type of the node to embedpublic Embedding embed(Graph graph)
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.
graph
- the graph to embedprotected boolean contains(int type)
type
- the type of the node to check forpublic boolean contains(Graph 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.
graph
- the graph to embedembed(Graph)
public boolean isCanonic(CanonicalForm cnf)
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.
cnf
- the canonical formprotected int isCanonic(CanonicalForm cnf, int fixed)
cnf
- the canonical formfixed
- the number of fixed edges-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. |
public boolean makeCanonic(CanonicalForm cnf)
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.
cnf
- the extension object defining the canonical formprotected boolean makeCanonic(CanonicalForm cnf, int keep)
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.
cnf
- the canonical formkeep
- the number of edges to keep at the beginning
of the graph/code wordpublic void normalize(CanonicalForm cnf)
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.
cnf
- the canonical formprotected void map(CanonicalForm cnf)
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.
cnf
- the canonical form providing the mappublic boolean equalsCanonic(Graph graph)
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.
graph
- the graph to compare topublic java.lang.String toString()
toString
in class java.lang.Object
public java.lang.String toString(Notation ntn)
public java.lang.String toString(CanonicalForm cnf)
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.
cnf
- the canonical formpublic static void main(java.lang.String[] args)
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.
args
- the command line arguments