"""this file is used to select test topologies from topology zoo dataset """
"""Input: file name contains with matrix representation of graphs (generated by gml2matrix)"""
"""Output: selected topology with matrix representation"""

import sys
import operator
import multiprocessing

def floyd( matrix ):
    "floyd algorithm implementation"
    length = len(matrix)
    next_hop = [ [ -1 for j in range(length) ] for i in range(length) ]
    for i in range(length):
        for j in range(length):
            if matrix[i][j] != 0:
                next_hop[i][j] = j

    it = [ row[:] for row in matrix ]
    max_length = 0xffffffff
    for i in range(length):
        for j in range(length):
            it[i][j] = it[i][j] if it[i][j] != 0 else max_length
    for k in range(length):
        for i in range(length):
            for j in range(length):
                if it[i][k] + it[k][j] < it[i][j]:
                    it[i][j] = it[i][k] + it[k][j]
                    next_hop[i][j] = next_hop[i][k]
    paths = {}
    for i in range(length):
        for j in range(length):
            if i == j:
                continue
            tmp = i
            path = []
            while tmp != j and tmp != -1:
                path.append(tmp)
                tmp = next_hop[tmp][j]
            if tmp == -1:
                path = []
            else:
                path.append(tmp)
            paths[(i,j)] = path
    return paths

def parse_matrix( filename ):
    matrices = {}
    info = [] # [ name, (nodes, edges) ]
    matrix = []
    with open(filename, "r") as f:
        for line in f:
            line = line.rstrip('\r\n ')
            if len(line) == 0:
                continue
            if len(info) == 0:
                info.append(line) # append name
            elif len(info) == 1:
                info.append( [ int(i) for i in line.split(' ') ] )
            elif len(info) == 2 and len(matrix) != info[1][0]:
                matrix.append( [ int(i) for i in line.split(' ' ) ] )
                if len(matrix) == info[1][0]:
                    matrices[info[0]] = matrix
                    info = []
                    matrix = []
            else:
                print 'error, cannot parse...'
                return None
    return matrices

def is_sub_list( left, right):
    if left[len(left)-1] != right[len(right)-1]:
        return False
    for i in range(len(right)):
        if right[i] == left[0]:
            sublist = True
            for j in range(len(left)):
                if i+j >= len(right) or right[i+j] != left[j]:
                    sublist = False
                    break
            if sublist:
                return True
    return False
def process( pair ):
    name, matrix = pair
    paths = floyd( matrix )
    lens = [ len(i) for i in paths.values() ]
    min_len = min(lens)
    avg_len = float(sum( lens ))/len(lens)
    max_len = max( lens )
    
    degs = [ 0 for i in range( len(matrix) ) ]
    for i in range( len( matrix) ):
        deg = 0
        for j in range( len( matrix) ):
            if matrix[j][i] == 1:
                deg += 1
        degs[i] = deg
    min_deg = min( degs )
    avg_deg = float(sum( degs ))/len(degs)
    max_deg = max(degs)
    
    long_paths = set(tuple(i) for i in paths.values() if len(i) != 0)
    while True:
        cpy = set(long_paths)
        removed = 0
        for left in long_paths:
            for right in long_paths:
                if left != right and is_sub_list(right, left):
                    if right in cpy:
                        cpy.remove(right)
                    removed += 1
        long_paths = cpy
        if removed == 0:
            break
                    
    path_num = len(long_paths)
    path_total_len = sum( [ len(i) for i in long_paths ] )
    result = (name, avg_len, min_len, max_len, avg_deg, min_deg, max_deg, path_num, path_total_len)
    print result
    return result
    
if __name__ == '__main__':
    outputfile = None
    if len(sys.argv) != 2 and len(sys.argv) != 3:
        print 'usage: ' + sys.argv[0] + ' filename'
        sys.exit(1)

    outputfile = 'output.dat' if len(sys.argv) != 3 else sys.argv[2]
    matrices = parse_matrix( sys.argv[1] )
    for name, matrix in matrices.items():
        if len(matrix) > 100:
            print 'topology %20s too large, having %4d nodes' % (name, len(matrix))
            del matrices[name]
    len_map = {}

    pool_size=multiprocessing.cpu_count()*8
    pool=multiprocessing.Pool(processes=pool_size)
    pool_outputs=pool.map(process,matrices.iteritems())
    pool.close()
    pool.join()
    
    with open(outputfile, 'w') as output:
        output.write('%50s %7s %7s %7s %7s %7s %7s %7s %8s %14s\n' % ('name', 'nodes', 'avg_len', 'min_len', 'max_len', 'avg_deg', 'min_deg', 'max_deg', 'path_num', 'path_total_len'))
        for name, avg_len, min_len, max_len, avg_deg, min_deg, max_deg, path_num, path_total_len in sorted(pool_outputs, key=operator.itemgetter(8)):
            output.write('%50s %7d %7.2f %7d %7d %7.2f %7d %7d %8d %14d\n' % (name, len(matrices[name]), avg_len, min_len, max_len, avg_deg, min_deg, max_deg, path_num, path_total_len))
            print '%50s %7d %7.2f %7d %7d %7.2f %7d %7d %8d %14d' % (name, len(matrices[name]), avg_len, min_len, max_len, avg_deg, min_deg, max_deg, path_num, path_total_len)
