Conflict Resolution Grouping Algorithm

Question

Algorithm question from Google:

The teacher wants to divide his problem students into two groups. He has a list of names (in pairs) that represents students who cannot be placed in the same group. Our task is to check whether it is possible to separate all students without collisions.

For example, if the list:

Jack Jim (cannot be in the same group) Jim Rose (...) Rose Jack (...) 

Then they cannot be separated without a collision.

My idea is to use the idea of ​​a graph and use the associated array or map to implement it. However, I think that if there are many unrelated branches of the graph, it will be very difficult. Anyone can help?

Answer 1

You want to check if the chart is bi-directional . Wikipedia contains information on how to do this.

Here is a related SO question and a Java implementation from Princeton.

Answer 2

This is similar to the graph coloring problem. Start by announcing that Jack is in the black group. This means that Jim should be in the "red" group. This means that the "Rose" must be in the "black group". Now we get a collision: because the rose is “black”, Jack must be “red”, but we have already assigned him a black color.

---

Edit: Pseudocode to implement (I have not compiled it, and I know that it has a memory leak)

 enum Group { UNKNOWN, RED, BLACK }; struct Person { string name; Group group; set<Person*> exclusionList; } class Class { public: void addExclusion(const string& inPersonA, const string& inPersonB) { bool first = (mMembers.empty()); Person* personA = findPerson(inPersonA); Person* personB = findPerson(inPersonB); personA->exclusinList.insert(personB); personB->exclusionList.insert(personA); if (first) { // special case, assign initial colors personA->color = BLACK; personB->color = RED; } else { switch (personA->color) { case UNKNOWN: switch(personB->color) { case UNKNOWN: break; // we can't do anything, nothing is known case BLACK: setColor(personA, RED); break; case RED: setColor(personA, BLACK); break; } break; case RED: switch (personB->color) { case UNKNOWN: setColor(personB, BLACK); break; case RED: throw "EXCLUSION FAILURE"; case BLACK: break; } case BLACK: switch (personB->color) { case UNKNOWN: setColor(personB, BLACK); break; case RED: break; case BLACK: throw "EXCLUSION FAILURE"; } } } } private: Person* findPerson(const string& inString) { Person* rval = mMembers[inString]; if (rval == null) { rval = new Person(inString, UNKNOWN); mMembers[inString] = rval; } return rval; } void setColor(Person* inPerson, Group inColor) { if (inPerson->color == inColor) return; // no op if (inPerson->color != UNKNOWN && inPerson->color != inColor) throw "EXCLUSION FAILURE"; // now we know inPerson was UNKNOWN inPerson->color = inColor; for (auto iter = inPerson->exclusionList.begin(); iter != inPerson->exclusionList.end(); ++iter) { setColor(*iter, (inColor == RED) ? BLACK : RED); } unordered_map<string, Person*> mMembers; }; 

Answer 3

 #algorithm.coffee #teacher wants to separate his/her problem prisoners into two groups by keeping #separated certain individuals. we have a list of kids and need to decide how to #separate them according to rules provided. only two groups allowed apparently. if #more are required we are in collision situation. reset = '\x1B[0m' red = '\x1B[0;31m' green = '\x1B[0;32m' #we list all the kids, and such that the values are arrays holding all problems associated with that # key=kid contras = "abe": [] "billy": [] "bella": [] "charles": [] "dafner": [] "echo": [] "ferris": [] "gomer": [] "gina": [] "heloise": [] #we have empty groups group1 = [] group2 = [] # defining problem relationships problems = [ ["abe", "heloise"] ["bella", "dafner"] ["gomer", "echo"] #["abe", "bella"] ["heloise", "dafner"] ["echo", "ferris"] ["abe", "dafner"] ] # with the problems array we can populate the contras object for item in problems contras[item[0]].push item[1] contras[item[1]].push item[0] # with the populated contras object we can determine conflicts for key, value of contras for item in value for item2 in value for item3 in contras[item] if item2 == item3 and item3 != item console.log red + "There is a collision implicit in problem pair " + reset + key + red + " and " + reset + item + red + " because both " + reset + key + red + " and " + reset + item + red + " are problematic with " + reset + item3 + red + " who is also known as " + reset + item2 + red + ".\n" # if there are no unresolvable conflicts then this routine below # will work, otherwise you'll see a bunch of # red flags thrown by the routine above. for item in problems if group1.length == 0 group1.push item[0] group2.push item[1] else duplicate = false for item2 in group1 if item2 in contras[item[0]] then duplicate = true if duplicate == true group1.push item[1] unless item[1] in group1 group2.push item[0] unless item[0] in group2 else group1.push item[0] unless item[0] in group1 group2.push item[1] unless item[1] in group2 ### some tests # checking if group1 contains problems for item in group1 for item2 in problems for item3 in item2 if item == item3 for item4 in item2 if item4 != item for item5 in group1 if item4 == item5 duplicate = false for item6 in collisions if item2 == item6 then duplicate = true if duplicate == false collisions.push item2 # checking if group2 contains problems for item in group2 for item2 in problems for item3 in item2 if item == item3 for item4 in item2 if item4 != item for item5 in group2 if item4 == item5 duplicate = false for item6 in collisions if item2 == item6 then duplicate = true if duplicate == false collisions.push item2 ### console.log green + "whole kids group is " + reset + kids console.log green + "group1 is " +reset + group1 console.log green + "group2 is " + reset + group2 # console.log red + "collisions are " + reset + collisions 

Answer 4

All you need to do is check if your graph is bipartite (i.e. if the vertices of your graph can be assigned one of two colors so that no edge connects the vertices of the same color). If you enroll students in a class with integers:

 1. Jack 2. Jim 3. Rose 

you can easily solve this problem using the Boost Graph library in C ++:

 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/bipartite.hpp> using namespace boost; int main (int argc, char **argv) { typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t; typedef std::pair <int, int> E; E edges[] = { E (1, 2), E (2, 3), E (3, 1)}; vector_graph_t students (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 3); if ( is_bipartite(students) ) std::cout << "Bipartite graph" << std::endl; else std::cout << "Non bipartite graph" << std::endl; return 0; }