최소로 색칠하기, Coloring in Discrete Optimization

https://class.coursera.org/optimization-002 에서 나온 문제입니다.

 Node 들이 있고, 각 Node는 Edge에 의해 다른 Node와 연결되어 있습니다.
 Node에 색을 칠하는 데, 제한조건은 Edge로 연결되어 있는 바로 옆 Node와 색이 같아서는 안 됩니다.
 목표는 최소한의 색으로 Node들을 칠하는 것입니다.


 제 알고리즘은

 - Node 중 Edge의 수가 가장 작은 Node부터 색을 칠합니다.

- 색을 칠할 때에는 연결되어 있는 Node에 칠해져있는 색을 알아봅니다.

- 색의 가지수는 많아봐야 Node 숫자보다는 작으므로, 0부터 최대치(Node의 갯수)까지 넣어보는 데, 연결되어 있는 Node에 그 숫자가 없으면 일단 그 Node에 가장 낮은 수를 넣습니다.

결과는 썩 좋은 편은 아닙니다. ㅋㅋㅋ 계속 개선해나가야죠.

def ConnectedNodes( SelectedNode, edges ):
    # 연결되어 있는 노드를 담을 리스트
    ConnectedNodes = []
    
    # edge를 죽 훑어본다.
    for edge in edges:
        if SelectedNode in edge:
            temp = list(edge)
            temp.remove(SelectedNode)
            tempint = int(temp[0])
            ConnectedNodes.append(tempint)
            
    return ConnectedNodes

def ColoringNode( index, edges, solution, node_count, Color ):
    #연결되어있는 node의 리스트 생성
    CNodes = ConnectedNodes( index, edges )
    
    #연결되어 있는 node의 색깔을 받는다.
    CNColors = []
    for cn in CNodes:
        CNColors.append(solution[cn])
    
    #0부터 node의 숫자만큼의 색깔 중에서 가장 낮은 숫자를 칠한다. 
    for i in range(0, node_count):
        if not i in CNColors:
            solution[index] = i
            return
    
    solution[index] = Color
    return 

def solve_it(input_data):
    # Modify this code to run your optimization algorithm

    # parse the input
    lines = input_data.split('\n')

    first_line = lines[0].split()
    node_count = int(first_line[0])
    edge_count = int(first_line[1])

    edges = []
    for i in range(1, edge_count + 1):
        line = lines[i]
        parts = line.split()
        edges.append((int(parts[0]), int(parts[1])))
        
    solution = [-1]*node_count
    
    # 각 node별로 edge들의 갯수를 구한다.
    NodesHaveEdgenum = [0]*node_count
    
    for edge in edges:
        NodesHaveEdgenum[edge[0]] += 1
        NodesHaveEdgenum[edge[1]] += 1
        
    # 각 node별로 edge의 수가 적은 순으로 사전 정렬
    WeightedIndex = []
 
       
    for i in range(0, node_count):
        WeightedIndex.append( [i,NodesHaveEdgenum[i]] )
        
    WeightedIndex = sorted( WeightedIndex, key=lambda WeightedIndex:WeightedIndex[1], reverse=False )
    #사전 정렬 끝.
    
    #계산이 끝난 후 solution에서 각각 1을 빼야됨
    
    #많아봐야 노드 갯수 이상의 색을 칠할 필요는 없으므로 loop의 한계는 node수로 한계지어놓는다.
    for i, index in enumerate(WeightedIndex):
        #node의 index를 주면 해당 node에 가장 작은 색을 칠한다.
        #print "index[0]: ", index[0], " ,edges: ", edges, " ,solution: ", solution, " ,i: ", i
        ColoringNode( index[0], edges, solution, node_count, i )
        
    # prepare the solution in the specified output format
    output_data = str(node_count) + ' ' + str(0) + '\n'
    output_data += ' '.join(map(str, solution))

    return output_data


import sys

if __name__ == '__main__':
    if len(sys.argv) > 1:
        file_location = sys.argv[1].strip()
        input_data_file = open(file_location, 'r')
        input_data = ''.join(input_data_file.readlines())
        input_data_file.close()
        print solve_it(input_data)
    else:
        print 'This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/gc_4_1)'