#encoding=utf-8
import networkx,heapq,sys
from matplotlib import pyplot
from collections import defaultdict,OrderedDict
from numpy import array
# Data in graphdata.txt:
# a b  4
# a h  8
# b c  8
# b h  11
# h i  7
# h g  1
# g i  6
# g f  2
# c f  4
# c i  2
# c d  7
# d f  14
# d e  9
# f e  10
def Edge(): return defaultdict(Edge)
class Graph:
  def __init__(self):
    self.Link = Edge()
    self.FileName = ''
    self.Separator = ''
  def MakeLink(self,filename,separator):
    self.FileName = filename
    self.Separator = separator
    graphfile = open(filename,'r')
    for line in graphfile:
      items = line.split(separator)
      self.Link[items[0]][items[1]] = int(items[2])
      self.Link[items[1]][items[0]] = int(items[2])
    graphfile.close()
  def LocalClusteringCoefficient(self,node):
    neighbors = self.Link[node]
    if len(neighbors) <= 1: return 0
    links = 0
    for j in neighbors:
      for k in neighbors:
        if j in self.Link[k]:
          links += 0.5
    return 2.0*links/(len(neighbors)*(len(neighbors)-1))
  def AverageClusteringCoefficient(self):
    total = 0.0
    for node in self.Link.keys():
      total += self.LocalClusteringCoefficient(node)
    return total/len(self.Link.keys())
  def DeepFirstSearch(self,start):
    visitedNodes = []
    todoList = [start]
    while todoList:
      visit = todoList.pop(0)
      if visit not in visitedNodes:
        visitedNodes.append(visit)
        todoList = self.Link[visit].keys() + todoList
    return visitedNodes
  def BreadthFirstSearch(self,start):
    visitedNodes = []
    todoList = [start]
    while todoList:
      visit = todoList.pop(0)
      if visit not in visitedNodes:
        visitedNodes.append(visit)
        todoList = todoList + self.Link[visit].keys()
    return visitedNodes
  def ListAllComponent(self):
    allComponent = []
    visited = {}
    for node in self.Link.iterkeys():
      if node not in visited:
        oneComponent = self.MakeComponent(node,visited)
        allComponent.append(oneComponent)
    return allComponent
  def CheckConnection(self,node1,node2):
    return True if node2 in self.MakeComponent(node1,{}) else False
  def MakeComponent(self,node,visited):
    visited[node] = True
    component = [node]
    for neighbor in self.Link[node]:
      if neighbor not in visited:
        component += self.MakeComponent(neighbor,visited)
    return component
  def MinimumSpanningTree_Kruskal(self,start):
    graphEdges = [line.strip('\n').split(self.Separator) for line in open(self.FileName,'r')]
    nodeSet = {}
    for idx,node in enumerate(self.MakeComponent(start,{})):
      nodeSet[node] = idx
    edgeNumber = 0; totalEdgeNumber = len(nodeSet)-1
    for oneEdge in sorted(graphEdges,key=lambda x:int(x[2]),reverse=False):
      if edgeNumber == totalEdgeNumber: break
      nodeA,nodeB,cost = oneEdge
      if nodeA in nodeSet and nodeSet[nodeA] != nodeSet[nodeB]:
        nodeBSet = nodeSet[nodeB]
        for node in nodeSet.keys():
          if nodeSet[node] == nodeBSet:
            nodeSet[node] = nodeSet[nodeA]
        print nodeA,nodeB,cost
        edgeNumber += 1
  def MinimumSpanningTree_Prim(self,start):
    expandNode = set(self.MakeComponent(start,{}))
    distFromTreeSoFar = {}.fromkeys(expandNode,sys.maxint); distFromTreeSoFar[start] = 0
    linkToNode = {}.fromkeys(expandNode,'');linkToNode[start] = start
    while expandNode:
      # Find the closest dist node
      closestNode = ''; shortestdistance = sys.maxint;
      for node,dist in distFromTreeSoFar.iteritems():
        if node in expandNode and dist < shortestdistance:
          closestNode,shortestdistance = node,dist
      expandNode.remove(closestNode)
      print linkToNode[closestNode],closestNode,shortestdistance
      for neighbor in self.Link[closestNode].iterkeys():
        recomputedist = self.Link[closestNode][neighbor]
        if recomputedist < distFromTreeSoFar[neighbor]:
          distFromTreeSoFar[neighbor] = recomputedist
          linkToNode[neighbor] = closestNode
  def ShortestPathOne2One(self,start,end):
    pathFromStart = {}
    pathFromStart[start] = [start]
    todoList = [start]
    while todoList:
      current = todoList.pop(0)
      for neighbor in self.Link[current]:
        if neighbor not in pathFromStart:
          pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
          if neighbor == end:
            return pathFromStart[end]
          todoList.append(neighbor)
    return []
  def Centrality(self,node):
    path2All = self.ShortestPathOne2All(node)
    # The average of the distances of all the reachable nodes
    return float(sum([len(path)-1 for path in path2All.itervalues()]))/len(path2All)
  def SingleSourceShortestPath_Dijkstra(self,start):
    expandNode = set(self.MakeComponent(start,{}))
    distFromSourceSoFar = {}.fromkeys(expandNode,sys.maxint); distFromSourceSoFar[start] = 0
    while expandNode:
      # Find the closest dist node
      closestNode = ''; shortestdistance = sys.maxint;
      for node,dist in distFromSourceSoFar.iteritems():
        if node in expandNode and dist < shortestdistance:
          closestNode,shortestdistance = node,dist
      expandNode.remove(closestNode)
      for neighbor in self.Link[closestNode].iterkeys():
        recomputedist = distFromSourceSoFar[closestNode] + self.Link[closestNode][neighbor]
        if recomputedist < distFromSourceSoFar[neighbor]:
          distFromSourceSoFar[neighbor] = recomputedist
    for node in distFromSourceSoFar:
      print start,node,distFromSourceSoFar[node]
  def AllpairsShortestPaths_MatrixMultiplication(self,start):
    nodeIdx = {}; idxNode = {}; 
    for idx,node in enumerate(self.MakeComponent(start,{})):
      nodeIdx[node] = idx; idxNode[idx] = node
    matrixSize = len(nodeIdx)
    MaxInt = 1000
    nodeMatrix = array([[MaxInt]*matrixSize]*matrixSize)
    for node in nodeIdx.iterkeys():
      nodeMatrix[nodeIdx[node]][nodeIdx[node]] = 0
    for line in open(self.FileName,'r'):
      nodeA,nodeB,cost = line.strip('\n').split(self.Separator)
      if nodeA in nodeIdx:
        nodeMatrix[nodeIdx[nodeA]][nodeIdx[nodeB]] = int(cost)
        nodeMatrix[nodeIdx[nodeB]][nodeIdx[nodeA]] = int(cost)
    result = array([[0]*matrixSize]*matrixSize)
    for i in xrange(matrixSize):
      for j in xrange(matrixSize):
        result[i][j] = nodeMatrix[i][j]
    for itertime in xrange(2,matrixSize):
      for i in xrange(matrixSize):
        for j in xrange(matrixSize):
          if i==j:
            result[i][j] = 0
            continue
          result[i][j] = MaxInt
          for k in xrange(matrixSize):
            result[i][j] = min(result[i][j],result[i][k]+nodeMatrix[k][j])
    for i in xrange(matrixSize):
      for j in xrange(matrixSize):
        if result[i][j] != MaxInt:
          print idxNode[i],idxNode[j],result[i][j]
  def ShortestPathOne2All(self,start):
    pathFromStart = {}
    pathFromStart[start] = [start]
    todoList = [start]
    while todoList:
      current = todoList.pop(0)
      for neighbor in self.Link[current]:
        if neighbor not in pathFromStart:
          pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
          todoList.append(neighbor)
    return pathFromStart
  def NDegreeNode(self,start,n):
    pathFromStart = {}
    pathFromStart[start] = [start]
    pathLenFromStart = {}
    pathLenFromStart[start] = 0
    todoList = [start]
    while todoList:
      current = todoList.pop(0)
      for neighbor in self.Link[current]:
        if neighbor not in pathFromStart:
          pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
          pathLenFromStart[neighbor] = pathLenFromStart[current] + 1
          if pathLenFromStart[neighbor] <= n+1:
            todoList.append(neighbor)
    for node in pathFromStart.keys():
      if len(pathFromStart[node]) != n+1:
        del pathFromStart[node]
    return pathFromStart
  def Draw(self):
    G = networkx.Graph()
    nodes = self.Link.keys()
    edges = [(node,neighbor) for node in nodes for neighbor in self.Link[node]]
    G.add_edges_from(edges)
    networkx.draw(G)
    pyplot.show()
