new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

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.
+