我试图对有向图进行深度优先搜索,在搜索的同时,我还试图跟踪有关图的数据。首先,这里是我用来构造有向图的类。
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]}
我认为我应该得到什么输出:时间值不应该相同。发现和探索之间应该有很大的区别。
提前感谢您的帮助。
您将时间视为通过引用传递的。事实并非如此,而是通过价值传递。这是因为python int是不可变的。所以当你这样做的时候:
def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered ,
explored , nodes , hierarchy ):
time = time + 1 #While vertex has just been discovered
...
这创建了一个本地调用时间,它指向与输入时间相同的int。然后递增它,现在时间指向函数本地的一个新整数。然后,当你这样做时:
depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered,
undiscovered,explored,nodes,hierarchy)
看起来我们希望子函数在它存在的时候增加时间,然后当它返回时,我传递的时间将被修改。但事实上,它不会。
Python变量传递对于其他语言的程序员来说可能有点困惑,因为它并不是真正的通过引用OR值传递,至少在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()