diff options
Diffstat (limited to 'forest/src/iter/plan.org')
| -rw-r--r-- | forest/src/iter/plan.org | 187 |
1 files changed, 187 insertions, 0 deletions
diff --git a/forest/src/iter/plan.org b/forest/src/iter/plan.org new file mode 100644 index 0000000..4ef7db1 --- /dev/null +++ b/forest/src/iter/plan.org @@ -0,0 +1,187 @@ +#+TITLE: Plan for querying +#+AUTHOR: बुबोधयिषुः +#+DATE: <2024-01-11 Jeu 11:40> + +* Basic plan + +Basically speaking, we are trying to solve a subgraph isomorphism +problem, but for parse forests only. Moreover, each pattern node +specifies some condition that the target node should satisfy, like the +rule number, the grammar node number et cetera. This simply acts like +the filtering algorithms employed by the general subgraph isomorphism +algorithms. + +There is however one difference from the original problem: + +#+begin_quote +Edges might be matched by paths. +#+end_quote + +This means that some edges in the pattern graph could be matched by +paths in the (directed) target graph. Moreover, some edges require to +be siblings of some previously matched edges. This poses some +traditionally missing contraints. + +But anyways, we can consult the backtracing algorithms that were +written for the general problem to have an idea how to solve our +specific variant of the problem. + +** Filtering + +Our pattern nodes already specify some conditions for the target nodes +to match. So it is worth condidering whether or not we employ some +more powerful filtering techniques, like the iterative strenghthening +of the subgraph-isomorphism-compatible-labels algorithm. This can be +simply adapted to our situation since we have a natural candidate for +the labels: the pattern nodes have the matching conditions as labels, +whereas the target nodes have labels that are either grammar nodes or +rule numbers. We can define a partial order on this set of labels by +requiring that a matching condition is less than or equal to a target +label if and only if that target label satisfies the matching +condition. + +Then we simply apply the iterative strenghthening procedure, by +forming, from the label \(L\), the new label \(L\times N(L)\), where +\(N(L)\) is the function that sends each node \(n\) to the /multiset/ +\(\{L(m) \mid \text{Adj}(m, n)\}\), where \(\text{Adj}\) means that +the two nodes are adjacent. And we say that a multiset \(m_1\) is less +than or equal to another multiset \(m_2\) if and only if the bipartite +graph formed from these two multisets have a matching covering every +vertex corresponding to elements in \(m_1\). Note that this bipartite +graph has as nodes \(N_x^i\) for every \(x\in m_1\), where \(i = 0, \ldots, +m_1(x)\) and \(m_1(x)\) is the multiplicity of \(x\) in \(m_1\). Also +two nodes \(N_x^i\) and \(N_y^j\), where \(x\in m_1\) and \(y\in m_2\) are +adjacent if and only if \(x\leq y\). We can prove that if \(L\) is +subgraph-isomorphism-compatible, then this new label \(L\times N(L)\) is +also subgraph-isomorphism-compatible. + +As a consequence, we can iteratively construct new labels to filter +out wrong candidate pairs of pattern nodes and target nodes, until +this procedure does not yield stronger labels, which are guaranteed to +happen in polynomial time. + +** General sketch + +Since our starting label is already domain-specific, it might be +anticipated that this procedure can enhance the performance of the +algorithm a lot. This is the general sketch of the algorithm. + +* Two difficulties + +** When a branch is exhausted, how should we switch to another branch? + +To solve this issue, we need a data type with the following methods: + +- Follow nodes in the depth-first order +- Enumerate and switch to a specific "world line" in the forest: that + is, a forest is a pack of trees, and we match against each tree + separately; when a tree cannot be matched, we switch to the next + tree. + +All of this should be implemented efficiently, that is, within a +constant and "small" amount of operations. + +For now, the plan is to preprocess the forest to store the information +about each packed node in advance, and then the world line is defined +by which child of those packed nodes to use. Thus to switch world +line, we just change an array of numbers, which is pretty efficient I +suppose. + +** When a query cannot be matched, how should we fallback to a parent query? + +To solve this issue, we need a data type with the following methods: + +- Follow nodes in the depth-first order +- Jump to the parent and restore the querying context that was stored + earlier. + + We can consult the codes for general subgraph isomorphism problems + to implement this, since the general structure is the same. + +* Steps [1/4] + +** TO-THINK Preprocess the target graph + +The target needs to be preprocessed so that we know about the world +lines in advance, and we can generate some supplemental graphs as well +to facilitate the search. + +This may not be required anymore. + +** SOLVED Backtrack based on domains +We need to keep track of the domains. Can we find better ways to do +this? + +Maybe we can keep track of only the differences of the set of domains, +where each domain is a bitset. For the functionality of bit-sets, +[[https://docs.rs/bitset-core/latest/bitset_core/index.html][this crate]] is quite useful. + +Since this is an external crate, we may treat this feature as an +optionally enabled feature, and by default we use ordinary arrays of +booleans. The main advantage, in my opinion, provided by the external +crate is its SIMD-awareness, so the default implementation should not +lose exponential performance. + +A more serious problem is how to handle the packed nodes, or +equivalently how to treat different trees packed inside a forest. +Previously I was thinking of searching each packed tree separately, +but this is not respecting the shared structures of these trees, so +that we must waste a lot of efforts to search the same portions +multiple times. + +A better approach could be to ignore all children of packed nodes, and +treat the grand-chidlren of the packed nodes as their own children. +This way we do not need to waste efforts, and we need no special +treatment of different world-lines when searching. + +Here is a more formal description of the approach. + +- For each pattern vertex, associate a vector of target vertices, + initialized as a vector of vertices with the same boolean true + label of length the number of nodes of the target graph. +- Repeat the following steps. +- Find a pattern vertex with the smallest domain, tiebreaking by + randomly choosing one with the higher degree, excluding vertices + whose domains are either empty or singleton. + + If there is a vertex with empty domain, the pattern graph is not a + subgraph of the target graph. + + If every vertex has a singleton domain, return the found mapping. +- Find a "suitable" target vertex with highest degree within the + domain of the chosen vertex. + + If none exists, then we go back to the previous association of + some target vertex to some pattern vertex, and exclude that target + vertex from the domain of that pattern vertex, and then repeat the + process again. + * If no previous association exists, this means we happen to + choose one pattern vertex that cannot be mapped to the target + graph at the first step, so we can simply stop the algorithm and + decide that the pattern graph is not a subgraph of the target + graph. +- Record the mapping from the above pattern to the above target in the + list of associations, and filter other domains. + + We can filter by the degree. + + We can filter by the sequence of degrees of neighbors. + +** TODO Rapid restarts and no-good recording +This is a highly important optional improvement. + +** TODO Connect with the rest of the package + + +Now we want to connect the subgraph isomorphism solver with the rest +of the package. This requires a mechanism to convert from user-input +to a pattern graph, and then run the subgraph (isomorphism) solver to +find a mapping from the pattern graph to the parse-graph. + +In addition, there are some other constraints that might be imposed by +the user, such as to require that certain edges be siblings, or that +certain edges be non-repeating (either for nodes or for edges) paths +instead of plain edges. + +All these can be implemented at the filtering step as additional +requirements other than the neighbourhood-preserving constraint. + +Also the user may expect the neighbour relation to be directed. I am +not sure if this causes any trouble, but I need to deal with this +correctly to avoid potential disasters. + |