Coding Logical Graphs
My earliest experiments coding logical graphs as dynamic “pointer” data structures taught me that conceptual and computational efficiencies of a critical sort could be achieved by generalizing their abstract graphs from trees to the variety graph theorists know as cacti. The genesis of that generalization is a tale worth telling another time, but for now it’s best to jump right in and proceed by way of generic examples.
Figure 1 shows a typical example of a painted and rooted cactus.
Figure 2 shows a way to visualize the correspondence between cactus graphs and cactus strings, demonstrated on the cactus from Figure 1. By way of convenient terminology, the polygons of a cactus graph are called its lobes. An edge not part of a larger polygon is called a 2‑gon or a bi‑gon. A terminal bi‑gon is called a spike.
The correspondence between a cactus graph and a cactus string is obtained by an operation called traversing the graph in question.
- One traverses a cactus graph by beginning at the left hand side of the root node, reading off the list of paints one encounters at that point. Since the order of elements at any node is not significant, one may start the cactus string with that list of paints or save them for the end. We have done the latter in this case.
- One continues by climbing up the left hand side of the leftmost lobe, marking the ascent by means of a left parenthesis, traversing whatever cactus one happens to reach at the first node above the root, that done, proceeding from left to right along the top side of the lobe, marking each interlobal span by means of a comma, traversing each cactus in turn one meets along the way, on completing the last of them climbing down the right hand side of the lobe, marking the descent by means of a right parenthesis, and then traversing each cactus in turn, in left to right order, that is incident with the root node.
The string of letters, parentheses, and commas one obtains by this procedure is called the traversal string of the graph, in this case, a cactus string.
Resources
- Theme One Program • Overview
- Theme One Program • Exposition
- Theme One Program • User Guide
- Survey of Theme One Program
cc: FB | Theme One Program • Laws of Form • Mathstodon • Academia.edu
cc: Conceptual Graphs • Cybernetics • Structural Modeling • Systems Science
be the set of nodes in a graph 
and let 
be a set of identifiers. We often find ourselves in situations where we have to consider many different ways of associating the nodes of 
Various manners of associating nodes with identifiers have been given conventional names by different schools of graph theorists. I will give one way of describing a few of the most common patterns of association.
”.
The painting of nodes is indicated by drawing the paints of each node next to the node they paint. Observe that some nodes may be painted with an empty set of paints.
This may be interpreted as a predicate 
whose first argument place is occupied by a sentence 
and whose second argument place is occupied by a monadic predicate 
is related to every 
by the relation 
a true sentence 
holds.
and 
whose argument 
is a dyadic predicate. These three properties are expressed in symbols as follows:![\begin{array}{l} \mathrm{Ref}(R) \colon (x)R(x, x), \\[6pt] \mathrm{Sym}(R) \colon (x)(y)(R(x, y) \rightarrow R(y, x)), \\[6pt] \mathrm{Tr}(R) \colon (x)(y)(z)(R(x, y) \And R(y, z) \rightarrow R(x, z)). \end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bl%7D++%5Cmathrm%7BRef%7D%28R%29+%5Ccolon+%28x%29R%28x%2C+x%29%2C++%5C%5C%5B6pt%5D++%5Cmathrm%7BSym%7D%28R%29+%5Ccolon+%28x%29%28y%29%28R%28x%2C+y%29+%5Crightarrow+R%28y%2C+x%29%29%2C++%5C%5C%5B6pt%5D++%5Cmathrm%7BTr%7D%28R%29+%5Ccolon+%28x%29%28y%29%28z%29%28R%28x%2C+y%29+%5CAnd+R%28y%2C+z%29+%5Crightarrow+R%28x%2C+z%29%29.++%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0&c=20201002)
(
is identical with 
). The predicate 
on the other hand, possesses only the property of transitivity. Thus the formulas 
and 
are true sentences, whereas 
and 
are false.
Inquiry Into Inquiry 