# FiniteGraph S¶

graph.spad line 1106 [edit on github]

S: SetCategory

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!: (%, 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) -> %
`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: % -> Matrix NonNegativeInteger
`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)`

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, 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: (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`

.

- 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