Ответ 1
Прежде чем начать, Запустите код на CodeSkulptor! Я также надеюсь, что в комментариях уточняется, что я сделал достаточно. Если вам нужно больше объяснений, посмотрите мое объяснение рекурсивного подхода ниже кода.
# 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 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 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)
Ввод и (хорошо отформатированный и отступы) вывод можно найти здесь. Если вы хотите посмотреть, как я отформатировал вывод, обратитесь к коду, который также может быть найден на 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
- Первое, что мы делаем, это посетить node. Мы делаем это, увеличивая количество посещений node в словаре.
- Затем мы поднимаем событие
start
node. - Мы делаем простую проверку, чтобы увидеть, является ли node бездетным (лист) node или нет. Если это так, мы поднимаем событие
end
и возвращаем. - Теперь, когда мы установили, что у node есть соседи, мы перебираем каждый сосед. Боковое примечание:. Я реверсирую список соседей (используя
graph[node][::-1]
) в рекурсивной версии, чтобы поддерживать тот же порядок (справа налево) обхода соседей, как в итеративной версии.- Для каждого соседа мы сначала вычислим количество повторов. Счетчик повторов распространяется (наследуется) через узлы-предки, поэтому наследуемый счетчик повторений используется, если сосед не содержит значение повторения.
- Мы поднимаем событие
middle
текущего node ( not соседа), если второй (или более) соседний сосед обрабатывается. - Если сосед можно посетить, сосед будет посещен. Проверка посещаемости выполняется путем проверки того, был ли сосед посещен менее a)
MAX_THRESHOLD
раз (для псевдо-бесконечных циклов) и b) вычисленное выше количество отсчетов повторения.
- Теперь мы закончили с этим node; поднимите событие
end
и очистите его посещения в хеш-таблице. Это делается так, что если какой-то другой node вызывает его снова, он не отменяет проверку посещаемости и/или выполняет менее чем необходимое количество раз.