### Enumerating all path-split graphs

←Return to chapter

## 4.5. Enumerating all path-split graphs

The `CanonicalPathSplit` procedure in the previous section defines for all graphs G GG and choice of root operation r r r a canonical PSG G π G^\piG π, and thus a canonical set of anchors π\pi π that we write as π r(G)=π.\pi_r(G) = \pi. π r​(G)=π.

Instead of `CanonicalPathSplit`, we can equivalently consider a `CanonicalAnchors` procedure, which computes π r(G)\pi_r(G)π r​(G) directly instead of the graph G π r(G)G^{\pi_r(G)}G π r​(G).

We formulate this computation below, using recursion instead of a `for` loop. This form generalises better to the `AllAnchors` procedure that we will introduce next.

The equivalence of the `CanonicalAnchors` procedure with `CanonicalPathSplit` follows from the observation made in section 4.2 that ordering operations in lexicographic order of the port labels is equivalent to a depth-first traversal of the graph.

`CanonicalAnchors` implements a recursive depth-first traversal (DFS), with the twist that the recursion is explicit only on the anchor nodes and otherwise relying on the lexicographic ordering just like in `CanonicalPathSplit`: lines 5–15 of `CanonicalAnchors` correspond to the iterations of the `for` loop (line 11–20) of `CanonicalPathSplit` until an anchor operation is found (i.e. the `else` branch on lines 18–20 is executed). From there, the graph traversal proceeds recursively.

We introduce the `ConnectedComponent`, `Neighbours` and `RemoveOperation` procedures; the first returns the connected component of the current operation, whereas the other two procedures are used to traverse, respectively modify, the graph G GG. Importantly, `Neighbours(G, op)` returns the neighbours of `op` ordered by port label order.

To ensure that the recursive DFS does not visit the same operation twice, we modify the graph with `RemoveOperation` on lines 11 and 15, ensuring that no visited operation remains in `G`. As a consequence, `CanonicalAnchors` may be called on disconnected graphs, which explains why an additional call to `ConnectedComponent` (line 4) is required.

Proposition 4.8Equivalence of `CanonicalPathSplit` and `CanonicalAnchors`

Let G GG be a connected graph and let r r r be a root operation in G GG. Then `CanonicalAnchors` maps the graph to the canonical anchor set:

(G, r,{})↦(π(G)r, L,∅),(G, r, \{\}) \mapsto (\pi(G)_r, L, \varnothing),(G, r,{})↦(π(G)r​,L,∅),

where L LL is the set of all paths in G GG and ∅\varnothing∅ designates the empty graph.

The proof follows directly from the previous paragraphs.

     1def CanonicalAnchors(
     2    G: Graph, root: Operation, seen_paths: Set[int]
     3) -> (Set[Operation], Set[int], Graph):
     4  operations = Operations(ConnectedComponent(G, root))
     5  # sort by PathAsPortLabels, as previously
     6  sorted_operations := sort(operations)
     7  operations_queue := queue(sorted_operations)
     8
     9  # Skip all operations that are not anchors
    10  op := operations_queue.pop() # never emtpy, contains root
    11  G = RemoveOperation(G, op)
    12  while len(LinearPaths(G, op)) == 1 or
    13        issubset(LinearPaths(G, op), seen_paths):
    14    op = operations_queue.pop() or return ({}, {}, G)
    15    G = RemoveOperation(G, op)
    16
    17  # op is anchor, update seen_paths and recurse
    18  seen_paths = union(seen_paths, LinearPaths(G, op))
    19  anchors := [op]
    20  # sort by port labels
    21  for child in Neighbours(G, op):
    22    (new_anchors, seen_paths, G) = CanonicalAnchors(
    23        G, child, seen_paths
    24    )
    25    anchors += new_anchors
    26
    27  return (anchors, seen_paths, G)

#### Maximal PSGs #

In addition to “simplifying” the data required to define path splitting, the definition of PSGs using anchor operations has another advantage that is fundamental to the pattern matching algorithm.

