I started taking notes about a potential implementation of Event Driven Processing (EDP) on Trello but figured I might as well share the adventure here by making a thread into a kind of journal.
If the goal of EDP is to allow for a graphlike structure of plugins, ordered arbitrarily and eventually visually as nodes and edges, then an alternative to EDP achieving the same goal is an directed acyclic graph (DAG), the practical difference being that one is dynamically discovering which task to perform next (EDP) whereas the other is static and decided upfront (DAG).
Pros/Cons
The benefit of EDP may lie in itâ€™s flexibility and potential for an infinitely large graph at the cost of not being able to map upfront what it is going to do, leading to behaviour that is difficult to debug and reproduce.
A DAG on the other hand is predetermined, meaning it is predictable, easy to reproduce and favours parallelism at the cost of requiring all dependencies to be available from the getgo.
Familiarity with implementing and programming with EDP (for me personally) comes from working with GUIs and Qt specifically, whereas the use and practice of DAGs comes from DCCs; Maya, Nuke and Houdini specifically.
Implementation
After some research, it looks like DAG and Topological Sort are very common amongst task scheduling programs like Pyblish and relatively easy to implement (given you understand the basics).
 https://github.com/airbnb/airflow
 https://github.com/thieman/dagobah
 https://github.com/pinterest/pinball
 https://github.com/andrewgardner/dependsworkflow
Iâ€™m looking to have it implemented into Pyblish as an extension (pyblishdag). Meaning it could potentially be a dropin replacement for the order
attribute currently in place to determine which plugins to run next.
Meaning you could potentially choose algorithm on a perrun basis, but more importantly means it can flourish (or perish) in isolation, making room for other algorithms including EDP.
Hereâ€™s a full implementation of a DAG along with DepthFirst Search and Topological Sorting, the primary ingredients for setting up plugin dependencies and ordering them accordingly, adapted from here.
import sys
class Graph(dict):
def __iter__(self):
for value in self.values():
yield value
def add_vertex(self, key):
newVertex = Vertex(key)
self[key] = newVertex
return newVertex
def add_edge(self,f,t,cost=0):
if f not in self:
self.add_vertex(f)
if t not in self:
self.add_vertex(t)
self[f].add_neighbor(self[t], cost)
class Vertex(dict):
def __init__(self, id):
self.id = id
self.color = "white"
self.distance = sys.maxsize
self.pred = None
self.discovery = 0
self.finish = 0
def __iter__(self):
for value in self.values():
yield value
def __hash__(self):
return hash(self.id)
def __str__(self):
return str(self.id)
def __repr__(self):
return self.__str__()
@property
def connections(self):
return self.keys()
def add_neighbor(self,nbr,weight=0):
self[nbr] = weight
class DfsGraph(Graph):
def __init__(self):
self.time = 0
def dfs(self):
for vertex in self:
vertex.color = "white"
vertex.pred = 1
for vertex in self:
if vertex.color == "white":
self.visit(vertex)
def visit(self, start_vertex):
self.time += 1
start_vertex.color = "gray"
start_vertex.discovery = self.time
for next_vertex in start_vertex.connections:
if next_vertex.color == "white":
next_vertex.pred = start_vertex
self.visit(next_vertex)
start_vertex.color = "black"
start_vertex.finish = self.time
self.time += 1
def toposorted(g):
return sorted(g, key=lambda v: v.finish, reverse=True)
if __name__ == "__main__":
g = DfsGraph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(5, 6)
g.add_edge(5, 7)
g.add_edge(5, 8)
g.dfs() # Perform depthfirst search
print toposorted(g) # Return sorted vertices
# > [1, 3, 2, 4, 5, 7, 6, 8]
Where an edge
represents a dependency (e.g. Validators before Extractors), a Vertex
a plugin and Graph
their canvas in which they reside.
Here is the graph being built in ASCII.
___
 1 
___ # E.g. Selector

________
__ __
 2   3 
___ ___ # E.g. Validators
_________

__
 4 
___ # E.g. Validator with custom order

__
 5 
___

________
  
__ __ __
 6  7  8  # E.g. Extractors
_________
If you pay attention to the returned list of integers at the bottom of the implementation, you can see that the order makes sense. Here it is again.
# > [1, 3, 2, 4, 5, 7, 6, 8]
Like with the current method of sorting by order, the final order of plugins with the same value of order
is undefined. But even here there are alternatives of various algorithms.
Examples from Wikipedia on Topological Sorting
 visual lefttoright, toptobottom
 smallestnumbered available vertex first
 fewest edges first
 largestnumbered available vertex first
 attempting toptobottom, lefttoright
 arbitrary
Each with itâ€™s own pros/cons.
UI/UX
With this in mind, from what I can tell, the difficult part then is how to draw it.
First off, graph drawing in itself is a vast topic. As can be seen by the shear number and size of available books. (Just Google â€śgraph drawingâ€ť). The main focus of these is on the layout of a graph. I.e. finding an aesthetically pleasing configuration in which to put one node next to another such that it makes sense to a human being.
Once weâ€™ve got the layout all figured out, the next task is then a choice of colors and shapes. Which of course is highly subjective, but weâ€™ve got some good references out there in our daily lives, along with this collection of all visual programming languages out there.
Once thatâ€™s done, the next step is interactivity. How does one interact with these nodes? Also here weâ€™ve got good reference and intuition since itâ€™s part of our daily lives.
The final and possibly easiest step is then to map the visual portion of a graph into something we can feed into an algorithm like Topological Sort. As each Vertex can be anything, including a PyQt QWidget, this should be as easy as just giving each an instance variable id
that the user adds to another QWidget by dragging from one to the other.