Class CanonicalForm
- All Implemented Interfaces:
Serializable
- Direct Known Subclasses:
CnFBreadth1
,CnFBreadth2
,CnFDepth
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.
- Since:
- 2002.03.11
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected long
all (remaining) ring flags of the current edgestatic final int
extension mode flag: generate all extensionsstatic final int
extension mode flag: use node orbits for all extensions; not only those leading to a new nodeprotected int
the edge type for chain extensionsstatic final int
extension mode flag: variable length chainprotected int
the number of variable length chainsstatic final int
extension mode flag: use node equivalence classesprotected int
the node type for chain extensionsprotected long
the current ring flagprotected boolean
whether the graphs are to be treated as directedstatic final int
extension mode flag: edges are to be treated as directedprotected int
the index of the current destination nodestatic final int
extension mode flag: single edgeprotected int
the number of new edgesprotected Edge[]
(relevant) edges of the extensionprotected int[]
the edge map for making a graph canonicprotected Embedding
the embedding that is extended (may benull
)static final int
extension mode flag: equivalent ring variantsprotected int
the number of fixed edges in a canonical form testprotected static final int
flag for a fixed edge in the ring order testprotected Fragment
the fragment that is extendedprotected int
the current edge index in the source nodeprotected int
the maximum fragment size (number of nodes)protected int
the extension mode (e.g.protected int[]
the node map for making a graph canonicprotected int
the number of new nodesprotected Node[]
(relevant) nodes of the extensionstatic final int
extension mode flag: use node orbits to filter (if known)protected int
the maximal position/position index of a ring edgeprotected int
the minimal position/current position index of a ring edgeprotected int
the current position 1 of equivalent edges for ring extensionsprotected int
the current position 2 of equivalent edges for ring extensionsprotected int
the maximum ring size (number of nodes/edges)protected int
the minimum ring size (number of nodes/edges)static final int
extension mode flag: ring (must be marked)static final int
extension mode flag: whether graphs/fragments are simple, that is, there is at most one edge between two nodesprotected int
the number of nodes in a ring (positive) or chain (negative)protected int
the index of the current source nodeprotected boolean
whether the current ring is locally symmetricprotected int
the type of the extension edge (fromEDGE.type
)protected int[]
the code word for isCanonic/makeCanonicprotected ExtMgr
the extension edge manager (for extensions without embeddings) -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected abstract int
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
Create an extension object corresponding to a given name.protected String
Create the code word for a given graph as a string.protected abstract String
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
Initialize the extension generation process.boolean
Initialize the extension generation process.protected void
initCanonic
(Graph graph, int fixed) Initialize a canonical form test or generation.boolean
Initialize the extension generation process.protected abstract void
initVars()
Initialize the generation of equivalent ring extension variants.protected boolean
Check whether a given graph is a canonic extension of its base.protected abstract int
isCanonic
(int ei, int ni, int cnt) Internal recursive function for the canonical form test.protected boolean
Check whether a given graph is canonic.protected int
Check whether a given graph is canonic.protected boolean
Check whether a prefix is a ring key.protected abstract boolean
makeCanonic
(int ei, int ni, int cnt) Internal recursive function for making a given graph canonic.protected boolean
makeCanonic
(Graph graph) Make a given graph canonic.protected boolean
makeCanonic
(Graph graph, int keep) Make a given graph canonic.Create an embedding from the current extension.Create a fragment from the current extension.protected boolean
Build a map for reordering the nodes and edges.protected abstract void
Create the (prefix of a) code word for a given edge array.protected int
Create the code word for a given graph.protected int
Create the code word for the first edges of a given graph.boolean
next()
Create the next (restricted) extension of an embedding.nextFrag()
Create the next (restricted) extension of a fragment.protected Graph
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
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
Whether node orbits are to be used to filter extensions.protected abstract boolean
Check whether the current ring extension is valid.protected abstract boolean
variant()
Create the next ring extension variant.
-
Field Details
-
SIMPLE
public static final int SIMPLEextension mode flag: whether graphs/fragments are simple, that is, there is at most one edge between two nodes- See Also:
-
DIRECTED
public static final int DIRECTEDextension mode flag: edges are to be treated as directed- See Also:
-
EDGE
public static final int EDGEextension mode flag: single edge- See Also:
-
RING
public static final int RINGextension mode flag: ring (must be marked)- See Also:
-
CHAIN
public static final int CHAINextension mode flag: variable length chain- See Also:
-
EQVARS
public static final int EQVARSextension mode flag: equivalent ring variants- See Also:
-
ORBITS
public static final int ORBITSextension mode flag: use node orbits to filter (if known)- See Also:
-
ALLEXTS
public static final int ALLEXTSextension mode flag: generate all extensions- See Also:
-
CLASSES
public static final int CLASSESextension mode flag: use node equivalence classes- See Also:
-
ALLORBS
public static final int ALLORBSextension mode flag: use node orbits for all extensions; not only those leading to a new node- See Also:
-
FIXED
protected static final int FIXEDflag for a fixed edge in the ring order test- See Also:
-
mode
protected int modethe extension mode (e.g.EDGE
,RING
) -
dir
protected boolean dirwhether the graphs are to be treated as directed -
max
protected int maxthe maximum fragment size (number of nodes) -
rgmin
protected int rgminthe minimum ring size (number of nodes/edges) -
rgmax
protected int rgmaxthe maximum ring size (number of nodes/edges) -
cnode
protected int cnodethe node type for chain extensions -
cedge
protected int cedgethe edge type for chain extensions -
xemgr
the extension edge manager (for extensions without embeddings) -
frag
the fragment that is extended -
emb
the embedding that is extended (may benull
) -
nodes
(relevant) nodes of the extension -
edges
(relevant) edges of the extension -
size
protected int sizethe number of nodes in a ring (positive) or chain (negative) -
nodecnt
protected int nodecntthe number of new nodes -
edgecnt
protected int edgecntthe number of new edges -
chcnt
protected int chcntthe number of variable length chains -
src
protected int srcthe index of the current source node -
idx
protected int idxthe current edge index in the source node -
dst
protected int dstthe index of the current destination node -
type
protected int typethe type of the extension edge (fromEDGE.type
) -
all
protected long allall (remaining) ring flags of the current edge -
curr
protected long currthe current ring flag -
sym
protected boolean symwhether the current ring is locally symmetric -
pmin
protected int pminthe minimal position/current position index of a ring edge -
pmax
protected int pmaxthe maximal position/position index of a ring edge -
pos1
protected int pos1the current position 1 of equivalent edges for ring extensions -
pos2
protected int pos2the current position 2 of equivalent edges for ring extensions -
fixed
protected int fixedthe number of fixed edges in a canonical form test -
word
protected int[] wordthe code word for isCanonic/makeCanonic -
nmap
protected int[] nmapthe node map for making a graph canonic -
emap
protected int[] emapthe edge map for making a graph canonic
-
-
Constructor Details
-
CanonicalForm
public CanonicalForm()Create a canonical form object.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.- Since:
- 2003.08.06 (Christian Borgelt)
-
-
Method Details
-
setExtMode
public void setExtMode(int mode) Set the extension 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.
- Parameters:
mode
- the extension mode (e.g.EDGE
orEDGE|RING
)- Since:
- 2009.04.29 (Christian Borgelt)
-
setMaxSize
public void setMaxSize(int max) Set the maximum fragment size (to limit extensions).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.
- Parameters:
max
- the maximum fragment size (number of nodes)- Since:
- 2009.04.29 (Christian Borgelt)
-
setRingSizes
public void setRingSizes(int rgmin, int rgmax) Set the ring sizes for ring extensions.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.
- Parameters:
rgmin
- the minimal ring size (number of nodes/edges)rgmax
- the maximal ring size (number of nodes/edges)- Since:
- 2006.07.01 (Christian Borgelt)
-
setChainTypes
public void setChainTypes(int node, int edge) Set the node and edge type for chain extensions.- Parameters:
node
- the type of the chain nodesedge
- the type of the chain edges- Since:
- 2006.10.29 (Christian Borgelt)
-
setExtMgr
Set the extension edge manager.- Parameters:
xemgr
- the extension edge manager- Since:
- 2010.01.22 (Christian Borgelt)
-
useOrbits
protected boolean useOrbits()Whether node orbits are to be used to filter extensions.With the help of node orbits some equivalent siblings can be suppressed.
- Returns:
- whether node orbits are to be used
- Since:
- 2011.02.22 (Christian Borgelt)
-
init
Initialize the extension generation process.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.
- Parameters:
frag
- the fragment to extendemb
- the embedding to extend (must be contained in the fragment ornull
for pure fragment extensions)- Returns:
- whether there may be extensions
- Since:
- 2003.08.06/2011.02.22 (Christian Borgelt)
-
init
Initialize the extension generation process.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)
.- Parameters:
frag
- the fragment to extend- Returns:
- whether they may be extensions
- Since:
- 2010.01.21 (Christian Borgelt)
- See Also:
-
initFrag
Initialize the extension generation process.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)
.- Parameters:
frag
- the fragment to extend- Returns:
- whether they may be extensions
- Since:
- 2011.02.18 (Christian Borgelt)
- See Also:
-
next
public boolean next()Create the next (restricted) extension of an embedding.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 (functioncompareTo()
) or turned into a new fragment (functionmakeFragment()
) or a new embedding (functionmakeEmbedding()
). When all (restricted) extensions of the embedding passed toinit(Fragment,Embedding)
have been created, the function returnsfalse
.- Returns:
- whether another extension was created
- Since:
- 2003.08.06/2011.02.22 (Christian Borgelt)
-
nextFrag
Create the next (restricted) extension of a fragment.Each call creates a new extended fragment or returns
null
. This function works without embeddings, (initialization: functionsinit(Fragment)
orinitFrag(Fragment)
), but rather draws an a stored list of extension edges.- Returns:
- the next extended fragment or
null
. - Since:
- 2010.01.21/2011.02.22 (Christian Borgelt)
-
ring
protected boolean ring()Create a ring extension.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 returnsfalse
, otherwisetrue
.- Returns:
- whether another ring extension was created
- Since:
- 2003.08.06 (Christian Borgelt)
-
validRing
protected abstract boolean validRing()Check whether the current ring extension is valid.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.- Returns:
- whether the ring is valid (has the correct form)
- Since:
- 2005.08.11 (Christian Borgelt)
-
initVars
protected abstract void initVars()Initialize the generation of equivalent ring extension variants.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.
- Since:
- 2006.07.06 (Christian Borgelt)
-
variant
protected abstract boolean variant()Create the next ring extension variant.- Returns:
- whether another ring variant was created
- Since:
- 2006.07.06 (Christian Borgelt)
- See Also:
-
adaptRing
Reorder the edges of a fragment with a ring extension.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.
- Parameters:
frag
- the fragment to adaptcheck
- whether to check the ring order- Returns:
- whether the ring adaptation succeeded, that is: -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.
- Since:
- 2006.07.01 (Christian Borgelt)
-
compareEdge
Compare two edges with the precedence order of the canonical form.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.
- Parameters:
e1
- the first edge to comparee2
- the second edge to comparenext
- the index with which to number the next node- Returns:
- whether the first edge is smaller (-1) or greater than (+1) or equal to (0) the second edge
- Since:
- 2006.04.11 (Christian Borgelt)
-
removeRings
Remove the flags of all rings an edge is contained in.- Parameters:
edge
- the edge to process- Since:
- 2007.03.24 (Christian Borgelt)
-
prepare
Prepare the rings of a fragment for adaptation and order test.- Parameters:
frag
- the fragment to prepare- Returns:
- the fragment as a graph
- Since:
- 2007.03.24 (Christian Borgelt)
-
isRingKey
Check whether a prefix is a ring key.This function presupposes that the internal edge buffer contains the graph's edges in adapted order.
- Parameters:
graph
- the graph to checkedge
- the edge at the end of the prefix to check- Returns:
- thether a prefix is a ring key
- Since:
- 2007.03.23 (Christian Borgelt)
-
chain
protected boolean chain()Create a variable length chain extension.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 innext()
is limited and thus it may be that no variable length chain can be created. In this case this function returnsfalse
.- Returns:
- whether a chain extension was created
- Since:
- 2003.02.19 (Christian Borgelt)
-
compareToFrag
Compare the current extension to a given fragment.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.
- Parameters:
frag
- the fragment to compare to- Returns:
-1
,0
, or+1
as the fragment described by this extension is less than, equal to, or greater than the fragment given as an argument- Since:
- 2002.04.02 (Christian Borgelt)
-
compareRing
Compare the current ring extension to a fragment.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.- Parameters:
frag
- the fragment to compare to- Returns:
- whether the current extension is smaller (-1) or greater than (+1) or equal to (0) the given fragment
- Since:
- 2006.05.12 (Christian Borgelt)
-
hasUnclosableRings
Check whether a fragment contains unclosable rings.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.
- Parameters:
frag
- the fragment to check for unclosable rings- Returns:
- whether the given fragment contains unclosable rings
- Since:
- 2006.05.17 (Christian Borgelt)
-
makeFragment
Create a fragment from the current extension.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.
- Returns:
- the current extension as a fragment
- Since:
- 2005.08.10 (Christian Borgelt)
-
makeEmbedding
Create an embedding from the current extension.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.
- Returns:
- the current extension as an embedding
- Since:
- 2006.10.24 (Christian Borgelt)
-
initCanonic
Initialize a canonical form test or generation.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.
- Parameters:
graph
- the graph to make canonic or to checkfixed
- the number of fixed (immovable) edges- Since:
- 2003.08.06 (Christian Borgelt)
-
makeWord
Create the code word for a given 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()
.- Parameters:
graph
- the graph for which to create the code word- Returns:
- the number of generated "characters" (array entries)
- Since:
- 2006.05.03 (Christian Borgelt)
-
makeWord
Create the code word for the first edges of a given graph.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()
.- Parameters:
graph
- the graph for which to create the code wordedgecnt
- the number of edges to consider- Returns:
- the number of generated "characters" (array entries)
- Since:
- 2006.05.03 (Christian Borgelt)
-
makeWord
Create the (prefix of a) code word for a given edge array.- Parameters:
edges
- the array of edges for which to create the code wordn
- the number of edges to consider- Since:
- 2006.05.03 (Christian Borgelt)
-
compareWord
Compare the current code word to the one of the given 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).- Parameters:
graph
- the graph to compare to- Returns:
- whether the internal code word is smaller (-1) or greater than (+1) or equal to (0) the code word of the graph
- Since:
- 2006.06.07 (Christian Borgelt)
-
compareWord
Compare the current code word to the one of the given graph.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).- Parameters:
graph
- the graph to compare toedgecnt
- the number of edges to consider- Returns:
- whether the internal code word is smaller (-1) or greater than (+1) or equal to (0) the code word of the graph
- Since:
- 2006.06.07 (Christian Borgelt)
-
compareWord
Compare the current code word to the one of the given edge array.- Parameters:
edges
- the array of edges to compare ton
- the number of edges to consider- Returns:
- whether the internal code word is smaller (-1) or greater than (+1) or equal to (0) the code word of the edges array
- Since:
- 2006.06.07 (Christian Borgelt)
-
isCanonic
protected abstract int isCanonic(int ei, int ni, int cnt) Internal recursive function for the canonical form test.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.
- Parameters:
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodes- Returns:
- the lowest edge index at which the considered graph differs from the canonical form (in this recursion)
- Since:
- 2005.08.11 (Christian Borgelt)
-
isCanonic
Check whether a given graph is canonic.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 firstfixed
edges (return value -1), (3) the graph is not in canonical form, but does not differ in the firstfixed
edges (return value 0).- Parameters:
graph
- the graph to check for canonical formfixed
- the number of fixed edges- Returns:
- -1, if the graph differs from the canonical form
in the first
fixed
edges,
0, if the graph is not canonical, but does not differ from the canonical form in the firstfixed
edges (but only in some later edge description),
1, if the graph is canonical. - Since:
- 2005.08.11 (Christian Borgelt)
-
isCanonic
Check whether a given graph is canonic.- Parameters:
graph
- the graph to check for canonical form- Returns:
- whether the given graph is canonic
- Since:
- 2009.05.07 (Christian Borgelt)
-
makeCanonic
protected abstract boolean makeCanonic(int ei, int ni, int cnt) Internal recursive function for making a given graph canonic.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.- Parameters:
ei
- the current edge indexni
- the current node indexcnt
- the number of already numbered nodes- Returns:
- whether the considered graphs needs to be changed
- Since:
- 2006.05.03 (Christian Borgelt)
-
makeCanonic
Make a given graph canonic.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. Ifkeep = 0
, then all edges may change their positions, but the first node is kept. Only ifkeep = -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.- Parameters:
graph
- the graph to make canonickeep
- the number of edges to keep- Returns:
- whether the graphs needs to be changed
- Since:
- 2006.05.03 (Christian Borgelt)
-
makeCanonic
Make a given graph canonic.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.
- Parameters:
graph
- the graph to make canonic- Returns:
- whether the graphs needs to be changed
- Since:
- 2009.05.07 (Christian Borgelt)
- See Also:
-
equivClasses
Find the node equivalence classes for a given 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
.- Parameters:
graph
- the graph for which to find node equivalence classes- Returns:
- the class of the root node
- Since:
- 2011.03.01 (Christian Borgelt)
-
isCanExt
Check whether a given graph is a canonic extension of its base.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.- Parameters:
graph
- the graph to check- Returns:
- whether the given graph is a canonic extension
- Since:
- 2011.03.01 (Christian Borgelt)
-
makeMap
Build a map for reordering the nodes and edges.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 firstgraph.edgecnt
elements of this array contain the new indices of the edges, the nextgraph.nodecnt
elements contain the new indices of the nodes. The map is used to reorganize the embeddings of a fragment.- Parameters:
graph
- the graph for which to build the mapn
- the highest already fixed node index- Returns:
- whether the map is the identity (no change needed)
- Since:
- 2006.05.08 (Christian Borgelt)
-
describe
Create the code word for a given graph as a string.- Parameters:
graph
- the graph for which to create a code word- Returns:
- a code word (as a string) for the given graph
- Since:
- 2006.05.10 (Christian Borgelt)
-
describe
Create the code word for a given graph as a string.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).- Parameters:
graph
- the graph for which to create a code word stringcreate
- whether the code word needs to be created- Returns:
- a code word (as a string) for the given graph
- Since:
- 2006.05.10 (Christian Borgelt)
-
createCnF
Create an extension object corresponding to a given name.- Parameters:
name
- the name of the extension type- Returns:
- the created extension
- Since:
- 2009.08.04 (Christian Borgelt)
-