Consider the rooted dual tree τ r(G π)\tau_r(G^\pi)τ r​(G π) of a PSG with root operation r r r in G π G^\piG π. Recall that tree nodes are uniquely identified by their path from the root and thus are considered equal if they are isomorphic as graphs. We can in the same way define a tree inclusion relation ⊆\subseteq⊆ on rooted dual trees that corresponds to checking that the trees have the same root and that the left-hand side is isomorphic to a subtree of the right-hand side. We also require that the operation weights given by the s p l i t splits pl it map s p l i t splits pl it map coincide on the common subtree.

Proposition 4.9Maximal PSG

Let G GG be a connected graph, π\pi π a set of operations in G GG and r∈π r \in \pi r∈π a root operation. Consider the set G π={H⊆G∣π r(H)=π}.\mathcal{G}_\pi = \{H \subseteq G \mid \pi_r(H) = \pi \}.G π​={H⊆G∣π r​(H)=π}.

There is a subgraph M⊆G M \subseteq G M⊆G such that for all subgraphs H∈G X H \in \mathcal{G}_X H∈G X​: H⊆M H \subseteq M H⊆M. Furthermore, for all graph P P P, there is r′r'r′ and π′=π(P)r′\pi' = \pi(P)_{r'}π′=π(P)r′​ such that

P≃H∈G X⇔τ r′(P π′)⊆τ r(M π).P \simeq H \in \mathcal{G}_X \quad\Leftrightarrow\quad \tau_{r'}(P^{\pi'}) \subseteq \tau_r(M^\pi).P≃H∈G X​⇔τ r′​(P π′)⊆τ r​(M π).

We call M π M^\pi M π the maximal PSG with anchors π\pi π in G GG.

The proof gives an explicit construction for M M M.

Assume G X≠∅\mathcal{G}_X \neq \varnothing G X​=∅, otherwise the statement is trivial.

Construction of M M M. Let L LL be the set of linear paths in G GG that go through at least one operation in π\pi π. Consider the set of operations O L O_L O L​ in G GG given by the operations whose linear paths are contained in L LL. This defines a subgraph G∣O L G|_{O_L}G∣O L​​ of G GG. Since G X≠∅\mathcal{G}_X \neq \varnothing G X​=∅, there exists H∈G X H \in \mathcal{G}_X H∈G X​. By assumption, H H H is connected, and thus the anchors π\pi π of H H H are connected in H H H. There is therefore a connected component M⊆G∣O L M \subseteq G|_{O_L}M⊆G∣O L​​ that contains the set π\pi π.

Well-definedness of M π M^\pi M π. Consider the PSG M π M^\pi M π of M M M. We must show that M π M^\pi M π is a tree-like graph for the proposition statement to be well-defined. In other words, we must show that the interaction graph I\mathcal{I}I of M π M^\pi M π is acyclic and connected. M M M is connected by construction, which implies connectedness of M π M^\pi M π and thus of I\mathcal{I}I. It is acyclic because w i d t h(M)=∣π∣+1 width(M) = |\pi| + 1 w idth(M)=∣π∣+1 and M M M has exactly ∣π∣|\pi|∣π∣ operations on more than one linear path. I\mathcal{I}I is a thus a tree.

H⊆M H \subseteq M H⊆M. For any subgraph H∈G X H \in \mathcal{G}_X H∈G X​, its operations must be contained in O L O_L O L​. Since any H∈G H \in \mathcal{G}H∈G is connected and contains π\pi π, it must further hold that H⊆M H \subseteq M H⊆M.

We can now prove the ⇔\Leftrightarrow⇔ equivalence of (1).

⇐\Leftarrow⇐: If τ r′(P π′)⊆τ r(M π)\tau_{r'}(P^{\pi'}) \subseteq \tau_r(M^\pi)τ r′​(P π′)⊆τ r​(M π), then there exists H′⊆M π H' \subseteq M^\pi H′⊆M π with rooted dual tree

