Python图算法实例分析_Python

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

									            continue

									          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()