当前位置：Gxlcms > Python > Python图算法

Python图算法

时间：2021-07-01 10:21:17 帮助过：173人阅读

这篇文章主要介绍了Python图算法,结合实例形式详细分析了Python数据结构与算法中的图算法实现技巧,需要的朋友可以参考下

本文实例讲述了Python图算法。分享给大家供大家参考，具体如下：

  1. #encoding=utf-8
  2. import networkx,heapq,sys
  3. from matplotlib import pyplot
  4. from collections import defaultdict,OrderedDict
  5. from numpy import array
  6. # Data in graphdata.txt:
  7. # a b  4
  8. # a h  8
  9. # b c  8
  10. # b h  11
  11. # h i  7
  12. # h g  1
  13. # g i  6
  14. # g f  2
  15. # c f  4
  16. # c i  2
  17. # c d  7
  18. # d f  14
  19. # d e  9
  20. # f e  10
  21. def Edge(): return defaultdict(Edge)
  22. class Graph:
  23.   def __init__(self):
  24.     self.Link = Edge()
  25.     self.FileName = ''
  26.     self.Separator = ''
  27.   def MakeLink(self,filename,separator):
  28.     self.FileName = filename
  29.     self.Separator = separator
  30.     graphfile = open(filename,'r')
  31.     for line in graphfile:
  32.       items = line.split(separator)
  33.       self.Link[items[0]][items[1]] = int(items[2])
  34.       self.Link[items[1]][items[0]] = int(items[2])
  35.     graphfile.close()
  36.   def LocalClusteringCoefficient(self,node):
  37.     neighbors = self.Link[node]
  38.     if len(neighbors) <= 1: return 0
  39.     links = 0
  40.     for j in neighbors:
  41.       for k in neighbors:
  42.         if j in self.Link[k]:
  43.           links += 0.5
  44.     return 2.0*links/(len(neighbors)*(len(neighbors)-1))
  45.   def AverageClusteringCoefficient(self):
  46.     total = 0.0
  47.     for node in self.Link.keys():
  48.       total += self.LocalClusteringCoefficient(node)
  49.     return total/len(self.Link.keys())
  50.   def DeepFirstSearch(self,start):
  51.     visitedNodes = []
  52.     todoList = [start]
  53.     while todoList:
  54.       visit = todoList.pop(0)
  55.       if visit not in visitedNodes:
  56.         visitedNodes.append(visit)
  57.         todoList = self.Link[visit].keys() + todoList
  58.     return visitedNodes
  59.   def BreadthFirstSearch(self,start):
  60.     visitedNodes = []
  61.     todoList = [start]
  62.     while todoList:
  63.       visit = todoList.pop(0)
  64.       if visit not in visitedNodes:
  65.         visitedNodes.append(visit)
  66.         todoList = todoList + self.Link[visit].keys()
  67.     return visitedNodes
  68.   def ListAllComponent(self):
  69.     allComponent = []
  70.     visited = {}
  71.     for node in self.Link.iterkeys():
  72.       if node not in visited:
  73.         oneComponent = self.MakeComponent(node,visited)
  74.         allComponent.append(oneComponent)
  75.     return allComponent
  76.   def CheckConnection(self,node1,node2):
  77.     return True if node2 in self.MakeComponent(node1,{}) else False
  78.   def MakeComponent(self,node,visited):
  79.     visited[node] = True
  80.     component = [node]
  81.     for neighbor in self.Link[node]:
  82.       if neighbor not in visited:
  83.         component += self.MakeComponent(neighbor,visited)
  84.     return component
  85.   def MinimumSpanningTree_Kruskal(self,start):
  86.     graphEdges = [line.strip('\n').split(self.Separator) for line in open(self.FileName,'r')]
  87.     nodeSet = {}
  88.     for idx,node in enumerate(self.MakeComponent(start,{})):
  89.       nodeSet[node] = idx
  90.     edgeNumber = 0; totalEdgeNumber = len(nodeSet)-1
  91.     for oneEdge in sorted(graphEdges,key=lambda x:int(x[2]),reverse=False):
  92.       if edgeNumber == totalEdgeNumber: break
  93.       nodeA,nodeB,cost = oneEdge
  94.       if nodeA in nodeSet and nodeSet[nodeA] != nodeSet[nodeB]:
  95.         nodeBSet = nodeSet[nodeB]
  96.         for node in nodeSet.keys():
  97.           if nodeSet[node] == nodeBSet:
  98.             nodeSet[node] = nodeSet[nodeA]
  99.         print nodeA,nodeB,cost
  100.         edgeNumber += 1
  101.   def MinimumSpanningTree_Prim(self,start):
  102.     expandNode = set(self.MakeComponent(start,{}))
  103.     distFromTreeSoFar = {}.fromkeys(expandNode,sys.maxint); distFromTreeSoFar[start] = 0
  104.     linkToNode = {}.fromkeys(expandNode,'');linkToNode[start] = start
  105.     while expandNode:
  106.       # Find the closest dist node
  107.       closestNode = ''; shortestdistance = sys.maxint;
  108.       for node,dist in distFromTreeSoFar.iteritems():
  109.         if node in expandNode and dist < shortestdistance:
  110.           closestNode,shortestdistance = node,dist
  111.       expandNode.remove(closestNode)
  112.       print linkToNode[closestNode],closestNode,shortestdistance
  113.       for neighbor in self.Link[closestNode].iterkeys():
  114.         recomputedist = self.Link[closestNode][neighbor]
  115.         if recomputedist < distFromTreeSoFar[neighbor]:
  116.           distFromTreeSoFar[neighbor] = recomputedist
  117.           linkToNode[neighbor] = closestNode
  118.   def ShortestPathOne2One(self,start,end):
  119.     pathFromStart = {}
  120.     pathFromStart[start] = [start]
  121.     todoList = [start]
  122.     while todoList:
  123.       current = todoList.pop(0)
  124.       for neighbor in self.Link[current]:
  125.         if neighbor not in pathFromStart:
  126.           pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
  127.           if neighbor == end:
  128.             return pathFromStart[end]
  129.           todoList.append(neighbor)
  130.     return []
  131.   def Centrality(self,node):
  132.     path2All = self.ShortestPathOne2All(node)
  133.     # The average of the distances of all the reachable nodes
  134.     return float(sum([len(path)-1 for path in path2All.itervalues()]))/len(path2All)
  135.   def SingleSourceShortestPath_Dijkstra(self,start):
  136.     expandNode = set(self.MakeComponent(start,{}))
  137.     distFromSourceSoFar = {}.fromkeys(expandNode,sys.maxint); distFromSourceSoFar[start] = 0
  138.     while expandNode:
  139.       # Find the closest dist node
  140.       closestNode = ''; shortestdistance = sys.maxint;
  141.       for node,dist in distFromSourceSoFar.iteritems():
  142.         if node in expandNode and dist < shortestdistance:
  143.           closestNode,shortestdistance = node,dist
  144.       expandNode.remove(closestNode)
  145.       for neighbor in self.Link[closestNode].iterkeys():
  146.         recomputedist = distFromSourceSoFar[closestNode] + self.Link[closestNode][neighbor]
  147.         if recomputedist < distFromSourceSoFar[neighbor]:
  148.           distFromSourceSoFar[neighbor] = recomputedist
  149.     for node in distFromSourceSoFar:
  150.       print start,node,distFromSourceSoFar[node]
  151.   def AllpairsShortestPaths_MatrixMultiplication(self,start):
  152.     nodeIdx = {}; idxNode = {}; 
  153.     for idx,node in enumerate(self.MakeComponent(start,{})):
  154.       nodeIdx[node] = idx; idxNode[idx] = node
  155.     matrixSize = len(nodeIdx)
  156.     MaxInt = 1000
  157.     nodeMatrix = array([[MaxInt]*matrixSize]*matrixSize)
  158.     for node in nodeIdx.iterkeys():
  159.       nodeMatrix[nodeIdx[node]][nodeIdx[node]] = 0
  160.     for line in open(self.FileName,'r'):
  161.       nodeA,nodeB,cost = line.strip('\n').split(self.Separator)
  162.       if nodeA in nodeIdx:
  163.         nodeMatrix[nodeIdx[nodeA]][nodeIdx[nodeB]] = int(cost)
  164.         nodeMatrix[nodeIdx[nodeB]][nodeIdx[nodeA]] = int(cost)
  165.     result = array([[0]*matrixSize]*matrixSize)
  166.     for i in xrange(matrixSize):
  167.       for j in xrange(matrixSize):
  168.         result[i][j] = nodeMatrix[i][j]
  169.     for itertime in xrange(2,matrixSize):
  170.       for i in xrange(matrixSize):
  171.         for j in xrange(matrixSize):
  172.           if i==j:
  173.             result[i][j] = 0
  174.             continue
  175.           result[i][j] = MaxInt
  176.           for k in xrange(matrixSize):
  177.             result[i][j] = min(result[i][j],result[i][k]+nodeMatrix[k][j])
  178.     for i in xrange(matrixSize):
  179.       for j in xrange(matrixSize):
  180.         if result[i][j] != MaxInt:
  181.           print idxNode[i],idxNode[j],result[i][j]
  182.   def ShortestPathOne2All(self,start):
  183.     pathFromStart = {}
  184.     pathFromStart[start] = [start]
  185.     todoList = [start]
  186.     while todoList:
  187.       current = todoList.pop(0)
  188.       for neighbor in self.Link[current]:
  189.         if neighbor not in pathFromStart:
  190.           pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
  191.           todoList.append(neighbor)
  192.     return pathFromStart
  193.   def NDegreeNode(self,start,n):
  194.     pathFromStart = {}
  195.     pathFromStart[start] = [start]
  196.     pathLenFromStart = {}
  197.     pathLenFromStart[start] = 0
  198.     todoList = [start]
  199.     while todoList:
  200.       current = todoList.pop(0)
  201.       for neighbor in self.Link[current]:
  202.         if neighbor not in pathFromStart:
  203.           pathFromStart[neighbor] = pathFromStart[current] + [neighbor]
  204.           pathLenFromStart[neighbor] = pathLenFromStart[current] + 1
  205.           if pathLenFromStart[neighbor] <= n+1:
  206.             todoList.append(neighbor)
  207.     for node in pathFromStart.keys():
  208.       if len(pathFromStart[node]) != n+1:
  209.         del pathFromStart[node]
  210.     return pathFromStart
  211.   def Draw(self):
  212.     G = networkx.Graph()
  213.     nodes = self.Link.keys()
  214.     edges = [(node,neighbor) for node in nodes for neighbor in self.Link[node]]
  215.     G.add_edges_from(edges)
  216.     networkx.draw(G)
  217.     pyplot.show()
  218. if __name__=='__main__':
  219.   separator = '\t'
  220.   filename = 'C:\\Users\\Administrator\\Desktop\\graphdata.txt'
  221.   resultfilename = 'C:\\Users\\Administrator\\Desktop\\result.txt'
  222.   myGraph = Graph()
  223.   myGraph.MakeLink(filename,separator)
  224.   print 'LocalClusteringCoefficient',myGraph.LocalClusteringCoefficient('a')
  225.   print 'AverageClusteringCoefficient',myGraph.AverageClusteringCoefficient()
  226.   print 'DeepFirstSearch',myGraph.DeepFirstSearch('a')
  227.   print 'BreadthFirstSearch',myGraph.BreadthFirstSearch('a')
  228.   print 'ShortestPathOne2One',myGraph.ShortestPathOne2One('a','d')
  229.   print 'ShortestPathOne2All',myGraph.ShortestPathOne2All('a')
  230.   print 'NDegreeNode',myGraph.NDegreeNode('a',3).keys()
  231.   print 'ListAllComponent',myGraph.ListAllComponent()
  232.   print 'CheckConnection',myGraph.CheckConnection('a','f')
  233.   print 'Centrality',myGraph.Centrality('c')
  234.   myGraph.MinimumSpanningTree_Kruskal('a')
  235.   myGraph.AllpairsShortestPaths_MatrixMultiplication('a')
  236.   myGraph.MinimumSpanningTree_Prim('a')
  237.   myGraph.SingleSourceShortestPath_Dijkstra('a')
  238.   # myGraph.Draw()

更多Python图算法相关文章请关注PHP中文网！

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！