# Similar Supergraph Search Based on Graph Edit Distance
## 5 Method for Traversing Prefix Tree for Constrained Problem  
In order to overcome drawback (1), described in the previous section, we introduce the following lemma. **Lemma 6**. : _Given two AcGM codes \(c\) and \(c^{\prime}\), we have the following:_  
\[ed(pre(c,i),pre(c^{\prime},i))\leq ed(pre(c,j),pre(c^{\prime},j))\text{ for }i<j. \tag{11}\]  
_In the case that \(i\) is greater than the number of fragments in \(c\), we assume that \(pre(c,i)\) is equivalent to \(c\) itself._  
Proof. : \(ed(pre(c,i+1),pre(c^{\prime},i+1))\) is the sum of \(ed(pre(c,i),pre(c^{\prime},i))\) and the number of edits between the \(i+1\)-th fragments of \(pre(c,i+1)\) and \(pre(c^{\prime},i+1))\). Since the number of edits is non-negative, \(ed(pre(c,i),pre(c^{\prime},i))\) increases monotonically when \(i\) is increased. Therefore, for \(i<j\), we have \(ed(pre(c,i),pre(c^{\prime},i))\leq ed(pre(c,j),pre(c^{\prime},j))\). **Colloratory 2**. : _According to Lemma 6, if \(ed(pre(c,i),pre(c^{\prime},i))>\theta\), then \(ed(c,c^{\prime})>\theta\)._  
As a consequence of Lemma 6 and Corollary 11, when \(ed(pre(c,i),pre(c^{\prime},i))>\theta\), we can stop the computation in Line 7 of Algorithm 1. **Lemma 7**. : _Given the two following fragments:_  
\[s = \ell(u_{i})x_{1,i}\cdots x_{i-1,i} \tag{12}\] \[s^{\prime} = \ell(u^{\prime}_{i})x^{\prime}_{1,i}\cdots x^{\prime}_{i-1,i}, \tag{13}\]  
_for which their lengths are equal, the number of edits ed\((s,s^{\prime})\) to equalize the fragments is as follows:_  
\[ed(s,s^{\prime})= \begin{cases}1+\sum\limits_{1\leq j<i}\delta^{\prime}(0,x^{ \prime}_{j,i})&(s=null)\\ 1+\sum\limits_{1\leq j<i}\delta^{\prime}(x_{j,i},0)&(s^{\prime}=null)\\ \delta^{\prime}(\ell(u_{i}),\ell(u^{\prime}_{i}))+\sum\limits_{1\leq j<i} \delta^{\prime}(x_{j,i},x^{\prime}_{j,i})&(otherwise).\end{cases}  \tag{14}\]  
_Since ed\((s,s^{\prime})\) is a symmetric function, ed\((s,s^{\prime})=ed(s^{\prime},s)\)._  
Proof. : Please see the proof for Lemma 3. Algorithm 2 shows the pseudocode for solving the problem defined by (4), which overcomes the aforementioned drawback (1). After obtaining the \(j\)-th fragments of AcGM codes \(c_{i}\) and \(c\) in Line 7 of the algorithm, the number of edits between the fragments is calculated according to Lemma 7. The number of edits is then added to the accumulated edit count \(ae\). According to Corollary 2, the algorithm stops the calculation of the number of edits between \(c_{i}\) and one of the AcGM codes of \(q\) in Line 8. However, because \(g_{i}\) is a member of the set defined in Equation (4) if the edited distance between \(c_{i}\) and at least one AcGM code in \(\Omega(q)\) is less than \(\theta\), these steps are repeated for all AcGM codes of \(q\). The time complexity of Algorithm 2 is \(O(|\Omega(q)|\sum_{i=1}|G||V(g_{i})|^{2})\). ```
Data:\(G=\{g_{1},g_{2},\ldots,g_{n}\}\), \(q\), and \(\theta\) Result:\(\{g_{i}\in G\mid\exists q^{\prime}\subseteq_{i}q\ s.t.\ ed(g_{i},q^{\prime})\leq\theta,q^{\prime}\text{is connected},|V(g_{i})|\leq|V(q^{\prime})|\}\)\(S\leftarrow\emptyset\);// /a variable for storing solutions for\(g_{i}\in G\)do\(c_{i}\gets code(g_{i})\); for\(c\in\Omega(q)\)do\(ae\gets 0\);//\(ae\) is accumulated edit count for\(j\in[1,|V(g_{i})|]\)do\(ae\gets ae+ed(frag(c_{i},j),frag(c,j))\); if\(ae>\theta\)then break; if\(j=|V(g_{i})|\)then\(S\leftarrow S\cup\{g_{i}\}\); if\(g_{i}\in S\)then break; return\(S\);
```  
**Algorithm 2**Straightforward Algorithm 2 for Searching (4)  
In order to overcome drawback (2), described in the previous section, we use a prefix tree for the AcGM codes for \(G\). **Definition 3** (Code Tree [17] (The detailed algorithm for constructing a code tree from a graph database \(G\) is given in [17].)). : _A code tree \(T\) is defined as the triplet \((\top,N,B)\), where \(\top\in N\) is the root node of the tree, \(N\) is a set of the nodes of the tree, and \(B\) is a set of the branches of the tree. In addition, each node is associated with a code fragment and a set of graph identifiers.