# Similar Supergraph Search Based on Graph Edit Distance
## 5 Method for Traversing Prefix Tree for Constrained Problem
Let \(s(n)\) be the concatenation of the fragments associated with nodes on the path from the root to node\(n\). When one of the AcGM codes of \(g_{i}\in G\) is the same as \(s(n)\), the set of graph identifiers for node \(n\) contains \(i\), which is the identifier of graph \(g_{i}\in G\)._  
The code fragment and graph identifiers associated with node \(n\) are denoted as \(fr(n)\) and \(ID(n)\), respectively. For the root node, \(fr(\top)=null\) and \(ID(\top)=\emptyset\). We present an example of a code tree below. **Example 3**. : _A graph database \(G=\{g_{1},g_{2},g_{3},g_{4}\}\) consists of four graphs, as shown in Figure 5. When one of the AcGM codes for each graph in \(G\) is generated, the AcGM codes for the four graphs are as follows._  
\[code(g_{1},\langle v_{1},v_{2},v_{3}\rangle) = ABaC0b,\] \[code(g_{2},\langle v_{1},v_{2},v_{3}\rangle) = ABaC0b,\] \[code(g_{3},\langle v_{1},v_{2}\rangle) = BBa,and\] \[code(g_{4},\langle v_{1},v_{2},v_{3}\rangle) = BBaC0b.\]  
_From these AcGM codes, a code tree is constructed, as shown in the right part of Figure 5. Node \(n_{6}\) of the tree is associated with the code fragment \(C0b\) and the set of graph identifiers \(ID(n)=\{1\}\). The concatenation of fragments associated with nodes on the path from the root to node \(n_{6}\) is \(ABaC0b\), which represents graph \(g_{1}\) in \(G\)._  
Algorithm 3 shows the pseudocode for searching for members of the set defined in Equation (4) by traversing the code tree. At node \(n\), Algorithm 3 adds vertex \(w\) of \(q\) to \(\langle w_{1},w_{2},\ldots,w_{h}\rangle\), from which the fragment \(s\) is generated, with the addition of the prefix \(code(q,\langle w_{1},w_{2},\ldots,w_{h}\rangle)\) of an AcGM code of \(q\). The algorithm then recursively traverses the children of \(n\) that have fragments similar to fragment \(s\). In contrast to Algorithm 2, which iteratively checks whether each individual graph in the graph database is a solution, Algorithm 3 checks whether multiple graphs in the database are simultaneously solutions. This is because each node in the code tree is associated with the common prefix of the AcGM codes of multiple graphs in the database. This simultaneous checking renders our search very efficient. The worst case time complexity of Algorithm 3 is the same as the time complexity of Algorithm 2. When AcGM codes of graphs in the database do not have common prefixes as one another, the time complexity of Algorithm 3 becomes worst. However, the codes usually have common prefixes as one another and the computation time that this algorithm needs is proportional to the number of nodes that Algorithm 3 traverses. In addition, at each node, Algorithm 3 needs \(O(h|V(q)||N|)\). Figure 5: Code tree. ```
Data: the set of graphs \(S\), query \(q\), threshold \(\theta\), current node \(n\), \(\langle w_{1},w_{2},\ldots,w_{h}\rangle\), and accumulated edit count \(ae\) Result:\(\{g_{i}\in G\mid\exists q^{\prime}\subseteq_{i}q\) s.t. \(ed(g_{i},q^{\prime})\leq\theta,q^{\prime}\)is connected, \(|V(g_{i})|\leq|V(q^{\prime})|\}\) \(S\leftarrow\mathrm{S}\cup\bigcup_{i\in ID(n)}\{g_{i}\}\); \(N\leftarrow\mathit{children}(n)\); \(C\leftarrow\{(w,s)\mid s_{1}s_{2}\cdots s_{h}s=code(q,\langle w_{1},w_{2}, \ldots,w_{h},w\rangle)\subseteq c,c\in\Omega(q)\}\); for\((m,(w,s))\in N\times C\)do \(e\gets ed(fr(m),s)\); if\(ae+e\leq\theta\)then \(\omega\leftarrow\langle w_{1},w_{2},\ldots,w_{h},w\rangle\); \(S\leftarrow\mathit{search}(S,q,\theta,m,\omega,ae+e)\); return\(S\);
```  
**Algorithm 3**Code Tree Search for Finding Solutions to Equation (4)