Simulating a Graph Computer ---------- - ----- -------- Preface: ------- When the Connection Machine was first proposed, one of the things it was supposed to be able to do was search labeled graphs for specific subgraphs. This is in theory the basic problem of searching structured data, and so should be useful for searching AI knowledge bases and other data bases. For example, information about everyone's ancestors might be expressed by a huge labeled graph, of which a tiny part might be: name + ----------> PHIL |\ | \ age | ---------> 25 | | child | v name + ----------> SALLY \ \ age ---------> 2 Here the graph nodes may have labels, e.g. `PHIL', `25', `SALLY', and `2'; and the arcs are directed arrows which may also have labels, e.g. `name', `age', and `child'. One might search such a graph for all children named `Sally' that are age `2' and have a parent of age `25', just for example. This amounts to searching for all subgraphs of the form: + |\ | \ age | ---------> 25 | | child | v name + ----------> Sally \ \ age ---------> 2 Part of such a search might be to mark all nodes labeled `Sally'; and then mark all nodes that are sources of a `name' arrow ending in a marked node. To do this sort of thing we define a `graph computer'. Problem ------- You are being asked to simulate a graph computer, which we define here. The graph computer stores labeled graphs of up to 50 nodes. Each node can be given a label, which is a single capital letter. Several nodes can be given the same label, and no node has to be given a label. At most one arrow can exist between any two nodes. If an arrow exists, it MUST be given a label, which is a lower case letter. An arrow can connect a node to itself, but there can be at most one such self-connect- ing arrow for each node. Each node in the graph computer has up to 10 boolean flags that are named by decimal digits, starting with `0'. The graph computer reads its standard input and executes commands in it. These commands constitute the input to the program. Some of these commands cause output to be printed. Input ----- The syntax and meaning of each command is described below. Each command is on a single line by itself. Spaces must be used to separate the parts of a command, unless specified otherwise. Spaces may be used to indent the command on its line. No line will be longer than 80 characters. Blank lines and lines whose first non-space character is `#' are to be ignored as comments. Assume there are NO syntax errors in the input: you NEED NOT check for syntax errors. clearall The graph computer is reset to its initial state, with all nodes unlabeled, no arrows, and all flags false. The number of nodes is set to , an unsigned integer from 0 through 50. The number of flags is set to , an unsigned integer from 0 through 10. labels { }* The word `labels' is followed by any number of pairs, where the node number is an unsigned integer and the node label is an uppercase letter. For each pair, the node with the given number is given the node label, where pairs are processed from left to right. Previous node labels may be overwritten. E.g `5A' gives label `A' to node 5. There can be no spaces between a and its . arrows { }* The word `arrows' is followed by any number of triples, where each node number is an unsigned integer, and each arrow label is a lowercase letter. For each triple, the arrow with the given label is added to the graph with source being the node with the left node number, and destination the node with the right node number. The triples are processed from left to right. Previous arrow labels may be overwritten. E.g. `1b3' gives the arrow label `b' to the arrow from node 1 to node 3. There can be no spaces surrounding an . print The status of the flags and node labels is printed. See the output section below. printall Does the same as `print' and then prints the arrow label matrix. See the output section below. In the following commands, some subset of nodes has been previously selected. The default case is that ALL nodes are previously selected. Thus set 5 sets flag 5 to true in all selected nodes. The command sequence if 3 set 5 issued when all nodes are selected, will first select all nodes with flag 3 true, and then set flag 5 in all selected nodes. The `set' command ends by making all nodes selected: the default case. if Selects all previously selected nodes whose designated flag is true. is a single decimal digit. if ! Selects all previously selected nodes whose designated flag is false. is a single decimal digit. if Selects all previously selected nodes whose node label equals the given label. is a single uppercase letter. if ! Selects all previously selected nodes whose node label does NOT equal the given label, or which do not have a node label. is a single uppercase letter. set Set the designated flag true in all previously selected nodes. Then make ALL nodes selected. is a single decimal digit. clear Set the designated flag false in all previously selected nodes. Then make ALL nodes selected. is a single decimal digit. forward (1) Sends a signal along each arrow with the designated label that has as its source a prev- iously selected node with the designated flag true. (2) Clears the flag (sets it to false) in all selected nodes. (3) Makes all nodes selected. (4) Sets the designated flag in all nodes (regardless of previous selection) that are destinations of arrows along which signals were sent. is a single decimal digit, and is a single lowercase letter. may also be a `*', in which case any existing arrow is considered to have the designated arrow label. backward (1) Sends a signal along each arrow with the designated label that has as its destination a previously selected node with the designated flag true. The signal goes intuitively from destination to source, and therefore goes in the opposite direction of the arrow. (2) Clears the flag (sets it to false) in all selected nodes. (3) Makes all nodes selected. (4) Sets the designated flag in all nodes (regardless of previous selection) that are sources of arrows along which signals were sent. is a single decimal digit, and is a single lowercase letter. may also be a `*', in which case any existing arrow is considered to have the designated arrow label. This is the same as `forward' would be if the direction of each arrow were reversed. Output ------ As each line is input, it is to be printed to the output. This includes blank and comment ('#') lines. Only two commands, `print' and `printall', output anything more. Output of the `print' command: An example `print' output is: .......... [Flag 3 line] .2........ [Flag 2 line] ...11..... [Flag 1 line] .......... [Flag 0 line] ABCDE..B.. [Node label line] If there are F flags and N nodes, the printout takes F+1 lines of N+2 columns. The first F lines hold flag values, the last line holds node labels. The first flag line is for the highest numbered flag, flag 3 in the example where F = 4. The last flag line is for flag 0. The first 2 columns of every line are blank; the last N columns correspond to nodes in order of increasing node number. The node label line holds in the column corresponding to each node the label of the node, or a `.' if the node has no label. In the above example, node 0 has label `A'; node 1, label B; node 2, label C; node 3, label D; node 4, label E; nodes 5 and 6 have no labels; node 7 has label `B'; and nodes 8 and 9 have no labels. In the line corresponding to flag f and the column corresponding to node i, the decimal digit naming the flag appears if flag f of node i is true, and the character `.' appears of that flag is false. Thus in the above example the only true flags in the graph computer are flag 2 for node 1 (with label B) and flag 1 for nodes 3 and 4 (with labels D and E). Output of the `printall' command: The `printall' command first prints what the `print' command prints, and then for an N node graph computer, prints N additional lines giving the arrow labels. An example `printall' output is: .......... [Flag 3 line] .2........ [Flag 2 line] ...11..... [Flag 1 line] .......... [Flag 0 line] ABCDE..B.. [Node label line] A .x..y..... [Source node 0] B ..x....... [Source node 1] C ...xx..... [Source node 2] D .......... [Source node 3] E .......... [Source node 4] . .......... [Source node 5] . .......... [Source node 6] B .......... [Source node 7] . .......... [Source node 8] . .......... [Source node 9] The extra N lines hold information about arrows sourced at different nodes. The first line is for node 0, the last for node N-1. Each of these lines begins with the node label of the node at which the arrows are sourced, or `.' if there is no label for that node. This is followed by a single space, and then N columns, one for each possible destination of an arrow. The column for destination node j in the line for source node i holds the label of any arrow from i to j, or the character `.' if there is no such arrow. In the above example there are arrows labeled x from nodes 0 to 1, 1 to 2, 2 to 3, and 2 to 4. There is also an arrow labeled y form node 0 to node 4. There are no other arrows in the graph. Example Input ------- ----- clearall 10 4 labels 0A 1B 2C 3D 4E 7B arrows 0x1 1x2 2x3 2x4 0y4 printall # Set flags 1 and 2 on B nodes. if B set 1 print if 1 set 2 print # Move flag 1 forward. forward 1 * print # Move flag 1 forward. forward 1 * print # Move flag 1 backward on y arrows. backward 1 y print # Move flag 1 forward. forward 1 * print # Set flag 3 = flag 1 and flag 2. if 1 if 2 set 3 print # Set flag 1 = flag 1 and flag 2. if ! 2 clear 1 print # Set flag 2 = flag 1 and flag 2. if ! 1 clear 2 print Example Output ------- ------ clearall 10 4 labels 0A 1B 2C 3D 4E 7B arrows 0x1 1x2 2x3 2x4 0y4 printall .......... .......... .......... .......... ABCDE..B.. A .x..y..... B ..x....... C ...xx..... D .......... E .......... . .......... . .......... B .......... . .......... . .......... # Set flags 1 and 2 on B nodes. if B set 1 print .......... .......... .1.....1.. .......... ABCDE..B.. if 1 set 2 print .......... .2.....2.. .1.....1.. .......... ABCDE..B.. # Move flag 1 forward. forward 1 * print .......... .2.....2.. ..1....... .......... ABCDE..B.. # Move flag 1 forward. forward 1 * print .......... .2.....2.. ...11..... .......... ABCDE..B.. # Move flag 1 backward on y arrows. backward 1 y print .......... .2.....2.. 1......... .......... ABCDE..B.. # Move flag 1 forward. forward 1 * print .......... .2.....2.. .1..1..... .......... ABCDE..B.. # Set flag 3 = flag 1 and flag 2. if 1 if 2 set 3 print .3........ .2.....2.. .1..1..... .......... ABCDE..B.. # Set flag 1 = flag 1 and flag 2. if ! 2 clear 1 print .3........ .2.....2.. .1........ .......... ABCDE..B.. # Set flag 2 = flag 1 and flag 2. if ! 1 clear 2 print .3........ .2........ .1........ .......... ABCDE..B.. File: gcomputer.txt Author: Bob Walton Date: Sat Aug 24 10:49:58 EDT 2002 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: hc3 $ $Date: 2002/08/24 15:31:09 $ $RCSfile: gcomputer.txt,v $ $Revision: 1.9 $