I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free).
These four different DAGs (directed from left to right)...
a-b-c a-d-c a-c c-a
/---\ a--b--c-a \-d-/
This is not a real DAWG (directed acyclic word graph): I don't want to store information like "is 'adc' included?". My structure could only answer to this question: "it would be possible that 'adc' was one of the words?".
Is there an algorithm for this purpose?
Update (12/15/14) - Levenshtein distance
I tried something different: I used Levenshtein distance to find the minimum number of edits required in order to transform a string into another (node=character and chain=sequence of nodes/characters=word). My algorithm ignores deletion, and insert characters instead of replacing them. Here's the interesting part (Python code):
current = words for word in words[1:]: edit = editops(current, word) customEdit = [('insert', s, d) for op, s, d in edit if op != 'delete'] current = apply_edit(customEdit, current, word)
Sometimes there are unneeded characters, so I remove them at the end of the process. If I change the words order I get different results, so I run my code many times shuffling words in order to find a shorter string (shuffling seems to provide better result with fewer iterations than permutations, even if words are sorted by length).
If every character is a node, and every word is a DAG, I can easily get a good approximation of the DAG I'm looking for.
The main problem with this approach is that I don't know how the best result will look like so I don't know when to stop (I can't check every result of my permutation: it will take too much time!).
ldoarmilpesouimtr (17) iapmdsoeluiortem (16) diolposarmieutm (15) ^C Original size: 22 Compressed: 15 diolposarmieutm (lorem) diolposarmieutm (ipsum) diolposarmieutm (dolor) diolposarmieutm (sit) diolposarmieutm (amet)
Is it a good way to solve this problem? What it could be improved? Do you know if it's possible to know the minimum number of nodes/characters needed in order to stop the algorithm when I get the optimum?