# Progressive Multiple Alignment of Graphs
## 3 Algorithmic Considerations
### Syntactic and Semantic Compatibility  
The compatibility test \(\texttt{compatible}(M,(x_{1},x_{2}))\) operates in two stages:  
_Syntactic compatibility_ requires, for each \((y_{1},y_{2})\in M\), that \(x_{1},y_{1}\) and \(x_{2},y_{2}^{\prime}\) preserve adjacency. For the pairwise alignment of graphs, syntactic compatibility is straightforward because there are no ambiguous edges: \((x_{1},x_{2})\) is syntactically compatible with \(M\) if and only if, for every \((y_{1},y_{2})\in M\), either both \(x_{1},y_{1}\) and \(x_{2},y_{2}\) are not adjacent or both \((x_{1},y_{1})\in E(G)\) and \((x_{2},y_{2})\in E(H)\). At this stage, ambiguous edges need to be handled. _Semantic compatibility_ requires that vertex labels are allowed to be aligned according the user-defined evaluation scheme. We denote by \(\lambda(x)\) and \(\lambda(x,y)\) the labels of vertices and edges. In general, the labels of vertices and edges in an alignment graph, i.e., \(\lambda(x)\) and \(\lambda(x,y)\) for alignment columns \(x\) and \(y\), are multisets of \"elementary\" labels defined on the input graphs, i.e., rows of the alignment. In general, the labels \(\lambda(x)\) and \(\lambda(x,y)\) are multisets of \"elementary\" labels defined on the input graphs. Moreover, we assume a relation that defines when two elementary vertex labels or two elementary edge labels are _compatible_. This pairwise compatibility rule can be chosen arbitrarily by the user. For alignments of alignments, label sets are compatible if and only if all pairs of labels are compatible, where gaps - are assumed to be compatible with all labels. In order to keep track of ambiguous edges, it is useful to consider a tri-partitions of \(V(G)\times V(H)\) into unambiguous edges \(E\), unambiguous non-edges \(Q\), and ambiguous edges \(A\). For simplicity, we write \(x_{1}x_{2}\) for the matching edges. Since semantic consistency in our setting is defined exclusively in terms of vertex and edge labels, the semantic filter can, in principle, be integrated with the syntactic consistency check. The discussion in the theory section immediately implies that a matching \(M\) is _consistent_ if and only if:  
1. the two vertex labels \(\lambda(x_{1})\), \(\lambda(x_{2})\) and the two vertex labels \(\lambda(y_{1})\), \(\lambda(y_{2})\) are compatible and
2. for all \(x_{1}x_{2},y_{1}y_{2}\in M\) one of the following conditions is satisfied: 1. \(\{x_{1},y_{1}\}\in E(G)\) and \(\{x_{2},y_{2}\}\in E(H)\) and the two edge labels \(\lambda(x_{1},y_{1})\) and \(\lambda(x_{2},y_{2})\) are are compatible, or 2. \(\{x_{1},y_{1}\}\in Q(G)\) and \(\{x_{2},y_{2}\}\in Q(H)\), or 3. \(\{x_{1},y_{1}\}\in A(G)\) or \(\{x_{1},y_{1}\}\in A(H)\). Clearly, the three conditions (i), (ii), and (iii) are mutually exclusive. Moreover, if \(M\) is consistently matching and \(x_{1}x_{2}\) is a candidate for extension, then \(M\cup\{x_{1}x_{2}\}\) is consistent if and only if the \(\lambda(x_{1})\) and \(\lambda(x_{2})\) are compatible and for every \(y_{1}y_{2}\in M\), one of the conditions (i), (ii), or (iii) is satisfied. Since each of the three conditions can be checked in constant time, testing whether \(M\) can be extended by \(x_{1}x_{2}\) requires \(O(|M|)\) time. These relationships immediately generalize to directed graphs: compatibility condition (i) then requires that also the direction of the edges matches, i.e.,  
1. If \(x_{1},y_{1}\) and \(x_{2},y_{2}\) are connected by directed edges, then \((x_{1},y_{1})\in E(G)\) iff \((x_{2},y_{2})\) and the labels of these directed edges, \(\lambda(x_{1},y_{1})\) and \(\lambda(x_{2},y_{2})\), are compatible. Ambiguous edges, on the other hand, are consistent with all edge directions and edge labels, as well as the absence of an edge. For a consistent matching \(M\), the corresponding graph \(K(M)\) and its ambiguous edges are uniquely defined by \(M\) as follows: In case (i), we have \(\{x_{1}x_{2},y_{1},y_{2}\}\in E(K(M))\). In case (ii), we have \(\{x_{1}x_{2},y_{1},y_{2}\}\in Q(K(M))\). In case (iii), we have to distinguish the following cases:  
1.