An Axiom Graph Theory Implementation

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:
  • incidenceMatrix
  • adjacencyMatrix
  • laplacianMatrix
  • distanceMatrix
• about whole graph:
  • isAcyclic?
  • isFunctional?
• about specific nodes
  • isDirectSuccessor?
  • isGreaterThan?
  • isFixPoint?
• 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
  • min -- there is an arrow or a sequence of arrows from this node to every other node
  • max -- there is an arrow or a sequence of arrows to this node from every other node

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:

• Maps in FunctionGraph
• mapContra
• coAdjoint and contraAdjoint

Loops and Routes:

• Spanning Tree
• Loops
• Routes

Specialised variants of graph:

• Function Graphs
• Undirected Graphs
• Multifunction Graphs
• Weighted Graphs

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

EuclideanSpace

home

Computer Algebra Systems

On this page I have put some information about computer algebra systems and in particular Axiom/FriCAS.

Prerequisites

For more of the theory see the page here.

Other Code

This is one of a series of pages describing code that I have written for FriCAS. Some of this code has already been included with the FriCAS library and so can be used as soon as FriCAS is installed (as described here). Other code on these pages is not yet included with FriCAS and so would have to be compiled from within FriCAS. For an overview of all the code I have written, on various topics, see page here.

IDE for FriCAS

Axiom/Fricas Information on this Site