def SolveTSP():
    global graph
    In = graph.getIn()
    Out = graph.getOut()
    print("In: ", In)
    print("Out: ", Out)
    minCost = 9999999
    minCostCycle = []
    list = FindAllHamiltonianCycles(Out, In)
    for cycle in list:
        cost = 0
        minCycle = []
        for index in range (0, len(cycle) - 1):
            cost += graph.getCostValue(cycle[index], cycle[index + 1])
            minCycle.append(cycle[index])
        if cost < minCost:
            minCost = cost
            minCostCycle = minCycle

------------------------------------------------

'''
Created on Mar 23, 2015

@author: razvan
'''

class Graph:
    def __init__(self, nrVertices):
        self.__In = {}
        self.__Out = {}
        self.__edges = {}
        self.__nrVertices = nrVertices
        for x in range(nrVertices):
            self.__Out[x] = []
            self.__In[x]  = []

    def getIn(self):
        return self.__In

    def getOut(self):
        return self.__Out

    def getNrOfVertices(self):
        return self.__nrVertices;

    def getVertices(self):
        return self.__Out.keys()

    def addEdge(self, start, end, cost):
        edge = (start, end)
        if end not in self.__Out[start]:
            self.__Out[start].append(end)
        if start not in self.__In[end]:
            self.__In[end].append(start)
        self.__edges[edge] = int(cost)

    def isEdge(self, start, end):
        if end in self.__Out[start]:
            return True
        return False

    def outbound(self, vertex):
        return self.__Out[vertex]

    def inbound(self, vertex):
        return self.__In[vertex]

    def getEdges(self):
        return self.__edges.keys()

    def getCostValue(self,start,end):
        '''key == tuple'''
        key = (start, end)
        if key in self.__edges.keys():
            return (self.__edges[key])
        else:
            print("There is no such edge!")

    def setCostValue(self, start, end, val):
        key = (start,end)
        self.__edges[key] = val

    def parseNout(self, vertex):
        return self.__Out[vertex]

    def parseNin(self, vertex):
        return self.__In[vertex]

    def vertexDegree(self, vertex):
        return [len(self.__In[vertex]), len(self.__Out[vertex])]