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

Question

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

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]}

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

在此先感谢您的帮助。

Answer 1

您将时间视为按引用传递。它不是 - 它是按值(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()