# Merge directed acyclic graphs minimizing number of nodes

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
``````

...should become:

`````` /---\
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[0]
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!).

Here's my code (tested with Python 2; python-Levenshtein is needed). The output looks like this:

```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?

• When you say you want to merge them, this implies that you can string them together (e.g. a-b-c-a-b-c...). Is this correct? If so, this sounds like a regular expression to me (the theoretical type used to model FSAs, not the type included in software libraries).
– user22815
Dec 14, 2014 at 4:43
• @Snowman I can string them together, but this makes sense to me only at the end of the process (if I merge `a-b` and `c-d` as `c-d-a-b` it's ok, but when I add `a-f` I get `c-d-a-b-f` while the correct result would be `a-b-c-d-e-f`) Dec 14, 2014 at 8:48
• Do you care that it looks like i->e is valid in the output even though it's not in any of the words? If not, the output sounds like a string, not a DAG. Dec 15, 2014 at 21:58
• @raptortech97 It looks like they are the same problem to me: from a DAG I can build many strings, and from one of those strings, using words, I can build the corresponding DAG. This is why I tried to use Levenshtein (which works on strings) to generate the optimum DAG, but this is just an experiment which seems to work better than my previous node-based approach. I can reply to you with "No, I don't care", because even in this case I should be able to build the DAG. Dec 16, 2014 at 9:42
• I think you're looking for this: Optimal insertion in deterministic DAWGs: citeseerx.ist.psu.edu/viewdoc/… It details how to create an optimal dictionary-representing DAWG. It's not a particularly easy read. Jul 22, 2015 at 20:00