if __name__=='__main__':
  separator = '\t'
  filename = 'C:\\Users\\Administrator\\Desktop\\graphdata.txt'
  resultfilename = 'C:\\Users\\Administrator\\Desktop\\result.txt'
  myGraph = Graph()
  myGraph.MakeLink(filename,separator)
  print 'LocalClusteringCoefficient',myGraph.LocalClusteringCoefficient('a')
  print 'AverageClusteringCoefficient',myGraph.AverageClusteringCoefficient()
  print 'DeepFirstSearch',myGraph.DeepFirstSearch('a')
  print 'BreadthFirstSearch',myGraph.BreadthFirstSearch('a')
  print 'ShortestPathOne2One',myGraph.ShortestPathOne2One('a','d')
  print 'ShortestPathOne2All',myGraph.ShortestPathOne2All('a')
  print 'NDegreeNode',myGraph.NDegreeNode('a',3).keys()
  print 'ListAllComponent',myGraph.ListAllComponent()
  print 'CheckConnection',myGraph.CheckConnection('a','f')
  print 'Centrality',myGraph.Centrality('c')
  myGraph.MinimumSpanningTree_Kruskal('a')
  myGraph.AllpairsShortestPaths_MatrixMultiplication('a')
  myGraph.MinimumSpanningTree_Prim('a')
  myGraph.SingleSourceShortestPath_Dijkstra('a')
  # myGraph.Draw()