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

更多关于Python相关内容可查看本站专题：《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。