# Finding all possible exclusive cliques in a graph

TL;DR I need to find all possible ways to traverse an undirected cyclic, possibly disconnected graph to find all exclusive sets of connected nodes which satisfy certain criteria.

There's a graph of nodes, where each node is assigned a value and edges represent compatible nodes.

Compatible nodes can be put together into a set, but only if each of the nodes is compatible with all of the others. For example given the following graph, represented as adjecency list:

0: 2, 3
1:
2: 0, 4, 6, 7
3: 0, 4, 6, 7
4: 2, 3, 5, 6
5: 4, 7
6: 2, 3, 4, 6
7: 2, 3, 5, 6


Nodes {4, 5} can form a set together as can nodes {3, 4, 6}, while node 1 can only form a single element set.

Now given that each node holds a value, find n sets with the highest combined value. For the example above if the nodes have following values:

0: 4
1: 6
2: 4
3: 5
4: 6
5: 3
6: 3
7: 5


The solution for n = 2 are sets {3, 4, 6} and {2, 7} with combined value of 23.

The approach I started is to use a modified version of DFS where the stack is only populated with the nodes which are compatible with all the nodes in the current set so far. If there are no such nodes, we create a new set and continue with the nodes which have not yet been visited.

Pseudocode:

// As long as we have any unvisited nodes
while(visited.contains(false))
{
// Take first unvisited node and push it onto a stack
stack.push(find_first(visited, false));

// Modified DFS
while (!stack.empty())
{
Node n = stack.pop();

// Add the node to the set (this will always be either first or compatible node)

// Find all compatible nodes by finding intersection of the adjecency list of the nodes
compatibleNodes = find_all_compatible_nodes(set);

// Add the first compatible, unvisited node we find to the stack
for(c : compatibleNodes)
{
if(!visited[c])
{
stack.push(c);
visited[c] = true;

break;
}
}

}

// Once we run out of compatible nodes for this set, we add it to candidate solution and start with a new one