Dynamic Graphs

This section assumes you’ve completed the Tutorial and have a good working knowledge of Graphcat.

Graphcat always ensures that tasks are executed when they’re needed and in the correct order, but there can be more than way to define “when a task is needed”, and those definitions have different tradeoffs in time and space. Graphcat allows you to select among those tradeoffs by providing two main types of graph: static and dynamic. To illustrate the difference between the two, we will setup a simple static graph:

import graphcat.notebook

graph = graphcat.StaticGraph()
graph.add_task("A", graphcat.constant("A"))
graph.add_task("B", graphcat.constant("B"))
graph.add_task("C", graphcat.passthrough(input=0))
graph.add_links("A", ("C", 0))
graph.add_links("B", ("C", 1))

graphcat.notebook.display(graph)

Note that there are two tasks “A” and “B” that produce the strings "A" and "B" respectively, connected to inputs 0 and 1 of task “C”. In turn, task “C” uses the graphcat.common.passthrough() function to return whatever value it receives from input 0:

print("Output:", graph.output("C"))
graphcat.notebook.display(graph)

Output: A

… as expected, task “C” returns "A", and all three tasks are finished (solid boxes), because tasks “A” and “B” are inputs to task “C”. This is what we mean when we say that the graph is static: it performs a static analysis of the graph topology to determine which tasks are inputs to “C”, and then executes them first.

However, a static analysis can be suboptimal: in this case, even though task “B” is an input to “C”, it isn’t really needed, since “C” is only using the input named 0. What if task “B” were time consuming? All of that effort is wasted if the output from “B” is never actually used by “C”.

Fortunately, we can use dynamic analysis to determine which tasks need to be executed during updates based on whether or not they actually get used. To do so, we simply use an instance of DynamicGraph instead of StaticGraph:

graph = graphcat.DynamicGraph()
graph.add_task("A", graphcat.constant("A"))
graph.add_task("B", graphcat.constant("B"))
graph.add_task("C", graphcat.passthrough(input=0))
graph.add_links("A", ("C", 0))
graph.add_links("B", ("C", 1))

graphcat.notebook.display(graph)

Note

The arrow heads in the diagram are open instead of solid, which indicates that this is a DynamicGraph.

Now, when we get the output from “C”, we should still get the same answer:

print("Output:", graph.output("C"))
graphcat.notebook.display(graph)

Output: A

… which we do, but task “B” hasn’t been executed, because it isn’t needed in this case. If we alter task “C” so that it uses its other input, we should see that task “B” gets executed:

graph.set_task("C", graphcat.passthrough(input=1))
print("Output:", graph.output("C"))
graphcat.notebook.display(graph)

Output: B

Voila! We see that task “B” is executed, because its output is now used by task “C”.

Given that dynamic graphs are potentially more efficient by eliminating unneeded computation, why have static graphs at all? This is because dynamic graphs use more resources to run, and may exceed the Python interpreter stack limits for large, complex graphs. As of this writing, Python has a default stack recursion limit of 1000, which means that updating a dynamic graph will fail as the number of tasks upstream from the task being updated nears a thousand. In those cases you can increase the recursion limit using sys.setrecursionlimit(), or switch back to static graphs, which may waste some computation, but will never run out of stack space.