Python图算法实例分析

 #encoding=utf-8 import networkx,heapq,sys from matplotlib import pyplot from collections import defaultdict,OrderedDict from 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  10 def 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