FiniteGraph S

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

=: (%, %) -> 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) -> %

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

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

CoercibleTo OutputForm

SetCategory