TL;DR I need to find all possible ways to traverse an undirected cyclic, possibly disconnected graph to find all 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)
temp_set.add(n);
// Find all compatible nodes by finding intersection of the adjecency list of the nodes
// already in the set
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
candidateSolution.add(temp_set);
temp_set.clear();
}
// Once we've visited all the nodes, we have a candidate solution where two sets with the highest score are the possible answer
Now this works for a single possible solution, but fails to explore different traversal paths. Basically it builds a tree where each branch represents a set and where all graph nodes are included. I need to find all possible trees which can be built in order to find the one with the highest score.
I think I understand what I need to do next. Starting with the last solution, traverse back to the point where an alternative path could've been taken and build a new solution from there. Then keep doing it until I return to the first node and there are no more nodes to visit. However I can't wrap my head around implementation. Any help appreciated.
