Cycles

Take a close look at the following static computational graph:

import logging
logging.basicConfig(level=logging.DEBUG)

import graphcat.notebook

graph = graphcat.StaticGraph()
logger = graphcat.Logger(graph)

graph.add_task("A")
graph.add_task("B")

graph.add_links("A", "B")
graph.add_links("B", "A")

Do you see a problem? Let’s look at the diagram:

graphcat.notebook.display(graph)

Notice the cycle in the graph - “B” depends on “A”, but “A” depends on “B”. This is a problem, because it means that both tasks depend on each other. This begs the question: what should happen when we execute either task, when it’s impossible to define which one should be executed first? You could imagine the computation getting stuck in an infinite loop, but as always this is Graphcat, and Graphcat always has your back. Let’s see what happens when we update one of the tasks - keep your hand close to the power switch:

graph.update("B")
graphcat.notebook.display(graph)

INFO:graphcat.common:Task B cycle detected.
INFO:graphcat.common:Task A updating.
INFO:graphcat.common:Task A executing. Inputs: {None: None}
INFO:graphcat.common:Task A finished. Output: None
INFO:graphcat.common:Task B updating.
INFO:graphcat.common:Task B executing. Inputs: {None: None}
INFO:graphcat.common:Task B finished. Output: None

Well, that wasn’t very exciting. Notice the first log message, where Graphcat has detected a cycle originating from task “B” (the task we executed). Graphcat detects the cycle and “breaks” it, so that the network executes in the same order that it would have if there wasn’t an edge from “B” to “A”, and both tasks are finished.

Let’s see what happens when we reset one of the tasks:

graph.mark_unfinished("A")
graphcat.notebook.display(graph)

Hmmm … as you might expect, Graphcat marked both tasks as unfinished, since they both depend on each other. Let’s try updating the other task:

graph.update("A")
graphcat.notebook.display(graph)

INFO:graphcat.common:Task A cycle detected.
INFO:graphcat.common:Task B updating.
INFO:graphcat.common:Task B executing. Inputs: {None: None}
INFO:graphcat.common:Task B finished. Output: None
INFO:graphcat.common:Task A updating.
INFO:graphcat.common:Task A executing. Inputs: {None: None}
INFO:graphcat.common:Task A finished. Output: None

This time the cycle is detected, but originating from task “A” (since that’s the task we executed). Execution proceeds in the same order that it would have if there wasn’t an edge from “A” to “B”.

What happens when our graph is more complex than just one cycle? Let’s add another task and see:

graph.mark_unfinished("A")
graph.add_task("C")
graph.add_links("B", "C")
graphcat.notebook.display(graph)

Now, when we execute “C”:

graph.update("C")
graphcat.notebook.display(graph)

INFO:graphcat.common:Task B cycle detected.
INFO:graphcat.common:Task A updating.
INFO:graphcat.common:Task A executing. Inputs: {None: None}
INFO:graphcat.common:Task A finished. Output: None
INFO:graphcat.common:Task B updating.
INFO:graphcat.common:Task B executing. Inputs: {None: None}
INFO:graphcat.common:Task B finished. Output: None
INFO:graphcat.common:Task C updating.
INFO:graphcat.common:Task C executing. Inputs: {None: None}
INFO:graphcat.common:Task C finished. Output: None

… the cycle is detected as originating at “B”, because it’s the first task on the cycle that’s upstream from “C”. From there, the graph executes as if there’s no edge from “B” to “A”.

So far, we’ve only been looking at static graphs. What about dynamic? Let’s recreate the same example using a dynamic graph:

graph = graphcat.DynamicGraph()
logger = graphcat.Logger(graph)

graph.add_task("A", graphcat.consume)
graph.add_task("B", graphcat.consume)
graph.add_task("C", graphcat.consume)
graph.add_links("A", "B")
graph.add_links("B", "A")
graph.add_links("B", "C")

graphcat.notebook.display(graph)

Note that we’ve assigned graphcat.consume as our task functions because this is a dynamic graph - without it, none of the tasks would use any of their inputs, and we wouldn’t actually cause a cycle.

Now, let’s update “C” again and see what happens:

graph.update("C")
graphcat.notebook.display(graph)

INFO:graphcat.common:Task C updating.
INFO:graphcat.common:Task C executing. Inputs: {None}
INFO:graphcat.common:Task B updating.
INFO:graphcat.common:Task B executing. Inputs: {None}
INFO:graphcat.common:Task A updating.
INFO:graphcat.common:Task A executing. Inputs: {None}
INFO:graphcat.common:Task B cycle detected.
INFO:graphcat.common:Task A finished. Output: None
INFO:graphcat.common:Task B finished. Output: None
INFO:graphcat.common:Task C finished. Output: None

Although the order of the logged messages is different because this is a dynamic graph, the cycle originating at “B” is detected, and the graph is executed as if the link from “B” to “A” doesn’t exist, just like the static version.

Final Thoughts

As you can see, Graphcat will never misbehave or hang due to a cycle in your graphs, and we’ve put in real effort to ensure that its behavior when cycles are encountered is consistent and well defined. This is to ensure that you can work confidently with Graphcat, never having to worry that an experiment or a misconfiguration will cause an infinite loop or a crash. Having said that, there is little reason to ever intentionally put cycles in a graph, because cycles are almost always the product of an ill-posed problem. When you have tasks with mutual dependencies, it typically means that you need to further decompose your problem into smaller sub-tasks, gradually teasing them apart until the interdependencies disappear.

If you want to enforce a “no cycles” policy, you can tap into the same signal mechanism used for logging to raise an exception or implement other behavior when a cycle occurs. For example:

def no_cycles_allowed(graph, name):
    raise RuntimeError(f"Illegal cycle detected originating with task {name}!")

graph.on_cycle.connect(no_cycles_allowed)

graph.mark_unfinished("A")

try:
    graph.update("C")
except Exception as e:
    print(f"Unhandled exception: {e}")

INFO:graphcat.common:Task C updating.
INFO:graphcat.common:Task C executing. Inputs: {None}
INFO:graphcat.common:Task B updating.
INFO:graphcat.common:Task B executing. Inputs: {None}
INFO:graphcat.common:Task A updating.
INFO:graphcat.common:Task A executing. Inputs: {None}
ERROR:graphcat.common:Task A failed. Exception: Illegal cycle detected originating with task B!
ERROR:graphcat.common:Task B failed. Exception: Illegal cycle detected originating with task B!
ERROR:graphcat.common:Task C failed. Exception: Illegal cycle detected originating with task B!

Unhandled exception: Illegal cycle detected originating with task B!