Skip to main content
 首页 » 编程设计

python之在深度优先搜索有向图时跟踪时间

2024年11月01日11yxwkf

我正在尝试对有向图进行深度优先搜索,同时我也在尝试跟踪有关该图的数据。首先,这是我用来构造有向图的类。

class Node(object): 
   def __init__(self, name): 
       self.name = str(name) 
   def getName(self): 
       return self.name 
   def __str__(self): 
       return self.name 
   def __repr__(self): 
      return self.name 
   def __eq__(self, other): 
      return self.name == other.name 
   def __ne__(self, other): 
      return not self.__eq__(other) 
 
class Edge(object): 
   def __init__(self, src, dest,distance,distance_out): 
       self.src = src 
       self.dest = dest 
       self.distance = distance 
       self.distance_out = distance_out 
   def getSource(self): 
       return self.src 
   def getDestination(self): 
       return self.dest 
   def getDistance(self): 
      return self.distance 
   def getDistance_Outdoors(self): 
      return self.distance_out 
   def __str__(self): 
       return str(self.src) + '--'+'Total Distance:(' +str(self.distance)+')' + ' '+ 'Outside Distance:('+str(self.distance_out)+')'+'-->' + str(self.dest) 
 
 
class Digraph(object): 
   """ 
   A directed graph 
   """ 
   def __init__(self): 
       self.nodes = set([]) 
       self.edges = {} 
   def addNode(self, node): 
       if node in self.nodes: 
           raise ValueError('Duplicate node') 
       else: 
           self.nodes.add(node) 
           self.edges[node] = [] 
   def addEdge(self, edge): 
       src = edge.getSource() 
       dest = edge.getDestination() 
       distance = edge.getDistance() 
       distance_out = edge.distance_out 
       if not(src in self.nodes and dest in self.nodes): 
           raise ValueError('Node not in graph') 
       self.edges[src].append([dest,[distance,distance_out]]) 
   def childrenOf(self, node): 
       return self.edges[node] 
   def hasNode(self, node): 
       return node in self.nodes 
   def testDict(self): 
      return self.edges 
   def __str__(self): 
       res = '' 
       for k in self.edges: 
           for d in self.edges[k]: 
               res = res + str(k) + '->' + str(d[0]) + str(d[1])+ '\n'  
       return res[:-1] 

我目前正在处理的有向图有 37 个节点和 129 条边。

这是我的搜索功能的代码。

import string 
from graph import Digraph, Edge, Node 
def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered , 
                          explored , nodes , hierarchy ): 
    time = time + 1 #While vertex has just been discovered 
    nodes[node].append(time) ##Mark the discovery time for the node in the nodes dictionary 
    discovered.append(node)##Mark the node as discovered 
    if node in undiscovered: ## Remove node from undiscovered after it's discovery 
        undiscovered.remove(node) 
    for adjacent_node in digraph.childrenOf(node):##Explore edge (node, adjacent_node) 
        if adjacent_node[0] in undiscovered: ##The adjacent node is a predecessor of the node 
            hierarchy[node].append(adjacent_node[0])##Mark it as such in the hierarchy dictionary 
            depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered, 
                                  undiscovered,explored,nodes,hierarchy)##Then recursively visit that adjacent_node 
    explored.append(node) ##After exploring all of the nodes adjacent 
    nodes[node].append(time) 
    return nodes 
def depthFirstSearch(digraph,time, discovered = [], undiscovered = [], 
                     explored = [], nodes = {}, hierarchy = {}): 
 
    if len(nodes) == 0: ## If nodes is empty 
        for i in digraph.nodes: ##Initialize a dictionary where nodes are the keys and  
            nodes[i] = [] ##An empty list for values, so they can be filled with discovery and exploration times 
    for key in nodes: ##For each node in the digraph mark them all as undiscovered. 
        undiscovered.append(key) 
    for key2 in nodes:##Construct hierarchy dict for later use in DepthFirstSearchVisit 
        hierarchy[key2] = [] 
    ##Time initialized to zero in parameter call 
    for node in nodes: 
        if node in undiscovered: 
            depthFirstSearchVisit(digraph,time,node,discovered, undiscovered, explored,nodes,hierarchy) 
    return nodes 

现在我正在测试字典节点是否输出正确的信息。这是节点字典的结构。

{node: [time of discovery, time of exploration]}  

发现时间是 DepthFirsTSearchVisit 第一次遇到一个节点时,探索时间是该节点的后代等一直向下都被发现的时间。

这是我得到的输出:

{32: [1, 1], 48: [4, 4], 50: [9, 9], 37: [17, 17], 13: [15, 15], 10: [25, 25], 64: [9, 9], 35: [18, 18], 5: [22, 22], 24: [14, 14], 6: [10, 10], 57: [2, 2], 9: [20, 20], 68: [6, 6], 39: [16, 16], 1: [23, 23], 38: [16, 16], 62: [8, 8], 4: [12, 12], 16: [4, 4], 34: [15, 15], 2: [9, 9], 54: [7, 7], 7: [21, 21], 66: [8, 8], 56: [5, 5], 46: [3, 3], 76: [7, 7], 18: [6, 6], 3: [24, 24], 36: [2, 2], 12: [13, 13], 33: [19, 19], 14: [8, 8], 8: [11, 11], 26: [3, 3], 31: [18, 18]} 

我认为我应该得到什么输出:时间值不应该相同。发现和探索之间应该有很大的区别。

在此先感谢您的帮助。

请您参考如下方法:

您将时间视为按引用传递。它不是 - 它是按值(value)传递的。这是因为 python 整数是不可变的。所以当你这样做时:

def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered , 
                          explored , nodes , hierarchy ): 
    time = time + 1 #While vertex has just been discovered 
    ... 

这创建了一个名为 time 的本地对象,它指向与输入时间相同的 int。然后递增它,现在 time 指向函数本地的一个新整数。稍后,当您执行此操作时:

depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered, 
     undiscovered,explored,nodes,hierarchy) 

它看起来像是期望子函数在它存在时增加时间,然后当它返回时,我传下来的时间将被修改。但实际上,它不会。

Python 变量传递对于其他语言的程序员来说可能有点困惑,因为它并不是真正的按引用或值传递,至少在 C++ 风格中不是这样。你有一个名字,它指向一个对象。当您调用一个函数时,该函数会获得一个新的本地名称,但它指向同一个对象。只要您不重新分配此名称,它就像按引用传递一样。但是一旦你重新分配它,你的本地名称现在指向一个新对象并且不再共享。

正如评论所说,最好只在顶部和底部调用 time.time()。

最后补充一点:如果你真的想要整数时间,使用 itertools.count 很容易。它必须是全局性的:

from itertools import count 
gtime = count(0) 
 
#Note: Removed time, as it's useless now 
def depthFirstSearchVisit(digraph, node,discovered, undiscovered , 
                          explored , nodes , hierarchy ): 
     starttime = gtime.next() 
     # Call some functions... 
     # .... 
     # Those also increment global time 
     endtime = gtime.next()