Q-Graph 1.2
======= ===
This is Q-Graph, a graph library and editor for the Q programming language.
The package contains:
- graph.q: a graph data structure implemented as a kind of asymmetric
adjacency list dictionary, and a collection of the usual graph operations
- graphed.q: a full-featured graph editor, allows you to create and edit your
input graphs with ease (requires Tcl/Tk)
To run this software you'll need the Q programming system, available from:
http://www.musikwissenschaft.uni-mainz.de/~ag/q
DESCRIPTION
===========
"Graphs" are those nice combinatorial structures consisting of nodes and edges
connecting the nodes. They are interesting to fiddle with and also play a
major role in many important applications, such as network optimization. You
will find that a plethora of sophisticated graph algorithms is described in
the math and computer science literature -- you can find some ubiquitous ones
in almost any decent book on algorithms and data structures.
In this package, graphs are represented using a kind of asymmetric adjacency
list data structure implemented as an ordered dictionary which is both
efficient (for most purposes) and general. In particular, the data structure
gives you efficient access to the (outgoing) edges of each node, and it is
capable of representing multigraphs, i.e., graphs with multiple edges between
the same pair of nodes. Node and edge labels are also provided. Undirected
graphs are not directly supported, but can be realized as bidirected graphs in
the usual manner.
The definition of the data type and some useful operations on graphs can be
found in graph.q. The graphed.q script implements the graph editor, which
needs Tcl/Tk and BWidgets (available from www.tcl.tk). On Unix/Linux systems
the graphed script can also be invoked from the command line (`make install'
installs an appropriate symlink in your program directory).
NOTE: The graph.q module in this package is not related to, and doesn't even
work with, the simplistic graph.q example in the standard Q distribution, so
don't mix up these two.
Documentation still needs to be written. For the time being, please refer to
graph.q for a description of the data structure and its operations. The graph
editor should be pretty self-explanatory. A sample implementation of a
well-known shortest path algorithm can be found in the examples directory.
INSTALL
=======
Ready-to-install packages for Linux (rpm) and Windows (msi) are available from
the Q homepage.
To install from the sources, unpack graph-.tar.gz (you probably did
that already) and perform one of the following:
- Under Unix/Linux, run `configure --prefix=PREFIX; make install' as root,
where PREFIX is the installation prefix of the Q programming system (usually
/usr or /usr/local).
- Under Windows, simply copy graph.q, graphed.q and graphed.tcl in the src
subdirectory to the Qpad library directory (usually c:/progra~1/qpad/lib).
You might also wish to copy the stuff in the examples subdirectory to the
Qpad examples/graph directory, and this README file to README-Graph in the
Qpad etc directory.
To get paginated PostScript and PDF output in graphed, you'll also need
epssplit and ghostscript. If you do not have these, graphed can only create
output files in encapsulated PostScript format (EPSF). You should still be
able to print these with your favourite graphics program.
NOTES
=====
This is still BETA SOFTWARE. Please be so kind and report bugs to the author.
The graph editor is not quite finished yet, but all core functionality is
working. A plugin interface will be added in the next version. This will allow
you to run your graph algorithms inside the editor.
I've also witten a similar (albeit much more restricted) graph library and
editor for the HP-49G. If you're a proud owner of this latest and greatest HP
calculator you might wish to check it out on my homepage (see "HP49 Software"
in the "Free Software" section).
Enjoy! :)
April 2003
Albert Graef
ag@muwiinfa.geschichte.uni-mainz.de, Dr.Graef@t-online.de
http://www.musikwissenschaft.uni-mainz.de/~ag