This project is an alternative I've developed over reading a few articles, based on finding cliques applying multiple selection techniques such as greedy and randomized
By the nature of my implementation, GRASP is used for finding A clique (not the clique with maximum size), by applying the steps below;
- Select a random clique
- List its neighbors by taking a cardinality parameter into consideration*
- From selected nodes obtain the top x% (x verifies depending on the size of the graph)
- Obtain the sublist constructed by the x% of nodes and pick a random node between them.
- Verify if the selected node has a connection with each node in possible solution set.If it is, add to the solution set, if not pick another one.
- Proceed this until no node can be found with the proper qualifications. Later on terminate the program.
*: Since my project involved working with graphs that only contains minimal information (Node #1, Node #2) I've come up with using the weight between two nodes as my cardinality parameter.
The file testGraph.txt can be an example for what kind of input the program requires.