Summarizing repeating gaph

61 views Asked by At

is there a way to summarize repetitive directed graph structures?

for example if we have a graph like

a->b->c1->d1->c2->d2->c3->d3 
      ^       ^       ^
      |       |       |
      e1      e2      e3

where c1, c2, c3, and d1, d2, d3, and e1,e2,e3 have similar properties or for example are of the same class respectively.
Is there a way to compress long graph like the above into a more general representation through algorithms that find repeating portions in trees and graphs?

the compressed version would look like




a -> b -> c_n -> d_n
          ^^     | 
          ||_____|
          |
          e_n

1

There are 1 answers

0
John On BEST ANSWER

Not sure if i got you right, you could do the following if this helps you:

Define root of tree(s) as common class(es) representing those properties. In this example, let your roots be: a, b, c, d and e.

Now take all elements that belong to given class, such as c1, c2 and c3. Organize them into tree with root c.

Connect each element directly to root, this will give you best search result if you need access to single element of a class.

Repeat grouping for each class and every element.

Once done, you should have trees with classes as roots. So, the only thing left is to connect these trees, where you should ideally connect tree which has less elements to tree that has more, e.g. making B subtree of C for example.

You want to connect smaller tree to larger to increase minimally required search complexity by affecting least number of elements, where search over larger tree will have same complexity as before connection.