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