from pygraphlib import pygraph,algo
import pygraphlib
from Numeric import *
import random

INFINITY = 100000000

def apsp(graph):
    "All-pairs shortest path using n Dijkstra computations"
    n = graph.number_of_nodes()
    dist = zeros((n,n)) + INFINITY
    for x in graph.node_list():
        sssp = algo.dijkstra(graph, x)[0]
        for y in sssp.items():
            dist[(x,y[0])] = y[1]
    return dist
    


def brute_force(graph, weights):
    """Identify a Condorcet winner of a graph using the n^3 brute-force
    method. Doesn't yet support identifying top cycles."""
    dist = apsp(graph)
    topCycle = []
    for x in graph.node_list():
        defeatCount = 0
        for y in graph.node_list():
            if (x == y):
                continue
            # Check whether y defeats x
            xVotes = 0
            yVotes = 0
            for z in graph.node_list():
                if dist[z,x] < dist[z,y]:
                    xVotes = xVotes + weights[z]
                elif dist[z,y] < dist[z,x]:
                    yVotes = yVotes + weights[z]
            if (yVotes >= xVotes):
                print y, "defeats", x
                defeatCount = defeatCount + 1
            if defeatCount >= 2:
                print x, "overly defeated"
                break;
        else:
            if defeatCount == 0:
                print x, "defeatcount 0"
                return x
            elif defeatCount == 1:
                print x, "defeatcount 1"
                topCycle.append(x)
    return topCycle

def tournament(graph, weights):
    dist = apsp(graph)
    seeding = graph.node_list()
    while len(seeding) > 1:
        random.shuffle(seeding)
        nextSeeding = []
        if len(seeding) % 2 == 1:        # Odd case; last one moves on
            nextSeeding.append(seeding[len(seeding) - 1])
        for i in range(len(seeding)/2):
            x = seeding[2*i]
            y = seeding[2*i + 1]
            # Check whether y defeats x
            xVotes = 0
            yVotes = 0
            for z in graph.node_list():
                if dist[z,x] < dist[z,y]:
                    xVotes = xVotes + weights[z]
                elif dist[z,y] < dist[z,x]:
                    yVotes = yVotes + weights[z]
            if (yVotes > xVotes):
                print y, "defeats", x
                nextSeeding.append(y)
            else:
                print x, "defeats", y
                nextSeeding.append(x)
        seeding = nextSeeding
    return seeding[0]

    





# Test graphs

# winner is 4
example1 = pygraph.UGraph()
example1.add_edge(1,2)
example1.add_edge(1,3)
example1.add_edge(2,3)
example1.add_edge(3,4)
example1.add_edge(4,5)
example1.add_edge(5,0)
weights1 = [0,10,4,0,8,8]

# top cycle is 0,2,4
example2 = pygraph.UGraph()
example2.add_edge(0,1)
example2.add_edge(1,2)
example2.add_edge(2,3)
example2.add_edge(3,4)
example2.add_edge(4,0)
weights2 = [10,4,7,8,2]