# FiniteGraph S¶

Category of finite graphs, allows us to model graph theory

+: (%, %) -> %
sum : disjoint union of nodes with arrows from appropriate input
=: (%, %) -> Boolean
from BasicType
~=: (%, %) -> Boolean
from BasicType
addArrow!: (%, Record(name: String, arrType: NonNegativeInteger, fromOb: NonNegativeInteger, toOb: NonNegativeInteger, xOffset: Integer, yOffset: Integer, map: List NonNegativeInteger)) -> %
addArrow!(s, ar) adds an arrow ar to the graph s
addArrow!: (%, String, NonNegativeInteger, NonNegativeInteger) -> %
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!: (%, String, NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> %
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
addArrow!: (%, String, S, 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
addObject!: (%, Record(value: S, posX: NonNegativeInteger, posY: NonNegativeInteger)) -> %
addObject!(s, n) adds object with coordinates n to the graph s.
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.
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: (%, NonNegativeInteger, NonNegativeInteger) -> String
arrowName(s, a, b) retrieves the name of arrow a->b if it does not exist then return "?"
arrowsFromArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
index of all arrows leading to a given arrow
arrowsFromNode: (%, NonNegativeInteger) -> List NonNegativeInteger
arrowsFromNode(s, a) gives list of all arrows leading to a given node
arrowsToArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
arrowsToArrow: (s: %, a: NNI) returns index of all arrows leading from a given arrow
arrowsToNode: (%, NonNegativeInteger) -> List NonNegativeInteger
arrowsToNode(s, a) gives list of all arrows leading from a given node
coerce: % -> OutputForm
from CoercibleTo OutputForm
createWidth: NonNegativeInteger -> NonNegativeInteger
createWidth(x) can be used by domains which extend graph to help in creating coordinates for objects in a graph
createX: (NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
createX(x, n) can be used by domains which extend graph to help in creating the x coordinate for objects in a graph
createY: (NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
createY(x, n) can be used by domains which extend graph to help in creating the y coordinate for objects in a graph
cycleClosed: (List S, String) -> %
cycleClosed: (objs: List S, arrowName: String) 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: (List S, String) -> %
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

deepDiagramSvg: (String, %, Boolean) -> Void

diagramHeight: % -> NonNegativeInteger
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
diagramsSvg: (String, List %, Boolean) -> Void
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
diagramSvg: (String, %, Boolean) -> Void
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: % -> NonNegativeInteger
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
distance: (%, NonNegativeInteger, NonNegativeInteger) -> Integer
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: % -> Matrix Integer
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: DirectedGraph % -> %
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: (%, NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
getArrowIndex(s, a, b) retrieves arrow index of the arrow form a to b
getArrows: % -> List Record(name: String, arrType: NonNegativeInteger, fromOb: NonNegativeInteger, toOb: NonNegativeInteger, xOffset: Integer, yOffset: Integer, map: List NonNegativeInteger)
getArrows(s) returns a list of all the arrows (or edges)
getVertexIndex: (%, S) -> NonNegativeInteger
getVertexIndex(s, o) gives index of object o. returns 0 if not found
getVertices: % -> List Record(value: S, posX: NonNegativeInteger, posY: NonNegativeInteger)
getVertices(s) returns a list of all the vertices (or objects) of the graph s.
hash: % -> SingleInteger
from SetCategory
hashUpdate!: (HashState, %) -> HashState
from SetCategory
incidenceMatrix: % -> Matrix Integer
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).
inDegree: (%, NonNegativeInteger) -> NonNegativeInteger
inDegree(s, a) gives the number of arrows leading in to node ‘a’ in graph 's'
initial: () -> %
initial constructs a graph without vertices or edges
isAcyclic?: % -> Boolean
isAcyclic?(s) returns true if there are no loops
isDirected?: () -> Boolean
isDirected? is true iff % is domain consisting of directed graphs, false for undirected graphs.
isDirectSuccessor?: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean
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'
isFixPoint?: (%, NonNegativeInteger) -> Boolean
isFixPoint?(s, a) is true if ‘a’ has an arrow to itself
isFunctional?: % -> Boolean
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?: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean
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: (List S, String) -> %
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: % -> Matrix Integer
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.
latex: % -> String
from SetCategory
loopsArrows: % -> List Loop
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: (%, NonNegativeInteger) -> List Loop
loopsAtNode(s, a) returns a list of loops for this graph that pass through vertex index ‘a’
loopsNodes: % -> List Loop
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: (%, %) -> Boolean
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: (%, List NonNegativeInteger, List S, Integer, Integer) -> %
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: (%, List NonNegativeInteger, List S, Integer, Integer) -> %
mapContra(s, m, newOb, offsetX, offsetY) is similar to map function but reverses the directions of the arrows
max: % -> NonNegativeInteger
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: (%, List NonNegativeInteger) -> NonNegativeInteger
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: (%, %) -> %
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: % -> NonNegativeInteger
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: (%, List NonNegativeInteger) -> NonNegativeInteger
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: (%, NonNegativeInteger) -> List NonNegativeInteger
nodeFromArrow(s, a) returns index of all nodes with a direct arrow leading in to arrow ‘a’ in graph 's'
nodeFromNode: (%, NonNegativeInteger) -> List NonNegativeInteger
nodeFromNode(s, a) gives list of all nodes with a direct arrow leading in to node ‘a’ in graph 's'
nodeToArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
nodeToArrow(s, a) returns index of all nodes with a direct arrow leading out of arrow ‘a’ in graph 's'
nodeToNode: (%, NonNegativeInteger) -> List NonNegativeInteger
nodeToNode(s, a) gives list of all nodes with a direct arrow leading out of node ‘a’ in graph 's'
outDegree: (%, NonNegativeInteger) -> NonNegativeInteger
outDegree(s, a) gives the number of arrows leading out of node ‘a’ in graph 's'
routeArrows: (%, NonNegativeInteger, NonNegativeInteger) -> List NonNegativeInteger
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: (%, NonNegativeInteger, NonNegativeInteger) -> List NonNegativeInteger
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: % -> List Tree Integer
spanningForestArrow(s) constructs a spanning tree for every arrow.
spanningForestNode: % -> List Tree Integer
spanningForestNode(s) constructs a spanning tree for every vertex.
spanningTreeArrow: (%, NonNegativeInteger) -> Tree Integer
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: (%, NonNegativeInteger) -> Tree Integer
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: (Scene SCartesian 2, %, Boolean, Boolean) -> Void
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: S -> %
terminal(a) constructs a graph over a with a single vertex and a single loop
unit: (List S, String) -> %
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

BasicType

SetCategory