I need help building a data structure for a state diagram

Tim Chase python.list at tim.thechases.com
Sun May 24 15:20:04 EDT 2009

> I'm working on a really simple workflow for my bug tracker.  I want
> filed bugs to start in an UNSTARTED status.  From there, they can go to
>>From STARTED, bugs can go to FINISHED or ABANDONED.
> I know I can easily hard-code this stuff into some if-clauses, but I
> expect to need to add a lot more statuses over time and a lot more
> relationships.
> This seems like a crude state diagram.  So, has anyone on this list done
> similar work?

I've got a similar workflow in one of my applications at work.  I 
use a database to persist the available states along with their 
transitions.  Both the states themselves and the transitions have 
various attributes to them to facilitate my workflows.  The 
following schema should work in most databases such as sqlite 
(included with Python2.5+) with minor syntactic tweaks (such as 

   CREATE TABLE States (
    description VARCHAR(50),
    other_attributes ...

   CREATE TABLE Transitions (
    from_state INT NOT NULL REFERENCES States(id),
    to_state INT NOT NULL REFERENCES States(id),
    other_attributes ...
   INSERT INTO States (description) VALUES
   INSERT INTO Transitions (from_state, to_state) VALUES
    (1, 2), -- Started -> Finished
    (1, 3), -- Started -> Abandoned
    (3, 2);  -- Abandoned -> Finished

You can then query states you can transition to:

   SELECT s1.description, s2.description, t.other_attributes
   FROM Transitions t
   INNER JOIN States s1
   ON s1.id = t.from_id
   INNER JOIN States s2
   ON s2.id = t.to_id
   -- WHERE t.from_id = @current_id
   ORDER BY s1.description, s2.description

You can easily add more state rows as well as transition rows to 
the tables.  Then use the other_attributes of either the 
transition or the state to control the workflows (we have 
transition attributes for things like "notifies account-manager", 
"notifies customer", "number of days that must pass from initial 
workflow-start", "number of days that must pass from most recent 
status change", "does this transition happen manually or 
automatically via an overnight script", etc.)  The workflow 
processing code then looks at these attributes for the transition 
that's being attempted, and behaves accordingly.

Hope this gives you some ideas.  If you want to read more, the 
magic google-words are "finite state automaton" (FSA) or "finite 
state machine" (FSM)[1]



More information about the Python-list mailing list