Quoting Tom Knight <tk@ai.mit.edu>:
I've been thinking a bit recently about representation and manipulation of graphical structure in computers, and specifically have a somewhat open ended question which some of you may have thought about. For matrix like operations, APL and Matlab provides a set of primitive ops (we can argue or not about how good they are...).
What are the similarly "primitive" operations needed to flexibly create, modify, search, or otherwise manipulate graph structures? How do things change between directed and undirected graphs?
[this mailer does funny things and my reply got wiped out. I'm trying again] Old LifeMail postings refer to the program G'PH, and cellular auntomata postings refer to L'ilG'ph in the NXLCAU programs; try looking at our web pages at the CIEA-IPN in Mexico City. Limitations on these efforts were evident when it came to the tenth generation de Bruijn diagram for Wolfram's Rule 110; the graph was too complex for human comprehension. Turning to desirable primitives, of course you need to be able to position nodes and links; the links should have arrows for digraphs, which should be the generic form for graphs, anyway. Sooner than later you will want to move the nodes and perhaps even the links. Supposing all this is done in a gui (graphical user interface} you will want to double-click or something in the neighborhood of one of these structures and then mouse-drag it. Placing and editing labels is certainly convenient; you will want to attach them to links and nodes, move them in synchrony, and make them visible or invisible at will. It will also not be long before you want to define groupings and move them as a unit; not only move them but dilate or shrink, cut or paste, and in general things that you might want to do with ordinary text in a conventional editor. Truly complex graphs need to be sectioned, hyperbolicized, scrolled and so on. You are practically talking about a data base here. As for the question of internal representation, of course the links and nodes are just a set of coordinates, perhaps with auxiliary parameters such as colors, thicknesses, radii of circles and so on. These are set initially either by a default structure, randomized, or more likely built up gradually, again by mouse-aided processes. So you will probably want a mechanism for reading and storing files. No sense always building everything from scratch. The essence of a graph is the set of linkages, which could be stored as a connection matrix in a large array. But that is very wasteful and will soon exhaust memory. If the graph is sparse, better to shorten the array by assigning the nodes to rows and using the columns to hold the number of links and their destinations. The sparse form comes in two varieties - in links or our links, but of course they could be combined. You need a dimension for the maximum number of links, but that may be much less than the total number of nodes. For fairly irregular graphs, a LISP-like data structure could be valuable. Having accounted for the external mechanics of representing and presenting the graph, there are desirable operations on the graph itself. This could call for a whole new data structure for each operation. For example the square of the connection matrix gives two- step paths, and so on. But do you want to create and store all of them? As useful an anything is the distance matrix, in which you record the shortest distance between any pair of nodes as you run through powers of the connection matrix.
From these matrices can be read off leaves, rootlets, ideals, connected components, and so on; not necesssarily without considerable labor. Isolating components, for example. Once isolated, the graph can pe partitioned, at considerable saving in resources and convenience.
G'PH evolved into a thesis at the CIEA, but I don't have the reference right handy, nor am I sure they have posted it in their archives. The other things aren't much documented except in program listings. - hvm ------------------------------------------------- Obtén tu correo en www.correo.unam.mx UNAMonos Comunicándonos