[sf-perl] Practical theory: graphs

Rich Morin rdm at cfcl.com
Fri Dec 16 22:36:34 PST 2005


As you note, the size of a graph representing the typical voice
maze is pretty small (though it may not seem small to the user),
so performance is not likely to be an issue.  Thus, the critical
questions are whether the graph representation you select is easy
to work with and flexible enough to support any required actions.


I like edge lists, because they are a very general representation,
but they may be overkill for this problem.  That said, some graph
libraries (e.g., Boost Graph Library, Ruby Graph Library) support
a variety of representations "under the covers".

Just as Object-Relational Mapping maps objects to database tables,
BGL and RGL map objects to graph nodes.  If you decide to roll your
own graph code, it might be interesting to look into this approach.

Unfortunately, Googling [BGL Perl] doesn't come up with anything
very promising, so I suspect that you might be required to link
to the Boost (C++) or Ruby library or translate one of them into
Perl.  I'd suggest starting with Ruby for any translation, as it
won't have all the baggage that the C++ version does.  However,
be warned that it is Alpha code and the developer is German:

  http://rubyforge.org/projects/rgl


Getting back to your problem description, it sounds like the log
doesn't really care about the graph at all.  It merely needs to
know which nodes got visited in what order.  That is, a simple
list of node names would suit your purpose.  However, the code
that migrates nodes up to the "front" of the graph might need to
pay attention to the graph structure.


The notion of automagically migrating nodes is intriguing, but I
worry that resulting menus may not fit any reasonable model that
the user might have.  Also, messages which work well in one menu
may not have sufficient context to be understandable in another.


Finally, I wonder whether it might not make sense to assume that
the person managing the menus is not a programmer at all.  If so,
you might want to consider using a GUI-based interface, based on
dot, dia, SVG, or ???.  Your code could present the current graph
(something like a state-transition diagram) and offer the manager
the ability to select from suggested re-connections, define new
connections, etc.

-r
-- 
email: rdm at cfcl.com; phone: +1 650-873-7841
http://www.cfcl.com        - Canta Forda Computer Laboratory
http://www.cfcl.com/Meta   - The FreeBSD Browser, Meta Project, etc.


More information about the SanFrancisco-pm mailing list