Mathematics and Clinical Concepts, Part VII: Graphs, Processes, and Workflows

by Jerome Carter on December 2, 2013 · 2 comments

Clinical care consists of processes.  Examining patients, prescribing medications, mailing bills, reviewing charts–they are all processes.   Fortunately, there exists a perfectly good way of describing processes mathematically using graphs.  Graph theory originated when Leonhard Euler attempted to solve a simple problem mathematically.  The town of Konigsberg, where he lived, had four land areas that were connected by seven bridges.  Euler set out to determine if it was possible to visit each land area while crossing each bridge only once.  His solution gave rise to graph theory (see Workflow Analysis–Doing the Math).

Basic graph concepts are simple.  A graph is made up of points (vertices) and lines that connect those points (edges).    Graphs can be defined in terms of sets.  Here is the definition of a graph from Epp (1).

A graph G consists of two finite sets: a non-empty set V(G) of vertices and a set of E(G) edges, where each edge is associated with a set of one or two vertices called its endpoints.  The correspondence from edges to endpoints is called the edge-endpoint function…

basic undirected graph

Figure 1 – A basic graph 

Since we are interested in processes, which by necessity require that steps occur in a specific sequence, I will limit the discussion in this post to directed graphs.   In directed graphs, movement through the graph follows along specific pathways.  This makes for an important difference between directed and undirected graphs.   In undirected graphs, like Figure 1, endpoints are sets (e.g., {A, E}), whereas in directed graphs endpoints are ordered pairs that indicate the direction of movement, (e.g., (A, E)).   Figure 2 illustrates a directed graph; arrows indicate the direction of movement.

basic Directed  graph

Figure 2 – A directed graph

Graphs are everywhere
Starting with the very simple concepts of vertices and edges, one can represent an amazing array of concepts with graphs: taxonomies, ontologies, family relationships, sentence structures, organizational charts, etc.

Figure 3 – A taxonomy of animals

Computational support for graphs is extensive in terms of both algorithms and data structures.   There are even databases (e.g., Neo4j, HyperGraphDB) designed specifically to support data that are most naturally represented as a graph.

The value of using graphs to represent clinical concepts arises from: 1) the ease with which the two are married, and 2) the existence of an extensive body of mathematical and computational tools that support their understanding and use.

Processes and graphs
Graphs offer a great deal of expressive power because they are so flexible.   Consider how many ways one could interpret this very simple graph segment.

AB Seg

A and B could represent any of the following steps: waiting  –> registration, viewing a formulary –>selecting a drug, or the progress of an illness from Stage A –>Stage B.  Using graphs simply requires that one select the concepts to be represented and the level of detail desired between steps.

Drawing a detailed process diagram by starting with a plain directed graph could require a lot of work.  Fortunately, there has been a huge amount of work done over the last 50 years in adapting graph theory to processes.  Those who have been following the blog know that I am referring to Petri nets (Figure 4).

Basic Petri nets (referred to as low-level or place/transition nets) have a built-in ability to represent states, locations, and movements or transitions between those states and locations (see the series Petri Nets in Clinical Workflow Modeling).  In addition, they provide simulation features that allow one to verify workflow assumptions in a way that swim-lanes or flow charts cannot match.


Figure 4A Petri net example

Colored Petri nets are an extension of basic Petri nets that support time, data values, data types, functions, and other programming language constructs.  Colored Petri nets are a Turing-complete programming language, and as a result, we have a graphical modeling language that can be used to model processes of arbitrary complexity.   As someone who writes software, this is simply extraordinary.  A well-designed colored Petri net is a model, an algorithm, and a program. Wow!

Obviously, I love Petri nets, but not just for their modeling capabilities. They also offer a mathematical understanding of processes to an extent I have not seen in other modeling tools.   Because they are based on graph theory, Petri nets can be represented mathematically.  Here is the definition of a Petri net taken from van der Aalst and Stahl (2).

A Petri net is a triple (P, T, F) where:

1) P is a finite set of places

2) T is a finite of transitions

3)  and

PN Def   is a flow relation.

Consequently, there is a one-to-one correspondence between the graphical representation of a Petri net and the triple (P, T, F).

Here, places are analogous to vertices and transitions to edges.    Notice that the flow relation (movement through the net) is a relation consisting of a subset of ordered pairs of the Cartesian product of places and transitions.   An ordered pair of the type (P, T) indicates a move from a place (vertex) to a transition (edge), while (T, P) indicates the move is from a transition (edge) to a place (vertex).   Since Petri net flows are relations, they can be manipulated using the mathematical operations appropriate for relations.

Series summary
In this series, we have looked at modeling truth with predicate logic (P (x) –> Q(x)), modeling EHR data with relations, tying specific inputs to specific outputs with functions and, finally, representing processes and relationships with graphs.   Sets, relations, functions, graphs and logic are clearly powerful tools for describing real-world entities and phenomena.  And, obviously, they can be used to represent clinical concepts.   Taking the next step–using these concepts to create a theory of clinical systems–strikes me as both reasonable and doable.

I’ll keep you posted…

  1. Epp SS. Discrete Mathematics with Application, Fourth Edition. Belmont, CA: Thomson-Brooks/Cole; 2010
  2. van der  Aalst W, van Hee K. Workflow Management: Models, Methods, and Systems.  Cambridge, MA: The MIT Press; 2004

Leave a Comment

{ 2 comments… read them below or add one }

Ramayya April 8, 2015 at 4:25 PM

Healthcare systems are Socio-Technical Systems and not pure Business Systems as the current Economic Theories expect them to be. Hence, all the current Economy/Business-based approaches to developing EHR Systems will always kill the Quality that is paramount in Health Care.

Further, healthcare has multiple facets- Quality, Regulations, new Knowledge that impacts the healthcare delivery, the location of the healthcare services, the locations and conditions of the healthcare receivers, etc.

Healthcare is not a business, just like flying a commercial airplane full of people or conducting war.

May I therefore suggest that Concept Map of Healthcare Landscape first developed before architecting a EMR/EHR System.

The following website is a mother load of Concept Map Information and also has a FREE Tool to develop Concept Maps–


Jerome Carter April 9, 2015 at 2:42 PM

Ramayya, thanks for your comment. Concept maps are one possible approach to EHR design. I am for adding structure to the design process, especially if that structure is mathematical. Since concepts maps are graphs, they certainly count. Thanks for the link!


Previous post:

Next post: