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程序设计有所帮助。