From 7dd4935230e303aef8d295d992239d59d95b32d7 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Thu, 5 Jan 2023 10:24:39 +0800 Subject: 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. --- chain/src/plan.org | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) (limited to 'chain') 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. -- cgit v1.2.3-18-g5258