Считать и сбрасывать глубину цепочки в DFS Python
Есть граф следующего формата:
graph = {
'1': ['2', '34', '4'],
'2': ['4', '9', '3', '65', 14],
'3': ['18', '7', '1'],
'4': ['3', '11'],
'5': ['11', '3', '4'],
...
}
Вводная: Все числа это id пользователей. Сам граф показыват связь учитель-ученик. То есть, например, у юзера 4 есть ученики 3 и 11. В графе также могут присутствовать "двойные" связи, когда оба юзера приходятся друг другу и учителем и учеником.
Задача: Нужно пройтись по графу и за каждого ученика, внученика, правнученика (и так до последнего "пра") посчитать для учителя определенные очки. Для каждое вну/пра даются свои очки.
Что я делаю: Я прохожусь по графу DFSом, считаю глубину цепочки и в зависимости от текущей грубины назначаю очки за ученика/внученика/правнученика и т.д. Однако, подсчет глубины цепочки нужно сбрасывать, каждый раз, когда я возвращаюсь обратно к корню графа, чтобы правильно назначать очки за учеников. И вот на этом моменте я сдулся, не помнию, как сбросить счетчик глубины, и точно ли я вообще иду в том направлении. Подскажите/направьте пожалуйста.
Код:
def dfs(visited, graph, node, chain):
points = 0
if node not in visited:
visited.add(node)
for neighbour in graph[node]:
if chain == 0:
points += 2
chain += 1
elif chain == 1:
points += 1
chain += 1
elif chain > 1:
points += 0.1 / chain
chain += 1
points += dfs(visited, graph, neighbour, chain)
return points
def run():
users = list(users_collection.find({}))
graph = get_graph(users)
for user in users:
visited = set()
total_points = dfs(visited, graph, str(user['_id']), 0)
print(user['name'], total_points, user['_id'])
if __name__ == "__main__":
run()