Axiom currently lacks an implementation of the mathematical concept of graph in the sense of Graph Theory See also: Graph_(mathematics) The concept of a graph is fundamental in many areas of mathematics and is the starting point for category theory. Graphs are also very important data structures in many algorithms in computer science. Our goal here therefore is to develop the concept of graph in Axiom in the most general way possible.

Axiom Version

)version

Value = "Sunday November 1, 2009 at 20:31:03 "

Spad Version

See SandBox Category of Graphs in SPAD

Aldor Verison

First we define the general category of graphs. Note that we use a [lowercase] short name graphcat for GraphCategory?.

#include "axiom.as"
define GraphCategory(nodes:Type, edges:Type): Category == with {
  source:edges->nodes;
  target:edges->nodes;
}

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/graphcat.as using AXIOM-XL compiler and 
      options 
-O -Fasy -Fao -Flsp -laxiom -Mno-ALDOR_W_WillObsolete -DAxiom -Y $AXIOM/algebra -I $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
   Compiling Lisp source code from file ./graphcat.lsp
   Issuing )library command for graphcat
   Reading /var/zope2/var/LatexWiki/graphcat.asy
   GraphCategory is now explicitly exposed in frame initial 
   GraphCategory will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/graphcat

Now we define finite graphs as follows:

#include "axiom.as";
#library graphcat "graphcat.ao";
import from graphcat;
inline from graphcat;
edges ==> Record(source:nodes,target:nodes);

FiniteGraph(nodes: BasicType): GraphCategory(nodes,edges)
with {
  new: %;
  addNode:(%,nodes)->nodes;
  addEdge:(%,nodes,nodes)-> edges;
} == add {
  Rep == Record(node: List nodes, edge: List edges);

  new:% == {
    n:List(nodes):=[];
    e:List(edges):=[];
    r:Rep:=[n,e];
    per(r);
  };
  addNode(g:%,n:nodes):nodes == {
    concat(rep(g).node,n);
    n;
  };
  addEdge(g:%,n1:nodes,n2:nodes):edges == {
    concat(rep(g).edge,[n1,n2]);
    [n1,n2];
  };

  source(ed:edges):nodes == ed.source;
  target(ed:edges):nodes == ed.target;
}

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/fgraph.as using AXIOM-XL compiler and 
      options 
-O -Fasy -Fao -Flsp -laxiom -Mno-ALDOR_W_WillObsolete -DAxiom -Y $AXIOM/algebra -I $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
   Compiling Lisp source code from file ./fgraph.lsp
   Issuing )library command for fgraph
   Reading /var/zope2/var/LatexWiki/fgraph.asy
   FiniteGraph is now explicitly exposed in frame initial 
   FiniteGraph will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/fgraph

Make sure that FiniteGraph? and GraphCategory? are known to Axiom:

 \begin{axiom}
 )lisp (si::allocate-contiguous-pages 3000 t)
 )library graphcat fgraph
 \end{axiom}

If we use UPPERCASE in the name of the Aldor library the example below results in:

    >> System error:
    AxiomXL file "GRAPHCAT" is missing!

But if we use lowercase, it (sometimes) works! However quite often when we refresh this page even without editing it, we get now the error:

    >> System error:
    Contiguous blocks exhausted.
  Currently, 1354 pages are allocated.
  Use ALLOCATE-CONTIGUOUS-PAGES to expand the space.

Example 1: create a simple finite graph:

g:FiniteGraph(INT)

Type: Void

g:=new()$FiniteGraph(INT)

 LISP output:
()

Type: FiniteGraph(Integer)

addNode(g,1)

(1)

Type: PositiveInteger

addNode(g,2)

(2)

Type: PositiveInteger

e:=addEdge(g,1,2)

(3)

Type: Record(source: Integer,target: Integer)

source(e)

   There are 1 exposed and 0 unexposed library operations named source
      having 1 argument(s) but none was determined to be applicable.
      Use HyperDoc Browse, or issue
                             )display op source
      to learn more about the available operations. Perhaps
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named
      source with argument type(s)
                   Record(source: Integer,target: Integer)

      Perhaps you should use "@" to indicate the required return type,
      or "$" to specify which version of the function you need.

Why do I need to specify $FiniteGraph(INT) in this case but not in the next example?

source(e)$FiniteGraph(INT)

(4)

Type: Integer

But without the category definition this seems to be ok?

#include "axiom.as"

edges ==> Record(source:nodes,target:nodes);

FiniteGraph(nodes: BasicType):
-- GraphCategory(nodes,edges)
with {
  source:edges->nodes;
  target:edges->nodes;
  new: %;
  addNode:(%,nodes)->nodes;
  addEdge:(%,nodes,nodes)-> edges;
} == add {
  Rep == Record(node: List nodes, edge: List edges);

  new:% == {
    n:List(nodes):=[];
    e:List(edges):=[];
    r:Rep:=[n,e];
    per(r);
  };
  addNode(g:%,n:nodes):nodes == {
    concat(rep(g).node,n);
    n;
  };
  addEdge(g:%,n1:nodes,n2:nodes):edges == {
    concat(rep(g).edge,[n1,n2]);
    [n1,n2];
  };

  source(ed:edges):nodes == ed.source;
  target(ed:edges):nodes == ed.target;
}

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/8126689142996008028-25px006.as using 
      AXIOM-XL compiler and options 
-O -Fasy -Fao -Flsp -laxiom -Mno-ALDOR_W_WillObsolete -DAxiom -Y $AXIOM/algebra -I $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
   Compiling Lisp source code from file 
      ./8126689142996008028-25px006.lsp
   Issuing )library command for 8126689142996008028-25px006
   Reading /var/zope2/var/LatexWiki/8126689142996008028-25px006.asy
   FiniteGraph is already explicitly exposed in frame initial 
   FiniteGraph will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/8126689142996008028-25px006

Example 2: create a simple finite graph:

g:FiniteGraph(INT)

Type: Void

g:=new()$FiniteGraph(INT)

 LISP output:
()

Type: FiniteGraph(Integer)

addNode(g,1)

(5)

Type: PositiveInteger

addNode(g,2)

(6)

Type: PositiveInteger

e:=addEdge(g,1,2)

(7)

Type: Record(source: Integer,target: Integer)

source(e)

(8)

Type: PositiveInteger

)lisp (room)

Dynamic space usage is:   411,806,736 bytes.
Read-only space usage is:      5,200 bytes.
Static space usage is:         3,088 bytes.
Control stack usage is:        3,184 bytes.
Binding stack usage is:          832 bytes.
Garbage collection is currently enabled.

Breakdown for dynamic space:
  322,469,920 bytes for    48,833 simple-character-string objects.
  33,695,136 bytes for 2,105,946 cons objects.
  21,682,480 bytes for    21,141 code objects.
  34,029,152 bytes for   433,762 other objects.
  411,876,688 bytes for 2,609,682 dynamic objects (space total.)
Value = NIL

Here is another Aldor version SandBox Category of Graphs 2