Skip to content

Draft: Fix graph regex unique

vincent lorrain requested to merge fixGraphRegexUnique into dev

Context

This merge request is a correction indirectly related to issue #91 (closed). It has become apparent that the definition of the unique node was incorrect because it should have one parent and one child.

The problem identified in the issue is due to :

  1. 'A*' Query given the folowing FSM:

	graph LR;
	classDef ref fill:#f96
	classDef start fill:#096

	s1(("q0")):::start
	q10(("q1")):::ref


	s1 --"is(A)"-->q10
	s1 --"E" --> q10
	q10 --"E" --> s1

where E are empty edge, (transition whith out test).

  1. The use of rejected nodes.

Originally, rejected nodes are used to verify that we are matching all possible traversable structures with the corresponding FSMs of the query. The basic principle is that when a traversal context encounters a common or unique node that does not validate, it is recorded in a common variable. To ensure that the regex match does not correspond to a sub-structure of a larger structure, all rejected nodes must be validated by at least one FSM from a query.

  1. the probleme

	graph LR;
	
	s1(("A"))
	q10(("B"))
	s1 -->q10

The problem is that for this example graph, starting from node A, the preceding FSM will validate node A and arrive in state Q1 on node B. In theory, the match is finished, but because there is transition E, we return to Q0 on node B. We attempt to make the unique transition, and node B is added to the rejected nodes. Since it's impossible to validate B, the match has no solution. Therefore, there is an issue with the definition of rejected nodes.

Modified files

  • FsmEdge.cpp correction of the unique node , correction of the definition of rejected nodes
  • RemoveFlatten.cpp FuseMulAdd.cpp Test_examples.cpp correctif due to the fix of unique node to add the Producer W,B in the query
  • FsmRunTimeContext.hpp , add a static clear to the rejected node to optimise the memory use

Detailed major modifications

The two main modifications are:

  • The correction of the unique edge to verify if there are no multiple parents and to impose a clear definition of the producer.
  • The correction of the definition of unique nodes necessitates manually defining the end of sequence.

TODO

  • Fix unique edge
  • Fix rejected nodes
  • Add $ end sequence
Edited by vincent lorrain

Merge request reports