Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
More sound similar class detector #7
Right now we pick one class and then find all classes that are similar to it. But depending on which class you start out with, you can end up with different sets. So we might want to find sets where all classes are pairwise similar. The complexity of that is most likely larger, definitely when implemented naively.
This is a highly nontrivial problem - it's about finding cliques in graphs. Our new class combiner builds cliques eagerly, which means the classes we combine are always pairwise similar, i.e. it's an improvement over the old algorithm. Depending on the order of the classes we might still find different cliques, however. The ideal would be to start with the largest clique, but finding that takes exponential time, so no.