singly labelled graphs

Now I have a new type of labelled graphs, which can index vertices by
labels, but not index edges by labels.  The biggest difference is that
I do not have to keep a hashmap of edge targets by labels, and I do
not have to guard against the duplication of nodes with the same set
of edges.  I guard against nodes with the same label, though.

Also, in this graph, both vertices and edges have one label at a time,
whereas in the previous labelled graph there can be a multitude of
edges between the same source and target nodes, but with different
labels.

Now it remains to test this type of graphs, and to think through how
we attach forest fragments to nondeterministic finite automata edges,
and how to join forest fragments together while skipping nullable
edges, in order to finish the "compilation" part.

1 files changed, 12 insertions, 9 deletions

diff --git a/chain/src/plan.org b/chain/src/plan.org
index 61738a9..75acf30 100644
--- a/chain/src/plan.org
+++ b/chain/src/plan.org
@@ -7,7 +7,7 @@
 - [X] Implement builders for graphs
 - [X] Find sets of the first terminals for each non-terminal, in the
   grammar module.
-- [-] Establish a testing framework of various grammars. [5/6]
+- [-] Collect various grammars for testing. [5/6]
   + [X] One simple grammar
   + [X] Notes
   + [X] Parentheses
@@ -38,7 +38,11 @@
       finite automata.
     * [X] Test the removal of dead states, where a state is dead if
       and only if no other states have an edge into that state.
-- [ ] Refactor [0/3]
+- [-] Refactor [2/5]
+  + [X] Implement a data type for graphs with labels on vertices and
+    edges, but do not need to index edges by labels, which can index
+    vertices by labels instead.
+  + [X] Implement a builder that borrows a graph mutably.
   + [ ] When we pull in some regular language because of the
     left-linear expansion, we need to mark that branch as coming from
     left-linear expansions.  This is necessary because we cannot
@@ -62,13 +66,12 @@
   + [X] First define a trait with the expected behaviours.
   + [ ] Then implement them as doubly labelled graphs.
   + [ ] Thenimplement finding derivatives by use of the chain rule.
-- [-] Implement forests [0/2]
-  + [-] Define a trait with the expected behaviours.
-  + [ ] Implement them using adjacency list: we only need one label
-    per edge, and we do not wish to exclude duplicate edges, and we do
-    not need to index edges by the labels.  All in all, the labels can
-    be implemented by a simple hash map that maps edges to labels, so
-    a special data type is not needed here.
+- [-] Implement forests [1/2]
+  + [X] Define a trait with the expected behaviours.
+  + [-] Implement them using adjacency map: we only need one label per
+    edge, and we do not wish to exclude duplicate edges, and we do not
+    need to index edges by the labels.  All in all, we implement them
+    using a vector of hashmaps.
 - [ ] Implement semiring. [0/5]
   + [ ] Define the trait.
   + [ ] Implement the boolean semiring.