3 Approaches to the Max Clique problem. Also provides a graph generator
- Bruteforce
- Vertex Cover (G')
- Original, statistic approach
To compile each program: type "make" + "program name" in the command line. The main program of interest is Original.exe, compiled with make original
. The relevant source code is OriginalMaxClique.cpp
- Original: my original approach to solving Max Clique. use
make
to compile with optimizations, ormake original
for regular compilation ./Original.exe <graph file> <node count>
- Generator: can be used to create graphs with a given size and density. Compile with
make generator
./Generator <graph file> <node count> <density%>
- Verifier: Used to verify a solution to a graph file. Compiled with
make verifier
./Verifier.exe <graph file> <Solution> <count>
- Density: finds the density and other statistics about the graph
make density
./Density.exe <graph file> <node count>
- Bruteforce: bruteforce the max clique out of a graph. Works in reasonable time for up to ~30 nodes. Compile with
make bruteforce
./BruteForceMaxClique.exe <graph file> <node count>
- Heuristic: Vertex Cover to Max Clique. Compile with
make heuristic
./HeuristicMaxClique.exe <graph file> <node count>
- To clean files, run
make clean
When I started this project, the first thing I noticed was that we were only working with binary data. I initially came up with the idea of using a logical AND between rows to quickly find which nodes they have in common. This evolved into finding the similarity between 2 rows A and B. I could pick the row with the most nodes (A) and find its most similar match (B), then AND them to C and run the process iteratively with A=C --> B=similar(C ). However, I tweaked the similarity function to only rank positive matches, which produced much better results. The basic steps in the final algorithm:
- Generate a positive similarity matrix
- Find 2 most similar rows (regardless of their edge counts)
- Then, iteratively:
- C = A AND B
- B = row in Graph most similar to C
- C AND B
- Until we run out of nodes.
- I used O3 to run compiler optimizations which greatly improved my running times. Some of these statistics are found in NOTES.txt
- A more exhaustive search (longer runtime) can be toggled by replacing "FindPosSimilarity" with "FindAbsSimilarity" in lines 221 and 271
- 6 cpp files for each program
- Makefile
- Notes
- Readme
- Solutions folder