I need help building a data structure for a state diagram

[Tim Chase]

> 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
> STARTED.
> 
>>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 
auto-increment)

   CREATE TABLE States (
    id INT PRIMARY KEY AUTOINCREMENT,
    description VARCHAR(50),
    other_attributes ...
   );

   CREATE TABLE Transitions (
    id INT PRIMARY KEY AUTOINCREMENT,
    from_state INT NOT NULL REFERENCES States(id),
    to_state INT NOT NULL REFERENCES States(id),
    other_attributes ...
   );
   INSERT INTO States (description) VALUES
    ('Started'),
    ('Finished'),
    ('Abandoned');
   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]

-tkc

[1]
http://en.wikipedia.org/wiki/Finite_state_machine