Graphs, in addition to being interesting structures in their own right, have importance in representing data structures, finite automata, communication networks and so on.

This is mostly an implementation of directed graphs (undirected graphs can be implemented by having arrows in both directions or by using Undirected Graph).

A graph has two parts:

- A set of 'vertices' or 'objects'.
- A set of 'arrows' or 'edges'

### Installation

To install this code goto github (https://github.com/martinbaker/multivector/blob/master/graph.spad) and download the file:

graph.spad

Then compile them:

(1) -> )boot $bootStrapMode := true (1) -> )co graph.spad (1) -> )boot $bootStrapMode := false (1) -> )co graph.spad |

As you can see above it is compiled twice, once in 'boot strap mode' and again without. This is because of circular definitions in the code.

### Tutorial

If Graph and directedGraph are not already loaded then load them as follows:

(1) -> )library LOOP Loop is now explicitly exposed in frame frame1 Loop will be automatically loaded when needed from /home/martin/LOOP.NRLIB/LOOP (1) -> )library FGRPH Graph is now explicitly exposed in frame frame1 Graph will be automatically loaded when needed from /home/martin/FGRPH.NRLIB/GRPH (1) -> )library FGRPH- Graph& is now explicitly exposed in frame frame1 Graph& will be automatically loaded when needed from /home/martin/FGRPH-.NRLIB/GRPH- (1) -> )library DGRPH DirectedGraph is now explicitly exposed in frame frame1 DirectedGraph will be automatically loaded when needed from /home/martin/DGRPH.NRLIB/DGRPH (1) -> )library FNGRPH FunctionGraph is now explicitly exposed in frame frame1 FunctionGraph will be automatically loaded when needed from /home/martin/FGRPH.NRLIB/FGRPH (1) -> )library UDGRPH UndirectedGraph is now explicitly exposed in frame frame1 UndirectedGraph will be automatically loaded when needed from /home/martin/UDGRPH.NRLIB/UDGRPH (1) -> )library MFGRPH MultifunctionGraph is now explicitly exposed in frame frame1 MultifunctionGraph will be automatically loaded when needed from /home/martin/MFGRPH.NRLIB/MFGRPH (1) -> )library WGRPH WeightedGraph is now explicitly exposed in frame frame1 WeightedGraph will be automatically loaded when needed from /home/martin/WGRPH.NRLIB/WGRPH |

This graph framework has many methods to create graph instances, click on the following links for details:

- Constructing graphs by building up individual objects and arrows.
- Constructing from adjacency matrix.
- Constructing standard types.
- Combining existing graphs using sum and product.
- Mapping from an existing graph.
- Constructing from permutation

We now have a graph and we can check out various things about it by calling functions such as those listed below. Click on these function names for more information:

- Matrix representations:
- about whole graph:
- about specific nodes
- arrowName -- the name of arrow a->b
- inDegree -- the number of arrows leading in to node 'a' in graph 's'
- outDegree -- the number of arrows leading out of node 'a' in graph 's'
- nodeFromNode -- index of all nodes with a direct arrow leading in to node 'a' in graph 's'
- nodeToNode -- index of all nodes with a direct arrow leading out of node 'a' in graph 's'
- arrowsFromNode -- index of all arrows leading to a given node
- arrowsToNode -- index of all arrows leading from a given node
- nodeFromArrow -- index of all nodes with a direct arrow leading in to arrow 'a' in graph 's'
- nodeToArrow -- index of all nodes with a direct arrow leading out of arrow 'a' in graph 's'
- arrowsFromArrow -- index of all arrows leading to a given arrow
- arrowsToArrow -- index of all arrows leading from a given arrow
- min and max can be over whole graph or over a subset of nodes

Now lets explore the methods for combining the graphs, these include:

- "+" (Sum) : disjoint union of nodes with arrows from appropriate input
- merge:(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.
- "*" : Tensor product : the tensor product G*H of graphs G and H is a graph such that the vertex set of G*H is the Cartesian product V(G) × V(H); and any two vertices (u,u') and (v,v') are adjacent in G × H if and only if u' is adjacent with v' and u is adjacent with v.
- cartesian: Cartesian product: the vertex set of G o H is the Cartesian product V(G) × V(H) and any two vertices (u,u') and (v,v') are adjacent in G o H if and only if either u = v and u' is adjacent with v' in H, or u' = v' and u is adjacent with v in G.
- ~ The complement or inverse of a graph.

There is a much more detailed tutorial for these operations here.

Maps:

Loops and Routes:

Specialised variants of graph:

To follow the whole tutorial start on this page with constructing graphs.