Algorithm for finding "good" neighbors - coloring a graph?

Question

I have a group of people, and for each of them a list of friends and a list of opponents. I want to align them (without a circle, like on a table) so that there is no choice of opponents, but only friends next to each other.

Input example: https://gist.github.com/solars/53a132e34688cc5f396c

It seems to me that I need to use the coloring of the graph to solve this problem, but I'm not sure how to do it - I think I need to leave a list of friends (or opponents) in order to simplify and display the graph.

Does anyone know how to solve such problems and can tell me if I'm on the right track?

Code samples or online examples will also be pleasant, I am not against a programming language, I usually use Ruby, Java, Python, Javascript

Many thanks for your help!

Answer 1

The comments already mentioned that this problem is equivalent to the traveling salesman problem. I would like to dwell on this:

Each person is equivalent to a vertex, and the ribs are between the vertices, which represent people who can sit with each other. Now finding the possible seat arrangement is equivalent to finding the Hamiltonian trajectory on the graph.

So this problem is NPC. The most naive solution would be to try all possible permutations leading to O(n!) Time. There are many well-known approaches that work better than O(n!) And are freely available on the Internet. I would like to mention Held-Karp , which works in O(n^2*2^n) and is pretty directly transcoded to the code, here in python:

 #graph[i] contains all possible neighbors of the i-th person def held_karp(graph): n = len(graph)#number of persons #remember the set of already seated persons (as bitmask) and the last person in the line #thus a configuration consists of the set of seated persons and the last person in the line #start with every possible person: possible=set([(2**i, i) for i in xrange(n)]) #remember the predecessor configuration for every possible configuration: preds=dict([((2**i, i), (0,-1)) for i in xrange(n)]) #there are maximal n persons in the line - every iterations adds a person for _ in xrange(n-1): next_possible=set() #iterate through all possible configurations for seated, last in possible: for neighbor in graph[last]: bit_mask=2**neighbor if (bit_mask&seated)==0: #this possible neighbor is not yet seated! next_config=(seated|bit_mask, neighbor)#add neighbor to the bit mask of seated next_possible.add(next_config) preds[next_config]=(seated, last) possible=next_possible #now reconstruct the line if not possible: return []#it is not possible for all to be seated line=[] config=possible.pop() #any configuration in possible has n person seated and is good enough! while config[1]!=-1: line.insert(0, config[1]) config=preds[config]#go a step back return line 

Disclaimer: This code is not properly verified, but I hope you can get the gist of it.