Example for NEST graph measures using A*I #
A*I matches all nodes first, afterwards the edges are mapped.
Which nodes are chosen first is random. In this example, the workflow node is mapped first. As there is only one workflow node, the only possible mapping is \(WN_{ q }\) to \(WN_{ c }\) . The heuristic of this node is computed as follows:
\(h_{I} = \frac{ \left\lvert S.N \right\rvert + \left\lvert S.E \right\rvert }{ \left\lvert N_{q } \right\rvert + \left\lvert E_{ q } \right\rvert } = \frac{ 3 + 6 }{ 4 + 6 } = \frac{ 9 }{ 10 }\)The value of \(g_{I}\) represents the similarity of the partial mapping, thus \(0.1\) . So, the value of \(f_{I}\) , which is the sum of \(h_{I}\) and \(g_{I}\) is \(1\) .
Then, the task nodes are mapped to each other. Here, as first node \(TN1_{q}\) is chosen. It can be mapped to \(TN1_{c}\) or \(TN2_{c}\) . The other nodes were not considered, because a Task Node can only be mapped to another Task Node. For both, a new search node is created.
The similarity of \(TN1_{q}\)
to \(TN1_{c}\)
and \(TN2_{c}\)
is computed. In this case, the similarity of \(TN1_{q}\)
and \(TN1_{c}\)
is 1.0, because both are the same. The similarity of \(TN1_{q}\)
and \(TN2_{c}\)
is lower, the value depends on which similarity measure will be used for the semantic descriptors. For both search nodes, the heuristic \(h_{I}\)
is computed. Here, for each item which is not mapped yet a similarity value of 1.0 is assumed. The search node with the mapping \(TN1_{q}\)
to \(TN1_{c}\)
has the higher heuristic, so this is chosen and expanded. The heuristic of this node is computed as follows:
The value of \(g_{I}\) represents the similarity of the partial mapping, thus \(0.2\) . So, the value of \(f_{I}\) , which is the sum of \(h_{I}\) and \(g_{I}\) is \(1\) .
Now, the sets have the following items:
\(S.N = \left\{TN2_{ q }, DN1_{ q } \right\} \\ S.E = \left\{ POE1_{ q }, POE2_{ q }, POE3_{ q }, DE1_{ q }, DE2_{ q }, CE1_{ q } \right\}\)Next, the other Task Node \(TN2_{q}\)
is mapped. Because there is only one other element, which can be legally mapped, one search node is created. There, \(TN2_{q}\)
is mapped to \(TN2_{c}\)
, where the similarity is also 1.0. So, the value of the heuristic function \(h_{I}\)
is \(\frac{7}{10}\)
and the value of \(g_{I}\)
is 1.0 . So the value for \(f_{I}\)
is \(1\)
.
Now, the sets have the following items:
\(S.N = \left\{ DN1_{ q } \right\} \\ S.E = \left\{ POE1_{ q }, POE2_{ q }, POE3_{ q }, DE1_{ q }, DE2_{ q }, CE1_{ q } \right\}\)After mapping all of the Task Nodes, other nodes are chosen. The Data Nodes are selected next. There is also just one element for each graph. So, the only possible mapping is \(DN1_{q}\)
to \(DN1_{c}\)
. Using the String Equals measure, the similarity would be 0.0. So, the value for the heuristic would be
Now, the sets have the following items:
\(S.N = \left\{ \right\} \\ S.E = \left\{ POE1_{ q }, POE2_{ q }, POE3_{ q }, DE1_{ q }, DE2_{ q }, CE1_{ q } \right\}\)At this point, all nodes are mapped. So, the edges are considered next. Here, the order of the edges is also random.
First, the Part Of Edges are mapped. The item \(POE1_{q}\)
can be mapped to \(POE1_{ c }\)
, \(POE2_{c}\)
or \(POE3_{c}\)
. The only legal mapping is \(POE1_{q}\)
to \(POE1_{c}\)
, because the nodes of both edges are mapped to each other. The similarity value is 1.0. So, \(g_{I}\)
is updated to \(\frac{4}{10}\)
and the heuristic value \(h_{I}\)
is updated to \(\frac{5}{10}\)
. So, the value of the total function \(f_{I}\)
is \(\frac{9}{10}\)
.
Now, the sets have the following items:
\(S.N = \left\{ \right\} \\ S.E = \left\{ POE2_{ q }, POE3_{ q }, DE1_{ q }, DE2_{ q }, CE1_{ q } \right\}\)Afterwards, the other Part Of Edges are mapped the same way. \(POE2_{q}\)
is mapped to \(POE2_{c}\)
and \(POE3_{q}\)
to \(POE3_{c}\)
. The similarity values are also 1.0, so after mapping both the heuristic value \(h_{I}\)
is \(\frac{3}{10}\)
and the similarity of the mapped elements \(g_{I}\)
is \(\frac{6}{10}\)
such that the value of the total function \(f_{I}\)
= \(\frac{9}{10}\)
.
Now, the sets have the following items:
\(S.N = \left\{ \right\} \\ S.E = \left\{ DE1_{ q }, DE2_{ q }, CE1_{ q } \right\}\)In the next step, the Dataflow Edges are mapped. Also, here is just one legal mapping possible for each node. So, \(DE1_{ q }\)
is mapped to \(DE1_{ c }\)
and \(DE2_{ q }\)
to \(DE2_{ c }\)
. The similarity values are also 1.0, so the value for the total function \(f_{I}\)
remains \(\frac{9}{10}\)
.
Now, the sets have the following items:
\(S.N = \left\{ \right\} \\ S.E = \left\{ CE1_{ q } \right\}\)At last, the Controlflow Edges are mapped. Here, each graph has only one node. Both nodes can be legally mapped to each other. So, \(CE1_{q}\)
is mapped to \(CE1_{c}\)
. The similarity value is also 1.0. The heuristic value is updated to \( 0.0 \)
. The value \(g_{I}\)
is now equal to the total function \(f_{I}\)
with \(\frac{9}{10}\)
.
At last, the sets have the following items:
\(S.N = \left\{ \right\} \\ S.E = \left\{ \right\}\)At this point, all nodes and edges are mapped. The best possible similarity value is \(\frac{9}{10}=0.9 \) .