public abstract class CanonicalForm
extends java.lang.Object
A canonical form object serves the purpose to define a canonical form of graphs and to create the corresponding restricted extensions of a fragment.
The same extension object is reused to create extensions of several fragments instead of creating a new extension object for each fragment or even embedding. As a consequence the fragment and embedding to extend are not passed directly to a constructor, but to an initialization function. In addition, if embeddings are used, extended fragments are created in a delayed manner, recording only the extension edge at the beginning and turning it into a full fragment only on request (to avoid creating duplicates).
The field size
is used to indicate the type of the
current extension. A negative size indicates a chain extension,
with the absolute value of the size being the chain length.
A zero size indicates a single edge extension (the standard case).
Finally, a positive size indicates a ring extension, with the size
being the number of nodes/edges in the ring.
Modifier and Type | Field and Description |
---|---|
protected long |
all
all (remaining) ring flags of the current edge
|
static int |
ALLEXTS
extension mode flag: generate all extensions
|
static int |
ALLORBS
extension mode flag: use node orbits for all extensions;
not only those leading to a new node
|
protected int |
cedge
the edge type for chain extensions
|
static int |
CHAIN
extension mode flag: variable length chain
|
protected int |
chcnt
the number of variable length chains
|
static int |
CLASSES
extension mode flag: use node equivalence classes
|
protected int |
cnode
the node type for chain extensions
|
protected long |
curr
the current ring flag
|
protected int |
dst
the index of the current destination node
|
static int |
EDGE
extension mode flag: single edge
|
protected int |
edgecnt
the number of new edges
|
protected Edge[] |
edges
(relevant) edges of the extension
|
protected int[] |
emap
the edge map for making a graph canonic
|
protected Embedding |
emb
the embedding that is extended (may be
null ) |
static int |
EQVARS
extension mode flag: equivalent ring variants
|
protected int |
fixed
the number of fixed edges in a canonical form test
|
protected static int |
FIXED
flag for a fixed edge in the ring order test
|
protected Fragment |
frag
the fragment that is extended
|
protected int |
idx
the current edge index in the source node
|
protected int |
max
the maximum fragment size (number of nodes)
|
protected int |
mode
the extension mode (e.g.
|
protected int[] |
nmap
the node map for making a graph canonic
|
protected int |
nodecnt
the number of new nodes
|
protected Node[] |
nodes
(relevant) nodes of the extension
|
static int |
ORBITS
extension mode flag: use node orbits to filter (if known)
|
protected int |
pmax
the maximal position/position index of a ring edge
|
protected int |
pmin
the minimal position/current position index of a ring edge
|
protected int |
pos1
the current position 1 of equivalent edges for ring extensions
|
protected int |
pos2
the current position 2 of equivalent edges for ring extensions
|
protected int |
rgmax
the maximum ring size (number of nodes/edges)
|
protected int |
rgmin
the minimum ring size (number of nodes/edges)
|
static int |
RING
extension mode flag: ring (must be marked)
|
protected int |
size
the number of nodes in a ring (positive) or chain (negative)
|
protected int |
src
the index of the current source node
|
protected boolean |
sym
whether the current ring is locally symmetric
|
protected int |
type
the type of the extension edge (from
EDGE.type ) |
protected int[] |
word
the code word for isCanonic/makeCanonic
|
protected ExtMgr |
xemgr
the extension edge manager (for extensions without embeddings)
|
Constructor and Description |
---|
CanonicalForm()
Create a canonical form object.
|
Modifier and Type | Method and Description |
---|---|
protected abstract int |
adaptRing(Fragment frag,
boolean check)
Reorder the edges of a fragment with a ring extension.
|
protected boolean |
chain()
Create a variable length chain extension.
|
protected abstract int |
compareEdge(Edge e1,
Edge e2,
int next)
Compare two edges with the precedence order of the canonical form.
|
protected int |
compareRing(Fragment frag)
Compare the current ring extension to a fragment.
|
abstract int |
compareToFrag(Fragment frag)
Compare the current extension to a given fragment.
|
protected abstract int |
compareWord(Edge[] edges,
int n)
Compare the current code word to the one of the given edge array.
|
protected int |
compareWord(Graph graph)
Compare the current code word to the one of the given graph.
|
protected int |
compareWord(Graph graph,
int edgecnt)
Compare the current code word to the one of the given graph.
|
static CanonicalForm |
createCnF(java.lang.String name)
Create an extension object corresponding to a given name.
|
protected java.lang.String |
describe(Graph graph)
Create the code word for a given graph as a string.
|
protected abstract java.lang.String |
describe(Graph graph,
boolean create)
Create the code word for a given graph as a string.
|
protected int |
equivClasses(Graph graph)
Find the node equivalence classes for a given graph.
|
protected abstract boolean |
hasUnclosableRings(Fragment frag)
Check whether a fragment contains unclosable rings.
|
boolean |
init(Fragment frag)
Initialize the extension generation process.
|
boolean |
init(Fragment frag,
Embedding emb)
Initialize the extension generation process.
|
protected void |
initCanonic(Graph graph,
int fixed)
Initialize a canonical form test or generation.
|
boolean |
initFrag(Fragment frag)
Initialize the extension generation process.
|
protected abstract void |
initVars()
Initialize the generation of equivalent ring extension variants.
|
protected boolean |
isCanExt(Graph graph)
Check whether a given graph is a canonic extension of its base.
|
protected boolean |
isCanonic(Graph graph)
Check whether a given graph is canonic.
|
protected int |
isCanonic(Graph graph,
int fixed)
Check whether a given graph is canonic.
|
protected abstract int |
isCanonic(int ei,
int ni,
int cnt)
Internal recursive function for the canonical form test.
|
protected boolean |
isRingKey(Graph graph,
Edge edge)
Check whether a prefix is a ring key.
|
protected boolean |
makeCanonic(Graph graph)
Make a given graph canonic.
|
protected boolean |
makeCanonic(Graph graph,
int keep)
Make a given graph canonic.
|
protected abstract boolean |
makeCanonic(int ei,
int ni,
int cnt)
Internal recursive function for making a given graph canonic.
|
Embedding |
makeEmbedding()
Create an embedding from the current extension.
|
Fragment |
makeFragment()
Create a fragment from the current extension.
|
protected boolean |
makeMap(Graph graph,
int n)
Build a map for reordering the nodes and edges.
|
protected abstract void |
makeWord(Edge[] edges,
int n)
Create the (prefix of a) code word for a given edge array.
|
protected int |
makeWord(Graph graph)
Create the code word for a given graph.
|
protected int |
makeWord(Graph graph,
int edgecnt)
Create the code word for the first edges of a given graph.
|
boolean |
next()
Create the next (restricted) extension of an embedding.
|
Fragment |
nextFrag()
Create the next (restricted) extension of a fragment.
|
protected Graph |
prepare(Fragment frag)
Prepare the rings of a fragment for adaptation and order test.
|
protected static void |
removeRings(Edge edge)
Remove the flags of all rings an edge is contained in.
|
protected boolean |
ring()
Create a ring extension.
|
void |
setChainTypes(int node,
int edge)
Set the node and edge type for chain extensions.
|
void |
setExtMgr(ExtMgr xemgr)
Set the extension edge manager.
|
void |
setExtMode(int mode)
Set the extension mode.
|
void |
setMaxSize(int max)
Set the maximum fragment size (to limit extensions).
|
void |
setRingSizes(int rgmin,
int rgmax)
Set the ring sizes for ring extensions.
|
protected boolean |
useOrbits()
Whether node orbits are to be used to filter extensions.
|
protected abstract boolean |
validRing()
Check whether the current ring extension is valid.
|
protected abstract boolean |
variant()
Create the next ring extension variant.
|
public static final int EDGE
public static final int RING
public static final int CHAIN
public static final int EQVARS
public static final int ORBITS
public static final int ALLEXTS
public static final int CLASSES
public static final int ALLORBS
protected static final int FIXED
protected int mode
EDGE
, RING
)protected int max
protected int rgmin
protected int rgmax
protected int cnode
protected int cedge
protected ExtMgr xemgr
protected Fragment frag
protected Embedding emb
null
)protected Node[] nodes
protected Edge[] edges
protected int size
protected int nodecnt
protected int edgecnt
protected int chcnt
protected int src
protected int idx
protected int dst
protected int type
EDGE.type
)protected long all
protected long curr
protected boolean sym
protected int pmin
protected int pmax
protected int pos1
protected int pos2
protected int fixed
protected int[] word
protected int[] nmap
protected int[] emap
public CanonicalForm()
Since CanonicalForm
is an abstract class, this
constructor cannot be called directly to create an instance.
Rather it is meant as a common initialization routine for
subclasses of this class.
public void setExtMode(int mode)
The extension mode controls what extensions are created. By default only single edge extensions are created. Other modes include ring extensions and chain extensions.
mode
- the extension mode
(e.g. EDGE
or EDGE|RING
)public void setMaxSize(int max)
The fragment size is the number of nodes of a fragment. The maximum fragment size is the maximum number of nodes a fragment may have. No extended fragments will be created that contain more than this number of nodes.
max
- the maximum fragment size (number of nodes)public void setRingSizes(int rgmin, int rgmax)
These ring sizes are actually not needed for creating ring extensions, but only for adapting them, which is needed only if canonical form pruning is used.
rgmin
- the minimal ring size (number of nodes/edges)rgmax
- the maximal ring size (number of nodes/edges)public void setChainTypes(int node, int edge)
node
- the type of the chain nodesedge
- the type of the chain edgespublic void setExtMgr(ExtMgr xemgr)
xemgr
- the extension edge managerprotected boolean useOrbits()
With the help of node orbits some equivalent siblings can be suppressed.
public boolean init(Fragment frag, Embedding emb)
Instead of creating a new extension object each time a fragment or an embedding has to be extended, the same extension object is reused, thus greatly reducing the overhead for memory allocation. As a consequence, the extension object has to be reinitialized for each fragment and each embedding that is to be extended.
frag
- the fragment to extendemb
- the embedding to extend
(must be contained in the fragment or
null
for pure fragment extensions)public boolean init(Fragment frag)
This function initializes the extension process without
embeddings, that is, based only on internally stored possible
extension edges. This function is equivalent to
initFrag(Fragment)
.
frag
- the fragment to extendinitFrag(Fragment)
public boolean initFrag(Fragment frag)
This function initializes the extension process without
embeddings, that is, based only on internally stored possible
extension edges. This function is equivalent to
init(Fragment)
.
frag
- the fragment to extendinit(Fragment)
public boolean next()
Each time this function is called and returns
true
, a new (restricted) extension has been created.
This extension may then be compared to already existing fragments
(function compareTo()
) or turned into a new fragment
(function makeFragment()
) or a new embedding
(function makeEmbedding()
).
When all (restricted) extensions of the embedding passed to
init(Fragment,Embedding)
have been created,
the function returns false
.
public Fragment nextFrag()
Each call creates a new extended fragment or returns
null
. This function works without embeddings,
(initialization: functions init(Fragment)
or
initFrag(Fragment)
), but rather draws an a
stored list of extension edges.
null
.protected boolean ring()
Follow a ring flag through the edges of the graph the
embedding to extend refers to and collect the new edges for
the extension. All created rings are checked with the function
validRing()
, restricting certain rings to a specific
form (thus avoiding some unnecessary canonical form tests).
If no (further) ring can be created, the function returns
false
, otherwise true
.
protected abstract boolean validRing()
In order to reduce the number of generated fragments, rings
are usually generated in only one form. It is checked whether
the source of the first new ring edge is minimal over all edges
of the ring (so that a ring is always attached to the node with
minimal index) and whether the first and last edges of the ring
allow to fix an orientation of the ring, only one of which is
considered valid. Invalid rings are discarded in the function
ring()
that creates ring extensions.
protected abstract void initVars()
If a ring start (and possibly also ends) with an edge that is equivalent to one or more edges already in the fragment (that is, edges that start at the same node, have the same type, and lead to nodes of the same type), these edges must be spliced with the already existing equivalent edges in the fragment. All possible ways of splicing the equivalent edges have to be tried. This function initializes this variant generation.
protected abstract boolean variant()
initVars()
protected abstract int adaptRing(Fragment frag, boolean check)
After a ring extension it may be necessary to reorder the edges of the resulting fragment, so that the edges get into the proper order w.r.t. the canonical form. In addition, it must be checked whether rings were added in the right order (if several rings were added). If not, the ring extension cannot be adapted and thus the function returns -1.
This function does not actually reorganize the fragment if the ring extension can be adapted, but only stores the edges and nodes in their new order in internal arrays. In addition, it creates a map for reorganizing the nodes and edges, also in an internal buffer. Either of these may later be used to actually reorganize the fragment (as a sub-graph) as well as the embeddings. Note that these arrays and maps are not filled/created if the fragment need not be changed in any way. In this case the function returns +1, otherwise the result is 0.
frag
- the fragment to adaptcheck
- whether to check the ring order-1, | if the ring adaptation failed, |
0, | if the ring adaptation succeeded, but the fragment needs to be modified, |
+1, | if the ring extension need not be adapted. |
protected abstract int compareEdge(Edge e1, Edge e2, int next)
A canonical form usually allows to compare two edges in the necessary way by fixing a specific precedence order of the defining properties of the edges.
This function is meant to compare edges from the same graph at each point where the next edge needs to be selected, when the graph (or rather its edge array) is rebuilt. At such a point all nodes incident to already processed edges are numbered. However, one of the nodes incident to the compared edges may not have been numbered yet. As this would make it impossible to compare the edges, the next number to be given to a node is also passed to the function.
e1
- the first edge to comparee2
- the second edge to comparenext
- the index with which to number the next nodeprotected static void removeRings(Edge edge)
edge
- the edge to processprotected Graph prepare(Fragment frag)
frag
- the fragment to prepareprotected boolean isRingKey(Graph graph, Edge edge)
This function presupposes that the internal edge buffer contains the graph's edges in adapted order.
graph
- the graph to checkedge
- the edge at the end of the prefix to checkprotected boolean chain()
A variable length chain consists of nodes of the same type
that are connected by edges of the same type. There must not
be any branches. This function is called when the function
next()
detects a possible start of a chain.
However, the check in next()
is limited and thus
it may be that no variable length chain can be created. In this
case this function returns false
.
public abstract int compareToFrag(Fragment frag)
This function is used to determine whether the current extension is equivalent to a previously created one (and thus only an embedding has to be created from it, which is then added to the corresponding fragment) or not (and thus a new fragment has to be created). It is designed as a comparison function, because the created fragments are kept as an ordered array, so that a binary search becomes possible.
frag
- the fragment to compare to-1
, 0
, or +1
as the fragment described by this extension is less
than, equal to, or greater than the fragment given
as an argumentprotected int compareRing(Fragment frag)
This is a sub-function of the function compareTo
,
which compares the current extension to a given fragment whatever
the type of the extension may be. If both the current extension
and the given fragment describe a ring extension, this function
is called to compare them.
This function assumes that the first edge of the ring together
with its destination node have already been compared (namely in
the function compareTo
) and thus only compares the
rest of the new ring edges.
frag
- the fragment to compare toprotected abstract boolean hasUnclosableRings(Fragment frag)
If the output is restricted to fragments containing only closed rings, the restricted extensions (as they can be derived from a canonical form) render certain nodes unextendable. If such a node has only one incident ring edge, the ring of which this edge is part cannot be closed by future extensions. Hence neither this fragment nor any of its extensions can produce output and thus it can be pruned.
frag
- the fragment to check for unclosable ringspublic Fragment makeFragment()
This function is called when the current extension is not equal to an already existing fragment and thus a new fragment has to be created.
public Embedding makeEmbedding()
This function is called when the current extension is equal to an already existing fragment and thus only a new embedding has to be added to that fragment.
protected void initCanonic(Graph graph, int fixed)
For a canonical form test or for the procedure that makes a graph canonical, the internal arrays have to have a certain size (depending on the size of the graph, that is, the number of its nodes and edges), so that they can hold the necessary data. This function ensures proper array sizes and also initializes some variables.
graph
- the graph to make canonic or to checkfixed
- the number of fixed (immovable) edgesprotected int makeWord(Graph graph)
The code word is created for the current order of the edges
as it is found in the graph. As a consequence the resulting
code word may or may not be the canonical code word. If the
canonical code word is desired, the graph has to be made
canonic by calling the function makeCanonic()
.
graph
- the graph for which to create the code wordprotected int makeWord(Graph graph, int edgecnt)
In other words, this function creates the prefix of the
code word for the given graph, using only the first edges.
If, however, edgecnt == graph.edgecnt
, all edges
are used and thus a full code word is created.
The code word is created for the current order of the edges
as it is found in the graph. As a consequence the resulting
code word may or may not be the canonical code word. If the
canonical code word is desired, the graph has to be made
canonic by calling the function makeCanonic()
.
graph
- the graph for which to create the code wordedgecnt
- the number of edges to considerprotected abstract void makeWord(Edge[] edges, int n)
edges
- the array of edges for which to create the code wordn
- the number of edges to considerprotected int compareWord(Graph graph)
This function assumes that makeWord()
has been
called before (for some other graph or a different form of the
same graph) and has placed a code word into the internal code
word buffer. This code word is then compared to the code word
that would be created for the given graph (without explicitely
generating the code word for the graph).
graph
- the graph to compare toprotected int compareWord(Graph graph, int edgecnt)
The comparison takes only the first edgecnt
edges into account. Any remaining edges are not compared.
If, however, edgecnt == graph.edgecnt
, the full
code words are compared.
This function assumes that makeWord()
has been
called before and has placed a code word into the internal code
word buffer. This code word is then compared to the code word
that would be created for the given graph (without explicitely
generating the code word for the graph).
graph
- the graph to compare toedgecnt
- the number of edges to considerprotected abstract int compareWord(Edge[] edges, int n)
edges
- the array of edges to compare ton
- the number of edges to considerprotected abstract int isCanonic(int ei, int ni, int cnt)
In each recursive call to this function one edge is checked. If a possibility to construct a lexicographically smaller (prefix of a) code word is found or if all (prefixes of) code words that could be constructed are lexicographically greater, the function returns directly. Only if there is a possibility to construct an equal prefix, the function calls itself recursively.
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodesprotected int isCanonic(Graph graph, int fixed)
In addition, if the graph is not canonic, it is determined
whether the canonical form differs from the form of the graph
within the first fixed
edges. Hence there are three
possible outcomes: (1) the graph is in canonical form (return
value 1), (2) the graph differs from the canonical form in the
first fixed
edges (return value -1), (3) the graph
is not in canonical form, but does not differ in the first
fixed
edges (return value 0).
graph
- the graph to check for canonical formfixed
- the number of fixed edgesfixed
edges,fixed
edges (but only in some
later edge description),protected boolean isCanonic(Graph graph)
graph
- the graph to check for canonical formprotected abstract boolean makeCanonic(int ei, int ni, int cnt)
This function works in basically the same way as the analogous
function isCanonic()
, with the only difference that
whenever a smaller (prefix of a) code word is found, the function
is not terminated, but continues with the new (prefix of a) code
word, thus constructing the lexicographically smallest code word.
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodesprotected boolean makeCanonic(Graph graph, int keep)
The form of the graph (that is, the order of its nodes
and edges) is changed in such a way that it produces the
lexicographically smallest code word. The first keep
edges are left unchanged. If keep = 0
, then all
edges may change their positions, but the first node is kept.
Only if keep = -1
the graph may be completely
reorganized.
This function does not actually reorganize the graph, but
only stores the found canonical order of the edges and nodes in
internal arrays. In addition, it creates maps for reorganizing
the nodes and edges, also in internal buffers. Either of these
may later be used to actually reorganize the graph as well
as any embeddings (if the graph represents a fragment). Note
that these arrays and maps are not filled/created if the graph
is already in canonical form. In this case the function returns
false
, thus indicating that no reorganization is
necessary.
graph
- the graph to make canonickeep
- the number of edges to keepprotected boolean makeCanonic(Graph graph)
The form of the graph (that is, the order of its nodes and edges) is changed in such a way that it produces the lexicographically smallest code word.
graph
- the graph to make canonicmakeCanonic(Graph,int)
protected int equivClasses(Graph graph)
This function modifies the types of the nodes of the graph.
Since the original types may be needed again later, they have
to be saved, and restored when the equivalence classes are not
needed anymore. It also destroys the node markers and sets them
all to -1
.
graph
- the graph for which to find node equivalence classesprotected boolean isCanExt(Graph graph)
The base of the graph is the graph without the last edge in
in its edge array (and without the last node if this node is
incident to no other edge). The difference to the function
isCanonic()
is that this function computes node
equivalence classes to simplify the construction of the canonical
code word.
graph
- the graph to checkprotected boolean makeMap(Graph graph, int n)
This map describes the transition from the original form to
the canonical form and is built in the word
array
of this extension structure. The first graph.edgecnt
elements of this array contain the new indices of the edges, the
next graph.nodecnt
elements contain the new indices
of the nodes. The map is used to reorganize the embeddings of a
fragment.
graph
- the graph for which to build the mapn
- the highest already fixed node indexprotected java.lang.String describe(Graph graph)
graph
- the graph for which to create a code wordprotected abstract java.lang.String describe(Graph graph, boolean create)
This function allows for the code word of the graph already
being available in the internal code word buffer. In this case
the function should be called with create == false
(the graph is only used to retrieve the number of edges).
graph
- the graph for which to create a code word stringcreate
- whether the code word needs to be createdpublic static CanonicalForm createCnF(java.lang.String name)
name
- the name of the extension type