Workflow-related issues are probably the most challenging aspect of EHR implementation.   First, there is the tedious job of mapping existing practice workflows, followed by figuring out acceptable adaptations to the EHR product’s implicit workflows.    The larger the organization, the longer it takes, and the more people it requires to complete the analysis.   Get it wrong, and there will be productivity misery.

EHR products with integrated workflow engines offer a reasonable approach to dealing with human-software workflow mapping.  Because workflow engines make software workflows explicit and manipulable, they make it easier to harmonize software workflows with human activities.  However, this still leaves the challenges involved in capturing, defining, and studying human workflows in a manner that is easily understood by humans and computers.  Enter graph theory, stage right.

Graph theory is a branch of discrete mathematics that began with famed mathematician Leonhard Euler and the Königsberg bridge problem.    Königsberg consisted of four land masses connected by  seven  bridges.  He attempted to determine if it was possible to tour the city and visit every bridge once, and only once.  Euler proved mathematically that such a tour was impossible, and in the process, inaugurated graph theory.

Image by Bogdan Giusca, from Seven Bridges of Königsberg, Wikipedia.

Euler’s imagined walk around Königsberg entails a series of events consisting of bridge-crossings and visits to sections of the city.   Using proper terminology, each city section is referred to as a vertex and each bridge as an edge.  A graph consists of an alternating sequence of vertices and edges.   Below is an image of a graph with 11 edges and 7 vertices.    This is an undirected graph.

Undirected Graph

Relationships between vertices and edges may be represented using edge-endpoint functions.  From the graph above, we can obtain e1 {v1, v2} as an edge-endpoint function relating edge e1 to vertices v1 and v2.  In undirected graphs, the order of the vertex pairs is not important.

When using graphs to model processes, directed graphs (referred to as digraphs) are used.   In digraphs, the order of vertex pairs in edge-endpoint functions is important because the order indicates how movement occurs within the graph.  For example, one possible path from v1 to v6 is

(e2 {v1, v3}, e4 {v3, v4}, e6 {v4, v6}).

Path in graph theory has a specific meaning.  A path is a walk from the starting vertex to the ending vertex in which each vertex and edge is traversed only once.   Using a digraph, any process can be represented both graphically and as an ordered set of edge-endpoint functions.   This is great for specifying workflow algorithms because people understand the graphical representation and computers the mathematical representation.

Consider for a moment the expressive power of edge-endpoint functions.  In the famous traveling salesman problem, the goal is to find the shortest possible route that includes visits to a set of cities where each city is visited only once.  Here, edges represent miles and vertices cities.  In a clinical application, an edge could represent a procedure, the initial vertex a patient who hasn’t undergone the procedure, and the final vertex the patient after the procedure has been completed.

Graph theory has not been overlooked as a workflow-modeling tool.  Petri nets, which introduced me to graph theory, are directed graphs with special extensions that make them useful for workflow analysis.    (Those interested in Petri nets may wish to read Workflow Management: Models, Methods, and Systems by van der Aalst and  van Hee).

In all, my work with graph theory over the past year has proven to be very fruitful in helping me to address some of those leftover algorithm issues I mentioned in my first post, “Why Another EHR Blog?” In fact, this is such a great tool that I recommend it to all clinical workflow modelers.




  1. Thanks for the links. My interest in YAWL and BP grew out of an interest in EHR design, of which workflow is a both significant component and challenge. Current EHR designs retain too much paper-based thinking– they are “faster horses.” A completely new metaphor is required; not only for processes, but also for data capture, data representation, and interoperability. I have been working on an extension to Petri nets along with a new data representation format that I hope will allow for a radical change in EHR design. Time will tell…

    I looked at a few of your tweets. Interesting…

  2. Chuck, thanks for stopping by and adding EHR Science to your blog roll. Having read a few of your papers, I must give you props for advocating workflow systems for EHRs before they became fashionable discussion topics in the HIT community.

    Dr. van der Aalst is great. I have corresponded with him a couple of times and he has always been very gracious and helpful. Modeling Business Processes: A Petri Net-Oriented Approach, his latest book, is quite good as an introduction to workflow modeling, possibly even better as a textbook, than Workflow Management-Models, Methods, and Systems, which is absolutely wonderful.

    My education on this topic, which is very much ongoing, began with the latter book. Thus far, it has been an interesting and productive journey.

    Have you experimented with YAWL?


Leave a Reply

Your email address will not be published. Required fields are marked *