Algorithm to analyze Longest Common Subsequences (commonly known as LCS)

[norbert_bergman]

Hi together,

we use neo4j to handle almost 1.000.000 products as nodes which all have an individual sequence of process steps which are necessary to build the products.
Each single process step node is labeld via a relation to a structure of "label" nodes which groups similar process steps togehter.

The picture shows the graph as exampe diagram.

What I am now trying to do is finding similar products according to the "Level 1"-labels. Like shown in the picture there are 2 almost equal procucts. Only the first process step is different - so also the fist connected label of level 1 is different.
Step 1: I like to query neo4j to get a list of groups of products which for example share 75% of the same process sequence / sequence of Labels of level 1 .
Step 2: During this step I want to consider the labels of level 2. If I rerun the query from step 1 but take only labels of level 2 into account I get the result that the two products are sharing 100% of their process sequence.

I can calculate the LCS-result during postprocessing but I was wondering if neo4j or apoc can support on this.

best regards and thanks