How to print a directed a-cyclical graph in this order?-CodePudding

Question:

I was thinking I can parse this JSON to generate the graph, and for this trivial graph, at the start node, I can see that I am connected to the edges B and C. Thus, I can print B after 5 seconds and then print C after 7 seconds such that the difference between when B and C are printed is 2 seconds.

However, my understanding of how to handle this breaks down when the graph is more complex and I will need to handle multiple levels of vertices. Could I get some guidance on how I should be thinking of handling this? I am thinking that I would need to perform some type of breadth first search, but how can I ensure that I am able to print in the correct order if the graph is several vertices deep? Or what if multiple vertices point to the same vertex?

For example, say for the given graph I have another edge from C to B, I would also need to print "B" again after X number of seconds where X is the edge value.

If you could give guidance in Python specifically that would be much appreciated, but any type of language works as well.

CodePudding user response：

You could use Dijkstra's algorithm here. This would typically involve a priority queue, but here we may maybe assume that the number of seconds will be realistic for a runner to run, i.e. the number of seconds will not be in the millions. In that case you can create a time line as a list, where every list entry represents a second, and the entry itself is a list of nodes that "expire", i.e. where the runner arrives when that second comes to pass.

Here is how that would work -- For every second that passes I call here sleep(0.1). It really should be sleep(1), but this way it runs a bit faster:

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

With the example in the question, you would call it as follows:

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

This produces this output:

If you don't want your algorithm to actually print those intermediate seconds, and don't want it to sleep at all, but just print the nodes in the expected order, then move the print inside the outer for loop, make it print print(now, node) and remove the call to sleep. Then the output is:

0 A
5 B
7 C

The timeline list may get very long -- if the number of accumulated seconds becomes large. In that case convert this code to use a min-heap instead of a plain list, and push (time, node) tuples on that heap:

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))

CodePudding user response：

You could track a list of "active" nodes along with their trigger time. Sleep until the next trigger time and then print the triggered nodes and add more active nodes from the ones that were triggered:

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

Output:

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