Python图算法实例分析

#encoding=utf-8import networkx,heapq,sysfrom matplotlib import pyplotfrom collections import defaultdict,OrderedDictfrom 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  10def 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()