τ r(H π)=τ r(P π′).\tau_r(H^\pi) = \tau_r(P^{\pi'}).τ r​(H π)=τ r​(P π′).

Furthermore, by definition of ⊆\subseteq⊆ on rooted trees, a s p l i t splits pl it map is defined on H′H'H′, given by the s p l i t splits pl it map of M π M^\pi M π on the domain H′H'H′. Recall from section 4.3 that there is a map σ\sigma σ that maps

(H′,s p l i t)⟼σ H and(M π, s p l i t)⟼σ M.(H', split) \overset{\sigma}{\longmapsto} H\quad\textrm{and}\quad(M^\pi, split) \overset{\sigma}{\longmapsto} M.(H′,s pl it)⟼σ​H and(M π, s pl it)⟼σ​M.
It merges split operations pairwise, and thus it is immediate that H′⊆M π H' \subseteq M^\pi H′⊆M π implies H⊆M H \subseteq M H⊆M. Thus H∈G X H \in \mathcal{G}_X H∈G X​ and H′=H π H' = H^\pi H′=H π. By construction, one can also derive that P≃H P \simeq H P≃H. The statement follows.

⇒\Rightarrow⇒: Since H∈G X H \in \mathcal{G}_X H∈G X​, we know from point 1 that H⊆M H \subseteq M H⊆M. Thus we can define an injective embedding φ: P→M\varphi: P \to Mφ: P→M.

Operation splitting leaves the set of values from H H H to H π H^\pi H π, as well as from M M M to M π M^\pi M π unchanged. Similarly, there is a bijection between values in H π H^\pi H π and M π M^\pi M π and thus between edges in τ r(H π)\tau_r(H^\pi)τ r​(H π) and τ r(M π)\tau_r(M^\pi)τ r​(M π). The pattern embedding φ\varphiφ hence defines an injective map ϕ E\phi_Eϕ E​ from tree edges in τ r(H π)\tau_r(H^\pi)τ r​(H π) to tree edges in τ r(M π)\tau_r(M^\pi)τ r​(M π). We extend this map to a map on the trees ϕ: τ r(H π)→τ r(M π)\phi: \tau_r(H^\pi) \to \tau_r(M^\pi)ϕ: τ r​(H π)→τ r​(M π) by induction over the nodes set of τ r(H π)\tau_r(H^\pi)τ r​(H π). We start by the root map ϕ(r)=r\phi(r) = rϕ(r)=r. Using ϕ E\phi_Eϕ E​, we can then uniquely define the image of any child node of r r r in τ r(H π)\tau_r(H^\pi)τ r​(H π), and so forth inductively.

We show now that the map ϕ\phiϕ thus defined is injective. Suppose v, v′v, v'v, v′ are nodes in τ r(H π)\tau_r(H^\pi)τ r​(H π) such that ϕ(v)=ϕ(v′)\phi(v) = \phi(v')ϕ(v)=ϕ(v′). By the inductive construction there are paths from the root r r r to v v v and v′v'v′ respectively such that their image under ϕ E\phi_Eϕ E​ are two paths from r r r to ϕ(v)=ϕ(v′)\phi(v) = \phi(v')ϕ(v)=ϕ(v′). But τ r(M π)\tau_r(M^\pi)τ r​(M π) is a tree, so both paths must be equal. By bijectivity of ϕ E\phi_Eϕ E​, it follows v=v′v = v'v=v′, and thus ϕ\phiϕ is injective. Finally, the value and operation weights are invariant under pattern embedding and thus are preserved by definition.

This result means that instead of listing all PSGs for every possible subgraph of G GG, it is sufficient to proceed as follows:

1. for every pattern P P P, fix a root operation r P r_P r P​ and construct the rooted tree dual of the canonical PSG
   τ P:=τ r P(P π r P(P)).\tau_P := \tau_{r_P}(P^{\pi_{r_P}(P)}).τ P​:=τ r P​​(P π r P​​(P)).
2. enumerate every possible root operation r r r in G GG,
3. enumerate every possible sets of anchors π\pi π in G GG with root r r r,
4. for each set π\pi π, find the maximal PSG M M M with anchors π\pi π in G GG, and take its rooted tree dual τ M:=τ r(M π)\tau_M := \tau_r(M^\pi)τ M​:=τ r​(M π),
5. find all patterns P P P such that τ P⊆τ M\tau_P \subseteq \tau_M τ P​⊆τ M​.

In other words, if `AllAnchors` is a procedure that enumerates all possible sets of anchors π\pi π in G GG and `MaximalPathSplit` computes the maximal PSG M M M as presented in the proof of Proposition 4.9, then `AllPathSplits(G)` can simply be obtained by calling `AllAnchors` and then returning their respective maximal PSGs in G GG:

    def AllPathSplits(G: Graph, root: Operation) -> Set[Graph]:
      all_anchors = AllAnchors(G, root)
      return {MaximalPathSplit(G, pi) for pi in all_anchors}

#### The missing piece: `AllAnchors` #

We can now complete the definition of `AllPathSplits` by defining the `AllAnchors` procedure, which enumerates all possible sets of anchors in G GG given a root operation r r r.

The procedure is similar to `CanonicalAnchors`, described in detail in the previous paragraphs. In addition to the arguments of `CanonicalAnchors`, `AllAnchors` requires a width w≥1 w \geq 1 w≥1 argument. It then returns all sets of at most w w w operations1 that form the canonical anchors of some width-w w w subgraph of G GG with root r r r. The main difference between `CanonicalAnchors` and `AllAnchors` is that the successive recursive calls (line 22 in `CanonicalAnchors`) are replaced by a series of nested loops (lines 42–48 in `AllAnchors`) that exhaustively iterate over the possible outcomes for different subgraphs of G GG. The results of every possible combination of recursive calls are then collected into a list of anchor sets, which is returned.

The part of the pseudocode that is without comments is unchanged from `CanonicalAnchors`. Using Proposition 4.3, we know that we can assume that every operation has at most 3 children, and thus 3 neighbours in `G`, given that the operations equivalent to parent nodes were removed.

     1def AllAnchors(
     2    G: Graph, root: Operation, w: int,
     3    seen_paths: Set[int] = {}
     4) -> List[(Set[Operation], Set[int], Graph)]:
     5  # Base case: return one empty anchor list
     6  if w == 0:
     7    return [({}, {}, G)]
     8
     9  operations = Operations(ConnectedComponent(G, root))
    10  sorted_operations := sort(operations)
    11  operations_queue := queue(sorted_operations)
    12
    13  op := operations_queue.pop()
    14  G = RemoveOperation(G, op)
    15  while len(LinearPaths(G, op)) == 1 or
    16        issubset(LinearPaths(G, op), seen_paths):
    17    op = operations_queue.pop() or return [({}, {}, G)]
    18    G = RemoveOperation(G, op)
    19
    20  seen0 = union(seen_paths, LinearPaths(G, op))
    21  # There are always at most three neighbours: we
    22  # unroll the for loop of CanonicalAnchors.
    23  [child1, child2, child3] = Neighbours(G, op)
    24  # Iterate over all ways to split w-1 anchors over
    25  # the three children and solve recursively
    26  all_anchors = []
    27  for 0 <= w1, w2, w3 < w with w1 + w2 + w3 == w - 1:
    28    for (anchors1, seen1, G1) in
    29        AllAnchors(G, child1, w1, seen0):
    30      for (anchors2, seen2, G2) in
    31          AllAnchors(G1, child2, w2, seen1):
    32        for (anchors3, seen3, G3) in
    33            AllAnchors(G2, child3, w3, seen2):
    34          # Concatenate new anchor with anchors from all paths
    35          anchors = union([op], anchors1, anchors2, anchors3)
    36          all_anchors.push((anchors, seen3, G3))
    37  return all_anchors

We can represent the sequence of recursive calls to `AllAnchors` as a tree. The call tree for the graph used as example to illustrate `CanonicalAnchors` earlier is given on the next page.

We now show correctness of the procedure. Let us write Π r w(G)\Pi_r^w(G)Π r w​(G) for the set of sets of anchors returned by `AllAnchors(G, r, w, {})`.

Proposition 4.11Correctness of AllAnchors

Let G GG be a graph and H⊆G H \subseteq G H⊆G be a subgraph of G GG of width w w w. Let r r r be a choice of root operation in H H H. We have π r(H)⊆Π r w(G).\pi_r(H) \subseteq \Pi_r^w(G).π r​(H)⊆Π r w​(G).

A call tree for an execution of `AllAnchors` on the example graph of the previous figure with w=3 w = 3 w=3. Starting from the root, each node in the tree corresponds to either picking an operation as anchor or not (thus splitting it). Edges are labelled by the values assigned to w w w for the respective children of the source node. One path from root to leaf leads to no solution (it is impossible to find an unseen linear path from operation b bb. The other paths each lead to a valid set of three anchors.

The proof is by induction over the width w w w of the subgraph H H H. The idea is to map every recursive call in `CanonicalAnchors` to one of the calls to `AllAnchors` on lines 29, 31 or 33. All recursive results are concatenated on line 36, and thus, the value returned by `CanonicalAnchors` will be one of the anchor sets in the list returned by `AllAnchors`.

Let H⊆G H \subseteq G H⊆G be a connected subgraph of G GG of width w w w. We prove inductively over w w w that if (X, S′,H′)=(X, S', H') = (X, S′,H′)=`CanonicalAnchors`$(H, r,S)$ then there is a graph G′G'G′ such that H′⊆G′⊆G H' \subseteq G' \subseteq G H′⊆G′⊆G such that

(X, S′,G′)∈(X, S', G') \in(X, S′,G′)∈ `AllAnchors`(G, r, w, S)(G, r, w, S)(G, r, w, S)

for all valid root operations r r r of H H H and all subsets of the linear paths of H H H in `seen_paths`. The statement in the proposition directly follows this claim.

For the base case w=1 w = 1 w=1, `CanonicalAnchors` will return the anchors `anchors = [op]` as defined on line 19: there is only one linear path, and it is already in `seen_paths`, thus for every recursive call to `CanonicalAnchors`, the `while` condition on line 12 will always be satisfied until all operations have been exhausted and empty sets are returned. In `AllAnchors`, on the other hand, The only values of `w1`, `w2` and `w3` that satisfy the loop condition on line 27 for w=1 w = 1 w=1 are `w1` === `w2` === `w3` =0= 0=0. As a result, given the `w` =0=0=0 base case on lines 6–7, the lines 35 and 36 of `AllAnchors` are only executed once, and the definition of `anchors` on line 36 is equivalent to its definition in `CanonicalAnchors`.

We now prove the claim for w>1 w > 1 w>1 by induction. As documented in `AllAnchors`, we can assume that every operation has at most 3 children. This simplifies the loop on lines 21–25 of `CanonicalAnchors` to, at most, three calls to `CanonicalAnchors`.

Consider a call to `CanonicalAnchors` for a graph H⊆G H \subseteq G H⊆G, a root operation r r r in H H H and a set S S S of linear paths. Let w a w_a w a​, w b w_b w b​ and w c w_c w c​ be the length of the values returned by the three recursive calls to `CanonicalAnchors` of line 22 for the execution of `CanonicalAnchors` with arguments H H H, r r r and S S S. Let c a, c b c_a, c_bc a​,c b​ and c c c_cc c​ be the three neighbours of r r r in H H H. If the child c x c_xc x​ does not exist, then one can set w x=0 w_x = 0 w x​=0 and it can be ignored – the argument below still holds in that case. The definition of `seen0` on line 20 in `AllAnchors` coincides with the update to the variable `seen_paths` on line 18 of `CanonicalAnchors`; similarly, the updates to `G` on lines 14 and 18 of `AllAnchors` are identical to the lines 11 and 15 of `CanonicalAnchors` that update `H`. Let the updated `seen_paths` be the set S a S_a S a​, the updated `G` be G a G_aG a​ and the updated H H H be H a H_a H a​, with H a⊆G a H_a \subseteq G_a H a​⊆G a​.

As every anchor operation reduces the number of unseen linear paths by exactly one (using the simplifying assumptions of section 4.2), it must hold that w a+w b+w c+1=w w_a + w_b + w_c + 1 = w w a​+w b​+w c​+1=w. Thus, for a call to `AllAnchors` with the arguments G GG, r r r, w w w and S S S, there is an iteration of the `for` loop on line 27 of `AllAnchors` such that `w1` =w a= w_a=w a​, `w2` =w b= w_b=w b​ and `w3` =w c= w_c=w c​. It follows that on line 29 of `AllAnchors`, the procedure is called recursively with arguments (G a, c a, w a, S a)(G_a, c_a, w_a, S_a)(G a​,c a​,w a​,S a​). From the induction hypothesis, we obtain that there is an iteration of the `for` loop on line 29 in which the values of `anchors1` and `seen1` coincide with the values of the `new_anchors` and `seen_paths` variables after the first iteration of the `for` loop on line 21 of `CanonicalAnchors`. Call the value of `seen1` (and `seen_paths`) S b S_b S b​. Similarly, call the updated value of `G` in `AllAnchors` G b G_bG b​ and the updated value of `G` in `CanonicalAnchors` H b H_b H b​. We have, by the induction hypothesis, that H b⊆G b H_b \subseteq G_b H b​⊆G b​.

Repeating the argument, we obtain that there are iterations of the `for` loops on lines 30 and 32 of `AllAnchors` that correspond to the second and third recursive calls to `CanonicalAnchors` on line 22 of the procedure. Finally, the concatenation of anchor lists on line 36 of `AllAnchors` is equivalent to the repeated concatenations on line 25 of `CanonicalAnchors`, and so we conclude that the induction hypothesis holds for w w w.

We will see that the overall runtime complexity of `AllAnchors` can be easily derived from a bound on the size of the returned list. For this, we use the following result:

Proposition 4.10Number of anchor sets in `AllAnchors`
For a graph G GG, a root operation r r r in G GG and 1≤w≤w i d t h(G)1 \leq w \leq width(G)1≤w≤w idth(G), the length of the list `AllAnchors`(G, r, w)(G, r, w)(G, r, w) is in O(c w⋅w−3/2)O(c^w \cdot w^{-3/2})O(c w⋅w−3/2), where c=6.75 c = 6.75c=6.75 is a constant.

Let C w C_w C w​ be an upper bound for the length of the list returned by a call to `AllAnchors` for width w w w. For the base case w=0 w = 0 w=0, C 0=1 C_0 = 1 C 0​=1. The returned `all_anchors` list is obtained by pushing anchor lists one by one on line 36. We can count the number of times this line is executed by multiplying the length of the lists returned by the recursive calls on lines 28–32, giving us the recursion relation

C w≤∑0≤w 1, w 2, w 3<w w 1+w 2+w 3=w−1 C w 1⋅C w 2⋅C w 3. C_w \leq \sum_{\substack{0 \leq w_1, w_2, w_3 < w\\w_1 + w_2 + w_3 = w - 1}} C_{w_1} \cdot C_{w_2} \cdot C_{w_3}.C w​≤0≤w 1​,w 2​,w 3​<w w 1​+w 2​+w 3​=w−1​∑​C w 1​​⋅C w 2​​⋅C w 3​​.

Since C w C_w C w​ is meant to be an upper bound, we replace ≤\leq≤ with equality above to obtain a recurrence relation for C w C_w C w​. This recurrence relation is a generalisation of the well-known Catalan numbers Stanley, 2015Richard P. Stanley. 2015. Catalan Numbers. Cambridge University Press. doi: 10.1017/CBO9781139871495, equivalent to counting the number of ternary trees with w w w internal nodes: a ternary tree with w≥1 w \geq 1 w≥1 internal nodes is made of a root along with three subtrees with w 1, w 2 w_1,w_2 w 1​,w 2​ and w 3 w_3 w 3​ internal nodes respectively, with w 1+w 2+w 3=w−1 w_1 + w_2 + w_3 = w-1 w 1​+w 2​+w 3​=w−1. A closed form solution to this problem can be found in Aval, 2008Jean-Christophe Aval. 2008. Multivariate Fuss–Catalan numbers. Discrete Mathematics 308, 20 (October 2008, 4660–4669). doi: 10.1016/j.disc.2007.08.100​:

C w=(3 w w)2 w+1=Θ(c w w 3/2)C_w = \frac{{3w \choose w}}{2w + 1} = \Theta \left(\frac{c^w}{w^{3/2}} \right)C w​=2 w+1(w 3 w​)​=Θ(w 3/2 c w​)

satisfying the above recurrence relation with equality, where c=27/4=6.75 c = 27/4 = 6.75c=27/4=6.75 is a constant obtained from the Stirling approximation:

(3 w w)=(3 w)!(2 w)!w!=Θ(1 w)((3 w)3 e 3)w(e 2(2 w)2)w(e w)w=Θ((27/4)w w 1/2).\begin{aligned}{3w \choose w} = \frac{(3w)!}{(2w)!w!} &= \Theta\left(\frac{1}{\sqrt{w}}\right) \Big(\frac{(3w)^3}{e^3}\Big)^{w}\Big(\frac{e^2}{(2w)^2}\Big)^{w}\Big(\frac{e}{w}\Big)^{w}\\ &= \Theta\left(\frac{(27/4)^w}{w^{1/2}}\right).\end{aligned}(w 3 w​)=(2 w)!w!(3 w)!​​=Θ(w
​1​)(e 3(3 w)3​)w((2 w)2 e 2​)w(w e​)w=Θ(w 1/2(27/4)w​).​

To obtain a runtime bound for `AllAnchors`, it is useful to identify how much of G GG needs to be traversed. If we suppose all patterns have at most depth d dd, then it immediately follows that any operation in G GG that is in the image of a pattern embedding must be at most a distance d dd away from an anchor operation. We can thus equivalently call `AllAnchors` on a subgraph of G GG such that no linear path is longer than 2 d 2d2d. We thus obtain the following runtime.

Proposition 4.12Runtime of `AllAnchors`

For patterns with at most width w w w and depth d dd, the total runtime of `AllAnchors` is in

O(c w⋅d w 1/2).O\left(\frac{c^w \cdot d}{w^{1/2}}\right).O(w 1/2 c w⋅d​).

We restrict `Operations` on line 9 to only return the first d dd operations on the linear path in each direction, starting at the anchor operation: operations more than distance d dd away from the anchor cannot be part of a pattern of depth d dd.

We use the bound on the length of the list returned by calls to `AllAnchors` of Proposition 4.10 to bound the runtime. We can ignore the non-constant runtime of the concatenation of the outputs of recursive calls on line 35, as the total size of the outputs is asymptotically at worst of the same complexity as the runtime of the recursive calls themselves. Excluding the recursive calls, the only remaining lines of `AllAnchors` that are not executed in constant time are the `while` loop on lines 15–18 and the `Operations` and `sort` calls on lines 9–11. Using the same argument as in `CanonicalAnchors`, we can ignore the latter two calls by replacing the queue of operations by a lazy iterator of operations. The next operation given `op` and the graph `G` can always be computed in O(1)O(1)O(1) time using a depth-first traversal of `G`.

Consider the recursion tree of `AllAnchors`, i.e. the tree in which the nodes are the recursive calls to `AllAnchors` and the children are the executions spawned by the nested `for` loops on line 28–32. This tree has at most

C w=Θ(c w w 3/2)C_w = \Theta\left(\frac{c^w}{w^{3/2}}\right)C w​=Θ(w 3/2 c w​)

leaves. A path from the root to a leaf corresponds to a stack of recursive calls to `AllAnchors`. Along this recursion path, `seen_paths` set is always strictly growing (line 35) and the operations removed from `G` on lines 14 and 18 are all distinct. For each linear path, at most 2 d 2d2d operations are traversed. Thus the total runtime of the `while` loop (lines 15–18) along a path from root to leaf in the recursion tree is in O(w⋅d)O(w \cdot d)O(w⋅d). We can thus bound the overall complexity of executing the entire recursion tree by O(C w⋅w⋅d)=O(c w⋅d w 1/2)O(C_w \cdot w \cdot d) = O(\frac{c^w \cdot d}{w^{1/2}})O(C w​⋅w⋅d)=O(w 1/2 c w⋅d​).

1. Every anchor operation is on at least one previously unseen linear path, thus there can be at most w w w operations in the set of anchors. ↩︎

←Return to chapter