How can you make a recursive object clustering function?

Question

JavaScript

Hello everyone, I have such an object with tags where the key is a tag, and the value is a tag object (where the key is a tag, and the value is the number of intersections of these two tags)




How can I recursively search for a chain of all incompatible tags ( so that in a group each tags are not compatible in any way) here is an example of group 1:



I would be grateful for pseudocode or at least an algorithm.

Answer 1

You have a graph where the vertices are tags and there are edges between them. If you take an edge where two tags are incompatible, then you have the task of finding clicks .
First, there is an ambiguity here. It may be that tags A, B, C are pairwise incompatible, but at the same time tags A, D, E are pairwise incompatible - where should tag A be assigned, to which group?
Finding the largest group is a difficult task; there are no simple algorithms. Full enumeration and all that stuff works here.
If you just need to find a large enough group, then you can do it greedily. There is a current "chain of incompatible tags", there are some already discarded tags, there are some remaining ones, so take any of the remaining ones and, if it fits, then add it to the incompatible tags. If not, discard.
There is alsoBron-Kerbosh algorithm . It iterates over all max cliques.