public class CnFBreadth1 extends CanonicalForm
Maximum source extensions are the restricted extensions of a breadth-first search spanning tree canonical form. Only nodes having an index no less than the maximum source of an edge (where the source of an edge is the incident node with the smaller index) may be extended by adding an edge. Edges closing rings must lead "forward", that is, must lead from a node with a smaller index to a node with a larger index. In addition, at the node with the maximum source index added edges must succeed all already incident edges that have this node as a source node.
For comparing edges and constructing code words the following precedence order of the edge properties is used:
The difference to CnFBreadth2
is the position of
the destination node index in the precedence order of the edge
properties. While in CnFBreadth2
it is the second
property to be compared, it is the last in this class.
all, ALLEXTS, ALLORBS, cedge, CHAIN, chcnt, CLASSES, cnode, curr, dst, EDGE, edgecnt, edges, emap, emb, EQVARS, fixed, FIXED, frag, idx, max, mode, nmap, nodecnt, nodes, ORBITS, pmax, pmin, pos1, pos2, rgmax, rgmin, RING, size, src, sym, type, word, xemgr
Constructor and Description |
---|
CnFBreadth1()
Create a breadth-first search spanning tree canonical form.
|
Modifier and Type | Method and Description |
---|---|
protected int |
adaptRing(Fragment frag,
boolean check)
Reorder the edges of a fragment with a ring extension.
|
protected int |
compareEdge(Edge e1,
Edge e2,
int next)
Compare two edges with the precedence order of the canonical form.
|
int |
compareToFrag(Fragment frag)
Compare the current extension to a given fragment.
|
protected int |
compareWord(Edge[] edges,
int n)
Compare the current code word to the one of the given edge array.
|
protected java.lang.String |
describe(Graph graph,
boolean create)
Create the code word for a given graph as a string.
|
protected boolean |
hasUnclosableRings(Fragment frag)
Check whether a fragment contains unclosable rings.
|
boolean |
init(Fragment frag,
Embedding emb)
Initialize the extension generation process.
|
protected void |
initVars()
Initialize the generation of equivalent ring extension variants.
|
protected int |
isCanonic(int ei,
int ni,
int cnt)
Internal recursive function for the canonical form test.
|
protected boolean |
makeCanonic(int ei,
int ni,
int cnt)
Internal recursive function for making a given graph canonic.
|
protected void |
makeWord(Edge[] edges,
int n)
Create the (prefix of a) code word for a given edge array.
|
boolean |
next()
Create the next extension.
|
Fragment |
nextFrag()
Create the next extended fragment.
|
protected boolean |
validRing()
Check whether the current ring extension is valid.
|
protected boolean |
variant()
Create the next ring extension variant.
|
chain, compareRing, compareWord, compareWord, createCnF, describe, equivClasses, init, initCanonic, initFrag, isCanExt, isCanonic, isCanonic, isRingKey, makeCanonic, makeCanonic, makeEmbedding, makeFragment, makeMap, makeWord, makeWord, prepare, removeRings, ring, setChainTypes, setExtMgr, setExtMode, setMaxSize, setRingSizes, useOrbits
public CnFBreadth1()
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.
init
in class CanonicalForm
frag
- the fragment to extendemb
- the embedding to extend
(must be contained in the fragment or
null
for pure fragment extensions)public boolean next()
Each time this function is called and returns
true
, a new extension has been created, which
may then be compared to already existing fragments (function
compareToFrag()
) or turned into a new fragment
(function makeFragment()
) or a new embedding
(function makeEmbedding()
). When all extensions of
the embedding passed to init()
have been created,
the function returns false
.
next
in class CanonicalForm
public Fragment nextFrag()
Each call creates a new fragment or returns null
.
This function works without embeddings, but draws an a stored list
of extension edges.
nextFrag
in class CanonicalForm
null
.protected 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.
validRing
in class CanonicalForm
protected 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, which keep their individual order (that is, the order of the already existing edges and the order of the added edges), have to be tried. This function initializes this variant generation.
initVars
in class CanonicalForm
protected boolean variant()
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, which keep their individual
order (that is, the order of the already existing edges and the
order of the added edges), have to be tried. This function
generates the next ring extension variant. Before it can be
called, the function initVars()
must have been
invoked.
variant
in class CanonicalForm
CanonicalForm.initVars()
protected 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.
adaptRing
in class CanonicalForm
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 int compareEdge(Edge e1, Edge e2, int next)
The precedence order of the edge properties is:
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.
compareEdge
in class CanonicalForm
e1
- the first edge to comparee2
- the second edge to comparenext
- the index with which to number the next node-1
, 0
, or +1
as the first edge is less than, equal to, or greater
than the second edgepublic 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 and to be 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.
compareToFrag
in class CanonicalForm
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 void makeWord(Edge[] edges, int n)
This function assumes that the node markers contain the node
indices, which is the case if this function is called from one
of the other makeWord
functions.
makeWord
in class CanonicalForm
edges
- the array of edges for which to create the code wordn
- the number of edges to considerprotected int compareWord(Edge[] edges, int n)
This function assumes that the node markers contain the node
indices, which is the case if this function is called from one
of the other compareWord
functions.
compareWord
in class CanonicalForm
edges
- the array of edges to compare ton
- the number of edges to consider-1
, 0
, or +1
as the internal code word is less than, equal to, or
greater than the code word of the given edges arrayprotected 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.
isCanonic
in class CanonicalForm
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodesprotected 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.
makeCanonic
in class CanonicalForm
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodesprotected boolean hasUnclosableRings(Fragment frag)
If the output is restricted to fragments containing only closed rings, the restricted extensions of a breadth-first search spanning tree canonical form render all nodes not on the rightmost path 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.
hasUnclosableRings
in class CanonicalForm
frag
- the fragment to check for unclosable ringsprotected 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).
describe
in class CanonicalForm
graph
- the graph for which to create a code word stringcreate
- whether the code word needs to be created