Python图算法实例分析

Python  /  管理员 发布于 7年前   190

本文实例讲述了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] = 0continue          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()

更多关于Python相关内容可查看本站专题：《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:

• python实现dict版图遍历示例
• Python数据结构与算法之图结构（Graph）实例分析
• python数据结构之图的实现方法
• python数据结构之图深度优先和广度优先实例详解
• Python基于回溯法子集树模板解决取物搭配问题实例
• Python基于回溯法子集树模板解决数字组合问题实例
• Python基于回溯法子集树模板解决0-1背包问题实例
• Python使用回溯法子集树模板解决迷宫问题示例
• Python基于回溯法子集树模板实现8皇后问题
• python回溯法实现数组全排列输出实例分析
• Python基于回溯法子集树模板实现图的遍历功能示例