Algorithm to find "good" neighbours - graph coloring?

Question

I have a group of people and for each of them a list of friends, and a list of foes. I want to line them up (no circle as on a table) so that preferrable no enemies but only friends are next to each other.

Example with the Input: https://gist.github.com/solars/53a132e34688cc5f396c

I think I need to use graph coloring to solve this, but I'm not sure how - I think I have to leave out the friends (or foes) list to make it easier and map to a graph.

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

Code samples or online examples would also be nice, I don't mind the programming language, I usually use Ruby, Java, Python, Javascript

Thanks a lot for your help!

Answer 1

It is already mentioned in the comments, that this problem is equivalent to travelling salesman problem. I would like to elaborate on that:

Every person is equivalent to a vertex and the edges are between vertices which represents persons who can seat to each other. Now, finding a possible seating arrangement is equivalent to finding a Hamiltonian path in the graph.

So this problem is NPC. The most naive solution would be to try all possible permutations resulting in a O(n!) running time. There are a lot of well known approaches which perform better than O(n!) and are freely available on the web. I would like to mention Held-Karp, which runs in O(n^2*2^n)and is pretty straight forward to 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 tested, but I hope you can get the gist of it.