graph.spad line 1106 [edit on github]
Category of finite graphs, allows us to model graph theory
x+y computes sum of x and y, that is disjoint union of nodes with arrows from appropriate input
addArrow!(s, ar) adds an arrow ar to the graph s
addArrow!(s, nm, o1, o2) adds an arrow to the graph s, where: nm is the name of the arrow o1 is the start object o2 is the end object
addArrow!(s, nm, n1, n2) adds an arrow to the graph s, where: nm is the name of the arrow n1 is the index of the start object n2 is the index of the end object
addArrow!(s, nm, n1, n2, mp) adds an arrow to the graph s, where: nm is the name of the arrow n1 is the index of the start object n2 is the index of the end object mp is a map represented by this arrow
addObject!(s, n) adds object n to the graph s. Use this version if you don't intend to create diagrams and therefore don't care about x, y coordinates.
addObject!(s, n) adds object with coordinates n to the graph s.
adjacencyMatrix(s) returns an n by n matrix A, where n is the number of vertices in the graph. If there is an edge from a vertex x to a vertex y, then the element ax, y is 1 (or in general the number of xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.
arrowName(s, a, b) retrieves the name of arrow a->b if it does not exist then return "?"
index of all arrows leading to a given arrow
arrowsFromNode(s, a) gives list of all arrows leading to a given node
arrowsToArrow(s, a) returns index of all arrows leading from a given arrow
arrowsToNode(s, a) gives list of all arrows leading from a given node
createWidth(x) can be used by domains which extend graph to help in creating coordinates for objects in a graph
createX(x, n) can be used by domains which extend graph to help in creating the x coordinate for objects in a graph
createY(x, n) can be used by domains which extend graph to help in creating the y coordinate for objects in a graph
cycleClosed(objs, arrowName) constructs a graph with vertices (from objs) connected in a cycle. arrowName is a prefix for all arrow names, this will be followed by a number starting at 1 and incremented for each arrow
cycleOpen(objs, arrowName) constructs a graph with vertices (from objs) connected in a cycle but with one gap. The last vertex in the sequence loops back to itself so all vertices have one outgoing arrow. arrowName is a prefix for all arrow names, this will be followed by a number starting at 1 and incremented for each arrow
diagramHeight(s) returns the height of the diagram that will be generated by diagramSvg. This is the maximum posY of all vertices in graph s
diagramSvg(fileName, n, dispArrowName) creates an SVG diagram fileName: String is the name of the SVG file that will be created n: % is the graph that will be written dispArrowName: Boolean is true to include the name of each arrow
diagramWidth(s) returns the width of the diagram that will be generated by diagramSvg. This is the maximum posX of all vertices in graph s
creates SVG diagram containing multiple graphs fileName: String is the name of the SVG file that will be created ln: List % is list of graphs that will be written dispArrowName: Boolean is true to include the name of each arrow
distance(s, a, b) gives the shortest distance between nodes 'a' and 'b' as a number of hops. 0 if 'a' = 'b', -1 if it is not possible to go from 'a' to 'b'
distanceMatrix(s) gives matrix of distances between vertices. Element a_i, j is the distance from i to j. Distance matrices are related to adjacency matrices, with the differences that: a. the latter only provides the information which vertices are connected but does not tell about costs or distances between the vertices b. adjacency matrix only tells us about directly connected vertices while distance matrix also considers indirect connections.
flatten(n) takes a second order graph, that is a graph whose elements are themselves graphs and create a first order graph whose vertices are the vertices of the inner graphs.
getArrowIndex(s, a, b) retrieves arrow index of the arrow form a to b
getArrows(s) returns a list of all the arrows (or edges)
getVertexIndex(s, o) gives index of object o. returns 0 if not found
getVertices(s) returns a list of all the vertices (or objects) of the graph s.
inDegree(s, a) gives the number of arrows leading in to node 'a' in graph 's'
incidenceMatrix(s) represents graph s by a matrix of size |V| by |E| where: V=number of vertices E=number of edges entry [vertex, arrow] = arrow endpoint data (undirected case case: 1 - incident, 0 - not incident, directed case: -1 - start, 1 - end, 0 - not incident).
initial constructs a graph without vertices or edges
isAcyclic?(s) returns true if there are no loops
isDirectSuccessor?(s, a, b) is true if 'b' is a direct successor of 'a' that is, if there is a direct arrow from 'a' to 'b'
isDirected?() is true iff % is domain consisting of directed graphs, false for undirected graphs.
isFixPoint?(s, a) is true if 'a' has an arrow to itself
isFunctional?(s) returns true if s is a functional graph, that is a directed graph in which each vertex has a single outgoing arrow.
isGreaterThan?(s, a, b) is true if we can get from vertex 'a' to 'b' through a sequence of arrows but we can't go in the opposite direction from 'b' to 'a'
kgraph(objs, arrowName) constructs a graph with vertices (from objs) and fully connected arrows, that is, each object has an arrow to every other object except itself. arrowName is a prefix for all arrow names, this will be followed by a number starting at 1 and incremented for each arrow
laplacianMatrix(s) returns matrix also known as "Kirchhoff matrix" or "Admittance matrix" where: entry [i, j] = inDegree(vi) if i = j (number of incoming links) -1 if i not = j and vi is adjacent to vj 0 otherwise Alternatively this is defined as D - A, where D is the diagonal degree matrix. It contains both adjacency information and degree information. There are other, similar matrices, that are also called "Laplacian matrices" of a graph.
loopsArrows(s) returns a list of loops for this graph in this case the loop is represented by the indexes of the sequence of nodes passed through. to-do: it would be better to use a more efficient algorithm, currently the code calls spanningForestArrow and traverses the result for loops, it might be more efficient to use Floyds algorithm.
loopsAtNode(s, a) returns a list of loops for this graph that pass through vertex index 'a'
loopsNodes(s) returns a list of loops for this graph in this case the loop is represented by the indexes of the sequence of nodes passed through.
looseEquals(x, y) is true if x 'equals' y this is a looser version of equality test but is not as general as isomorphism. it only requires the same number of vertices but does not require the objects themselves being equal. the arrows must be the same, that is it may return false if the order of vertices is changed so this is not isomorphism test.
map(s, m, newOb, offsetX, offsetY) creates a new graph by mapping from this one newOb should contain the new list of vertices. m should contain a NNI value for each vertex, this is the new index into newOb. It is allowed that newOb may contain less objects than s (for surjective mapping) or more objects than s (for injective mapping)
mapContra(s, m, newOb, offsetX, offsetY) is similar to map function but reverses the directions of the arrows
max(s) returns index of the vertex which can be reached from all other vertices. Gives 0 if no such node exists or if it is not unique, if there is a loop for instance.
max(s, sub) returns index of the vertex which can be reached from a given subset of the vertices. Gives 0 if no such node exists or if it is not unique, if there is a loop for instance.
merge(a, b) returns sum : union (not necessarily disjoint) of nodes with arrows merged in from appropriate input, if arrow exists from both inputs then it will be duplicated.
min(s) returns index of the vertex which can reach to all other vertices. Gives 0 if no such node exists or if it is not unique, if there is a loop for instance.
min(s, sub) returns index of the vertex which can reach to a given subset of the vertices. Gives 0 if no such node exists or if it is not unique, if there is a loop for instance.
nodeFromArrow(s, a) returns index of all nodes with a direct arrow leading in to arrow 'a' in graph 's'
nodeFromNode(s, a) gives list of all nodes with a direct arrow leading in to node 'a' in graph 's'
nodeToArrow(s, a) returns index of all nodes with a direct arrow leading out of arrow 'a' in graph 's'
nodeToNode(s, a) gives list of all nodes with a direct arrow leading out of node 'a' in graph 's'
outDegree(s, a) gives the number of arrows leading out of node 'a' in graph 's'
routeArrows(s, a, b) gives the shortest route between nodes 'a' and 'b' as a sequence of arrow indexes. [] if 'a' = 'b' [0] if it is not possible to go from 'a' to 'b'
routeNodes(s, a, b) gives the shortest route between nodes 'a' and 'b' as a sequence of node indexes. [a] if 'a' = 'b' [] if it is not possible to go from 'a' to 'b'
spanningForestArrow(s) constructs a spanning tree for every arrow.
spanningForestNode(s) constructs a spanning tree for every vertex.
spanningTreeArrow(s, i) constructs a spanning tree for graph 's' rooted at the arrow indexed by 'i'. The tree will expand out from 'i' only stopping when reaching a arrow that has already been visited (that is: loop detected). Elements in the tree are Integer, a positive Integer represents a arrow and a negative Integer represents a repeated arrow. note: it is possible that nodes may be visited many times, only arrows must not be re-visited.
spanningTreeNode(s, i) constructs a spanning tree for graph 's' rooted at the node indexed by 'i'. The tree will expand out from 'i' only stopping when reaching a vertex that has already been visited (that is: loop detected). Elements in the tree are Integer, a positive Integer represents a vertex and a negative Integer represents a repeated vertex.
subdiagramSvg(sc, n, dispArrowName, deep) creates a branch of an SVG diagram diagram under an already existing scene node sc. n: % is the graph that will be written dispArrowName: Boolean is true to include the name of each arrow
terminal(a) constructs a graph over a with a single vertex and a single loop
unit(objs, arrowName) constructs a graph with vertices (from objs) and arrows from each object to itself. arrowName is a prefix for all arrow names, this will be followed by a number starting at 1 and incremented for each arrow