notes-computer-jasper-graphTechnicalNotes

Technical notes on Jasper "graphs"

What we call "graphs" in Jasper is a type of value which are what is called in some parts of computer science a "labeled multidigraph with unique node labels and a distinguished node", and where the node and edge labels are arbitrary Jasper values, and some nodes without outgoing edges are arbitrary Jasper values.

To non-CS people, a graph (of either sort) might be called a "network". A graph in Jasper is something that you might draw by drawing a bunch of circles and then drawing some arrows between some of the circles, and then attaching names to some of the circles, and attaching notes to some of the arrows (some arrows might have more than one note). We call the circles "nodes", the arrows "edges", the circle names "node labels", and the notes on the arrows "edge labels".

Formally, (following http://en.wikipedia.org/wiki/Pseudograph) a Jasper __graph__ is an 9-tuple G=(node labels, edge labels, interior nodes, value nodes, edges, s, t, L_n, L_e) where

In other words, a Jasper graph consists a set of interior nodes, which may have names, a set of value nodes, and a set of labeled edges. Value nodes, node names and edge labels may be arbitrary Jasper values. Interior nodes may or may not have a node name; a node name is an arbitary Jasper value that corresponds to exactly one node. A node is either an interior node, or "value node", which is just an arbitrary Jasper value. are any value besides interior nodes. __Edges__ are things that each have a __source__, which is an interior node, and a __destination__, which is an arbitrary node, and one or more __edge labels__, which are arbitary values. One of the nodes is named "root".

A node is reachable from another node if you can start from the one node and get to the other by following intervening edges from source to destination.

A node is connected to another node if you can start from one node and find a sequence of edges such that the first edge's source or target is the one node, and the last edge's source or target is the other node, and each edge's source is either the source or the target of the previous edge. A graph is connected if any pair of nodes is connected. Basically, a graph is connected if you can reach any node from any other node by following the edges, if you're allowed to follow them "backwards". If you draw a graph on paper, it's connected if you can't find any proper subset of nodes such that you can draw a circle around those nodes without intersecting any of the edges.

A Jasper G-constructor can't create any graph value, only some of them, namely (i think) those in which each node is reachable from the "root" node. The values that a single G-constructor can create are kind of like S-expressions in Lisp, except that in addition there is a facility to create cycles.

(I think that) a series of G-constructors, where later constructors make use of values created in earlier G-constructors, can create any connected graph value. By also using a function that merges graphs, (i believe that) any graph value can be created.