- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
概览
我试图弄清楚如何使用某种 DFS 迭代算法遍历 有向循环图。这是我目前实现的一个小 mcve 版本(它不处理循环):
class Node(object):
def __init__(self, name):
self.name = name
def start(self):
print '{}_start'.format(self)
def middle(self):
print '{}_middle'.format(self)
def end(self):
print '{}_end'.format(self)
def __str__(self):
return "{0}".format(self.name)
class NodeRepeat(Node):
def __init__(self, name, num_repeats=1):
super(NodeRepeat, self).__init__(name)
self.num_repeats = num_repeats
def dfs(graph, start):
"""Traverse graph from start node using DFS with reversed childs"""
visited = {}
stack = [(start, "")]
while stack:
# To convert dfs -> bfs
# a) rename stack to queue
# b) pop becomes pop(0)
node, parent = stack.pop()
if parent is None:
if visited[node] < 3:
node.end()
visited[node] = 3
elif node not in visited:
if visited.get(parent) == 2:
parent.middle()
elif visited.get(parent) == 1:
visited[parent] = 2
node.start()
visited[node] = 1
stack.append((node, None))
# Maybe you want a different order, if it's so, don't use reversed
childs = reversed(graph.get(node, []))
for child in childs:
if child not in visited:
stack.append((child, node))
if __name__ == "__main__":
Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = NodeRepeat('Repeat1', num_repeats=2)
Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = NodeRepeat('Repeat2', num_repeats=3)
Mesh = Node('Mesh')
cyclic_graph = {
Sequence1: [MtxPushPop1, Rotate1],
MtxPushPop1: [Sequence2],
Rotate1: [Repeat1],
Sequence2: [MtxPushPop2, Translate],
Repeat1: [Sequence1],
MtxPushPop2: [Rotate2],
Translate: [Rotate3],
Rotate2: [Scale],
Rotate3: [Repeat2],
Scale: [Mesh],
Repeat2: [Sequence2]
}
dfs(cyclic_graph, Sequence1)
print '-'*80
a = Node('a')
b = Node('b')
dfs({
a : [b],
b : [a]
}, a)
上面的代码正在测试几个案例,第一个是下图的某种表示:
第二种是一个图包含一个“无限”循环的最简单情况{a->b, b->a}
要求
Repeat
的特殊节点,您可以在其中指示围绕循环循环的迭代次数问题
谁能提供某种知道如何遍历无限/有限循环的解决方案?
引用文献
如果此时问题还不清楚,您可以在 article 上阅读更多关于此问题的信息。 ,整个想法将使用遍历算法来实现类似的工具,如那篇文章中所示。
这是一个屏幕截图,展示了这种数据结构的全部功能,我想弄清楚如何遍历和运行:
最佳答案
在我开始之前,Run the code on CodeSkulptor!我也希望评论能详细说明我所做的足够多的事情。如果您需要更多解释,请查看我在代码下方对 recursive 方法的解释。
# If you don't want global variables, remove the indentation procedures
indent = -1
MAX_THRESHOLD = 10
INF = 1 << 63
def whitespace():
global indent
return '| ' * (indent)
class Node:
def __init__(self, name, num_repeats=INF):
self.name = name
self.num_repeats = num_repeats
def start(self):
global indent
if self.name.find('Sequence') != -1:
print whitespace()
indent += 1
print whitespace() + '%s_start' % self.name
def middle(self):
print whitespace() + '%s_middle' % self.name
def end(self):
global indent
print whitespace() + '%s_end' % self.name
if self.name.find('Sequence') != -1:
indent -= 1
print whitespace()
def dfs(graph, start):
visits = {}
frontier = [] # The stack that keeps track of nodes to visit
# Whenever we "visit" a node, increase its visit count
frontier.append((start, start.num_repeats))
visits[start] = visits.get(start, 0) + 1
while frontier:
# parent_repeat_count usually contains vertex.repeat_count
# But, it may contain a higher value if a repeat node is its ancestor
vertex, parent_repeat_count = frontier.pop()
# Special case which signifies the end
if parent_repeat_count == -1:
vertex.end()
# We're done with this vertex, clear visits so that
# if any other node calls us, we're still able to be called
visits[vertex] = 0
continue
# Special case which signifies the middle
if parent_repeat_count == -2:
vertex.middle()
continue
# Send the start message
vertex.start()
# Add the node's end state to the stack first
# So that it is executed last
frontier.append((vertex, -1))
# No more children, continue
# Because of the above line, the end method will
# still be executed
if vertex not in graph:
continue
## Uncomment the following line if you want to go left to right neighbor
#### graph[vertex].reverse()
for i, neighbor in enumerate(graph[vertex]):
# The repeat count should propagate amongst neighbors
# That is if the parent had a higher repeat count, use that instead
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
# We've gone through at least one neighbor node
# Append this vertex's middle state to the stack
if i >= 1:
frontier.append((vertex, -2))
# If we've not visited the neighbor more times than we have to, visit it
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
frontier.append((neighbor, repeat_count))
visits[neighbor] = visits.get(neighbor, 0) + 1
def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
visits[node] = visits.get(node, 0) + 1
node.start()
if node not in graph:
node.end()
return
for i, neighbor in enumerate(graph[node][::-1]):
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
if i >= 1:
node.middle()
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
dfs_rec(graph, neighbor, repeat_count, visits)
node.end()
visits[node] = 0
Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = Node('Repeat1', 2)
Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = Node('Repeat2', 3)
Mesh = Node('Mesh')
cyclic_graph = {
Sequence1: [MtxPushPop1, Rotate1],
MtxPushPop1: [Sequence2],
Rotate1: [Repeat1],
Sequence2: [MtxPushPop2, Translate],
Repeat1: [Sequence1],
MtxPushPop2: [Rotate2],
Translate: [Rotate3],
Rotate2: [Scale],
Rotate3: [Repeat2],
Scale: [Mesh],
Repeat2: [Sequence2]
}
dfs(cyclic_graph, Sequence1)
print '-'*40
dfs_rec(cyclic_graph, Sequence1)
print '-'*40
dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)
print '-'*40
dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)
输入和(格式和缩进良好的)输出可以在 here 中找到.如果想看如何我格式化输出,请引用代码,也可以是found on CodeSkulptor .
好的,继续解释。下面是更容易理解但效率更低的递归解决方案,我将使用它来帮助解释:
def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
visits[node] = visits.get(node, 0) + 1
node.start()
if node not in graph:
node.end()
return
for i, neighbor in enumerate(graph[node][::-1]):
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
if i >= 1:
node.middle()
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
dfs_rec(graph, neighbor, repeat_count, visits)
node.end()
visits[node] = 0
start
事件。end
事件并返回。graph[node][::-1]
)以保持相同的顺序(从右到左)在迭代版本中遍历邻居。
middle
事件。MAX_THRESHOLD
次(对于伪无限循环)和 b) 以上计算的重复计数次数。end
事件并清除其在哈希表中的访问。这样做是为了如果其他节点再次调用它,它不会使可访问性检查失败和/或执行的次数少于所需的次数。关于python - 如何使用改进的 DFS 算法遍历循环有向图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39427638/
我是 PHP 新手。我一直在脚本中使用 for 循环、while 循环、foreach 循环。我想知道 哪个性能更好? 选择循环的标准是什么? 当我们在另一个循环中循环时应该使用哪个? 我一直想知道要
我在高中的编程课上,我的作业是制作一个基本的小计和顶级计算器,但我在一家餐馆工作,所以制作一个只能让你在一种食物中读到。因此,我尝试让它能够接收多种食品并将它们添加到一个价格变量中。抱歉,如果某些代码
这是我正在学习的一本教科书。 var ingredients = ["eggs", "milk", "flour", "sugar", "baking soda", "baking powder",
我正在从字符串中提取数字并将其传递给函数。我想给它加 1,然后返回字符串,同时保留前导零。我可以使用 while 循环来完成此操作,但不能使用 for 循环。 for 循环只是跳过零。 var add
编辑:我已经在程序的输出中进行了编辑。 该程序要求估计给定值 mu。用户给出一个值 mu,同时还提供了四个不等于 1 的不同数字(称为 w、x、y、z)。然后,程序尝试使用 de Jaeger 公式找
我正在编写一个算法,该算法对一个整数数组从末尾到开头执行一个大循环,其中包含一个 if 条件。第一次条件为假时,循环可以终止。 因此,对于 for 循环,如果条件为假,它会继续迭代并进行简单的变量更改
现在我已经习惯了在内存非常有限的情况下进行编程,但我没有答案的一个问题是:哪个内存效率更高;- for(;;) 或 while() ?还是它们可以平等互换?如果有的话,还要对效率问题发表评论! 最佳答
这个问题已经有答案了: How do I compare strings in Java? (23 个回答) 已关闭 8 年前。 我正在尝试创建一个小程序,我可以在其中读取该程序的单词。如果单词有 6
这个问题在这里已经有了答案: python : list index out of range error while iteratively popping elements (12 个答案) 关
我正在尝试向用户请求 4 到 10 之间的整数。如果他们回答超出该范围,它将进入循环。当用户第一次正确输入数字时,它不会中断并继续执行 else 语句。如果用户在 else 语句中正确输入数字,它将正
我尝试创建一个带有嵌套 foreach 循环的列表。第一个循环是循环一些数字,第二个循环是循环日期。我想给一个日期写一个数字。所以还有另一个功能来检查它。但结果是数字多次写入日期。 Out 是这样的:
我想要做的事情是使用循环创建一个数组,然后在另一个类中调用该数组,这不会做,也可能永远不会做。解决这个问题最好的方法是什么?我已经寻找了所有解决方案,但它们无法编译。感谢您的帮助。 import ja
我尝试创建一个带有嵌套 foreach 循环的列表。第一个循环是循环一些数字,第二个循环是循环日期。我想给一个日期写一个数字。所以还有另一个功能来检查它。但结果是数字多次写入日期。 Out 是这样的:
我正在模拟一家快餐店三个多小时。这三个小时分为 18 个间隔,每个间隔 600 秒。每个间隔都会输出有关这 600 秒内发生的情况的统计信息。 我原来的结构是这样的: int i; for (i=0;
这个问题已经有答案了: IE8 for...in enumerator (3 个回答) How do I check if an object has a specific property in J
哪个对性能更好?这可能与其他编程语言不一致,所以如果它们不同,或者如果你能用你对特定语言的知识回答我的问题,请解释。 我将使用 c++ 作为示例,但我想知道它在 java、c 或任何其他主流语言中的工
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
我是 C 编程和编写代码的新手,以确定 M 测试用例的质因数分解。如果我一次只扫描一次,该功能本身就可以工作,但是当我尝试执行 M 次时却惨遭失败。 我不知道为什么 scanf() 循环有问题。 in
这个问题已经有答案了: JavaScript by reference vs. by value [duplicate] (4 个回答) 已关闭 3 年前。 我在使用 TSlint 时遇到问题,并且理
我尝试在下面的代码中添加 foreach 或 for 循环,以便为 Charts.js 创建多个数据集。这将允许我在此折线图上创建多条线。 我有一个 PHP 对象,我可以对其进行编码以稍后填充变量,但
我是一名优秀的程序员,十分优秀!