Блог

Вопрос:

Я думал, что смогу проанализировать этот JSON для создания графика, и для этого тривиального графика в начальном узле я вижу, что я подключен к ребрам B и C. Таким образом, я могу напечатать B через 5 секунд, а затем напечатать C через 7 секунд, так что разница между тем, когда печатаются B и C, составляет 2 секунды.

Однако мое понимание того, как с этим справиться, нарушается, когда граф становится более сложным, и мне нужно будет обрабатывать несколько уровней вершин. Могу ли я получить некоторые рекомендации о том, как я должен думать об этом? Я думаю, что мне нужно будет выполнить какой-то поиск по ширине, но как я могу гарантировать, что смогу печатать в правильном порядке, если граф имеет глубину в несколько вершин? Или что, если несколько вершин указывают на одну и ту же вершину?

Например, скажем, для данного графика у меня есть другое ребро от C до B, мне также нужно будет снова напечатать «B» через X секунд, где X-значение ребра.

Если бы вы могли дать конкретные рекомендации на Python, это было бы очень ценно, но любой тип языка также работает.

Здесь вы можете использовать алгоритм Дейкстры. Обычно это связано с очередью приоритетов, но здесь мы можем предположить, что количество секунд будет реалистичным для бегуна, т. Е. Количество секунд не будет исчисляться миллионами. В этом случае вы можете создать временную линию в виде списка, где каждая запись в списке представляет собой секунду, а сама запись представляет собой список узлов, срок действия которых «истекает», т. Е. Куда прибывает бегун, когда наступает эта секунда.

Вот как это будет работать-За каждую проходящую секунду я звоню сюда sleep(0.1) . Так и должно быть sleep(1) , но так оно работает немного быстрее:

 from time import sleep

def runner(graph):
    # Find node to start with
    node = next(node for node in graph if graph[node].get("start"))
    # Put start node on the time line at second 0
    timeline = [[node]]
    now = 0
    while now < len(timeline):
        print(now, *timeline[now])  # print the nodes the expire now
        for node in timeline[now]:  # for each of them:
            for neighbor, delay in graph[node]["edges"].items():
                future = now   delay
                # Extend time line if not long enough
                while len(timeline) <= future:
                    timeline.append([])
                # Add this neighbor on the time line
                timeline[future].append(neighbor)
        now  = 1  # Go to next second
        sleep(0.1)  # Wait for a (tenth of a) second
 

С примером в вопросе вы бы назвали его следующим образом:

 graph = {
    "A": { "start": True, "edges": { "B": 5, "C": 7 } },
    "B": { "edges": {} },
    "C": { "edges": {} }
}
runner(graph)
 

Это приводит к получению этого результата:

 0 A
1
2
3
4
5 B
6
7 C
 

Если вы не хотите, чтобы ваш алгоритм на самом деле печатал эти промежуточные секунды, и вообще не хотите этого sleep , а просто печатаете узлы в ожидаемом порядке, затем переместите print внутренний внешний for цикл, сделайте его печатным print(now, node) и удалите вызов sleep . Тогда выход будет:

 0 A
5 B
7 C
 

Список временной шкалы может стать очень длинным-если количество накопленных секунд станет большим. В этом случае преобразуйте этот код для использования минимальной кучи вместо простого списка и помещайте (time, node) кортежи в эту кучу:

 from heapq import heappush, heappop

def runner(graph):
    # Find node to start with
    node = next(node for node in graph if graph[node].get("start"))
    # Put start node on the heap at second 0
    timeheap = [(0, node)]
    while timeheap:
        (now, node) = heappop(timeheap)
        print(now, node)
        for neighbor, delay in graph[node]["edges"].items():
            future = now   delay
            # Add this neighbor on the heap
            heappush(timeheap, (future, neighbor))
 

Вы можете отслеживать список «активных» узлов вместе с их временем срабатывания. Спите до следующего времени срабатывания, а затем распечатайте запущенные узлы и добавьте более активные узлы из тех, которые были запущены:

 graph = {
    "A": { "start": True, "edges": { "B": 5, "C": 7 } },
    "B": { "edges": {} },
    "C": { "edges": {} }
}

import time

activeNodes = [(node,0) for node,d in graph.items() if d.get("start",False)]
timeCounter = 0 
while activeNodes:
    sleepTime    = min(time-timeCounter for _,time in activeNodes) # wait for earliest trigger time
    time.sleep(sleepTime)
    timeCounter  = sleepTime                                                # advance time counter
    trigger      = {node for node,time in activeNodes if time==timeCounter} # identify triggered nodes
    print(time.strftime('%H:%M:%S'),trigger)
    activeNodes  = [(node,time) for node,time in activeNodes if node not in trigger] # remove triggered 
    activeNodes  = [nodeTime for t in trigger for nodeTime in graph[t]["edges"].items()] # activate more
 

Выход:

 21:14:39 {'A'}
21:14:44 {'B'}
21:14:46 {'C'}