Python图算法实例分析
本文实例讲述了Python图算法。分享给大家供大家参考,具体如下:
#encoding=utf-8 importnetworkx,heapq,sys frommatplotlibimportpyplot fromcollectionsimportdefaultdict,OrderedDict fromnumpyimportarray #Dataingraphdata.txt: #ab4 #ah8 #bc8 #bh11 #hi7 #hg1 #gi6 #gf2 #cf4 #ci2 #cd7 #df14 #de9 #fe10 defEdge():returndefaultdict(Edge) classGraph: def__init__(self): self.Link=Edge() self.FileName='' self.Separator='' defMakeLink(self,filename,separator): self.FileName=filename self.Separator=separator graphfile=open(filename,'r') forlineingraphfile: items=line.split(separator) self.Link[items[0]][items[1]]=int(items[2]) self.Link[items[1]][items[0]]=int(items[2]) graphfile.close() defLocalClusteringCoefficient(self,node): neighbors=self.Link[node] iflen(neighbors)<=1:return0 links=0 forjinneighbors: forkinneighbors: ifjinself.Link[k]: links+=0.5 return2.0*links/(len(neighbors)*(len(neighbors)-1)) defAverageClusteringCoefficient(self): total=0.0 fornodeinself.Link.keys(): total+=self.LocalClusteringCoefficient(node) returntotal/len(self.Link.keys()) defDeepFirstSearch(self,start): visitedNodes=[] todoList=[start] whiletodoList: visit=todoList.pop(0) ifvisitnotinvisitedNodes: visitedNodes.append(visit) todoList=self.Link[visit].keys()+todoList returnvisitedNodes defBreadthFirstSearch(self,start): visitedNodes=[] todoList=[start] whiletodoList: visit=todoList.pop(0) ifvisitnotinvisitedNodes: visitedNodes.append(visit) todoList=todoList+self.Link[visit].keys() returnvisitedNodes defListAllComponent(self): allComponent=[] visited={} fornodeinself.Link.iterkeys(): ifnodenotinvisited: oneComponent=self.MakeComponent(node,visited) allComponent.append(oneComponent) returnallComponent defCheckConnection(self,node1,node2): returnTrueifnode2inself.MakeComponent(node1,{})elseFalse defMakeComponent(self,node,visited): visited[node]=True component=[node] forneighborinself.Link[node]: ifneighbornotinvisited: component+=self.MakeComponent(neighbor,visited) returncomponent defMinimumSpanningTree_Kruskal(self,start): graphEdges=[line.strip('\n').split(self.Separator)forlineinopen(self.FileName,'r')] nodeSet={} foridx,nodeinenumerate(self.MakeComponent(start,{})): nodeSet[node]=idx edgeNumber=0;totalEdgeNumber=len(nodeSet)-1 foroneEdgeinsorted(graphEdges,key=lambdax:int(x[2]),reverse=False): ifedgeNumber==totalEdgeNumber:break nodeA,nodeB,cost=oneEdge ifnodeAinnodeSetandnodeSet[nodeA]!=nodeSet[nodeB]: nodeBSet=nodeSet[nodeB] fornodeinnodeSet.keys(): ifnodeSet[node]==nodeBSet: nodeSet[node]=nodeSet[nodeA] printnodeA,nodeB,cost edgeNumber+=1 defMinimumSpanningTree_Prim(self,start): expandNode=set(self.MakeComponent(start,{})) distFromTreeSoFar={}.fromkeys(expandNode,sys.maxint);distFromTreeSoFar[start]=0 linkToNode={}.fromkeys(expandNode,'');linkToNode[start]=start whileexpandNode: #Findtheclosestdistnode closestNode='';shortestdistance=sys.maxint; fornode,distindistFromTreeSoFar.iteritems(): ifnodeinexpandNodeanddist<shortestdistance: closestNode,shortestdistance=node,dist expandNode.remove(closestNode) printlinkToNode[closestNode],closestNode,shortestdistance forneighborinself.Link[closestNode].iterkeys(): recomputedist=self.Link[closestNode][neighbor] ifrecomputedist<distFromTreeSoFar[neighbor]: distFromTreeSoFar[neighbor]=recomputedist linkToNode[neighbor]=closestNode defShortestPathOne2One(self,start,end): pathFromStart={} pathFromStart[start]=[start] todoList=[start] whiletodoList: current=todoList.pop(0) forneighborinself.Link[current]: ifneighbornotinpathFromStart: pathFromStart[neighbor]=pathFromStart[current]+[neighbor] ifneighbor==end: returnpathFromStart[end] todoList.append(neighbor) return[] defCentrality(self,node): path2All=self.ShortestPathOne2All(node) #Theaverageofthedistancesofallthereachablenodes returnfloat(sum([len(path)-1forpathinpath2All.itervalues()]))/len(path2All) defSingleSourceShortestPath_Dijkstra(self,start): expandNode=set(self.MakeComponent(start,{})) distFromSourceSoFar={}.fromkeys(expandNode,sys.maxint);distFromSourceSoFar[start]=0 whileexpandNode: #Findtheclosestdistnode closestNode='';shortestdistance=sys.maxint; fornode,distindistFromSourceSoFar.iteritems(): ifnodeinexpandNodeanddist<shortestdistance: closestNode,shortestdistance=node,dist expandNode.remove(closestNode) forneighborinself.Link[closestNode].iterkeys(): recomputedist=distFromSourceSoFar[closestNode]+self.Link[closestNode][neighbor] ifrecomputedist<distFromSourceSoFar[neighbor]: distFromSourceSoFar[neighbor]=recomputedist fornodeindistFromSourceSoFar: printstart,node,distFromSourceSoFar[node] defAllpairsShortestPaths_MatrixMultiplication(self,start): nodeIdx={};idxNode={}; foridx,nodeinenumerate(self.MakeComponent(start,{})): nodeIdx[node]=idx;idxNode[idx]=node matrixSize=len(nodeIdx) MaxInt=1000 nodeMatrix=array([[MaxInt]*matrixSize]*matrixSize) fornodeinnodeIdx.iterkeys(): nodeMatrix[nodeIdx[node]][nodeIdx[node]]=0 forlineinopen(self.FileName,'r'): nodeA,nodeB,cost=line.strip('\n').split(self.Separator) ifnodeAinnodeIdx: nodeMatrix[nodeIdx[nodeA]][nodeIdx[nodeB]]=int(cost) nodeMatrix[nodeIdx[nodeB]][nodeIdx[nodeA]]=int(cost) result=array([[0]*matrixSize]*matrixSize) foriinxrange(matrixSize): forjinxrange(matrixSize): result[i][j]=nodeMatrix[i][j] foritertimeinxrange(2,matrixSize): foriinxrange(matrixSize): forjinxrange(matrixSize): ifi==j: result[i][j]=0 continue result[i][j]=MaxInt forkinxrange(matrixSize): result[i][j]=min(result[i][j],result[i][k]+nodeMatrix[k][j]) foriinxrange(matrixSize): forjinxrange(matrixSize): ifresult[i][j]!=MaxInt: printidxNode[i],idxNode[j],result[i][j] defShortestPathOne2All(self,start): pathFromStart={} pathFromStart[start]=[start] todoList=[start] whiletodoList: current=todoList.pop(0) forneighborinself.Link[current]: ifneighbornotinpathFromStart: pathFromStart[neighbor]=pathFromStart[current]+[neighbor] todoList.append(neighbor) returnpathFromStart defNDegreeNode(self,start,n): pathFromStart={} pathFromStart[start]=[start] pathLenFromStart={} pathLenFromStart[start]=0 todoList=[start] whiletodoList: current=todoList.pop(0) forneighborinself.Link[current]: ifneighbornotinpathFromStart: pathFromStart[neighbor]=pathFromStart[current]+[neighbor] pathLenFromStart[neighbor]=pathLenFromStart[current]+1 ifpathLenFromStart[neighbor]<=n+1: todoList.append(neighbor) fornodeinpathFromStart.keys(): iflen(pathFromStart[node])!=n+1: delpathFromStart[node] returnpathFromStart defDraw(self): G=networkx.Graph() nodes=self.Link.keys() edges=[(node,neighbor)fornodeinnodesforneighborinself.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数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。