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 = "Friday November 9, 2007 at 19:35:06 "

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-AXL_W_WillObsolete -DAxiom -Y $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
#1 (Warning) Deprecated message prefix: use `ALDOR_' instead of `_AXL'
   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-AXL_W_WillObsolete -DAxiom -Y $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
#1 (Warning) Deprecated message prefix: use `ALDOR_' instead of `_AXL'
   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)

g:=new()$FiniteGraph(INT)

 LISP output:
()

addNode(g,1)

(1)

addNode(g,2)

(2)

e:=addEdge(g,1,2)

(3)

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)

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-AXL_W_WillObsolete -DAxiom -Y $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
#1 (Warning) Deprecated message prefix: use `ALDOR_' instead of `_AXL'
   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)

g:=new()$FiniteGraph(INT)

 LISP output:
()

addNode(g,1)

(5)

addNode(g,2)

(6)

e:=addEdge(g,1,2)

(7)

source(e)

(8)

)lisp (room)

  2326/2326   78.0%       3 CONS BIGNUM RATIO COMPLEX STRUCTURE
   179/200    86.1%         FIXNUM SHORT-FLOAT LONG-FLOAT CHARACTER RANDOM-STATE READTABLE
SPICE
   632/795    98.4%       1 SYMBOL STREAM PATHNAME CCLOSURE CLOSURE
     1/8      34.8%         PACKAGE
    88/400    51.5%         ARRAY HASH-TABLE VECTOR BIT-VECTOR
    55/100    99.7%         CFUN CFDATA
   996/1243   24.8%       2 SFUN STRING GFUN VFUN AFUN

  2569/3000                 contiguous (450 blocks)
       1465                 hole
       1000   81.2%       1 relocatable

      4277 pages for cells
      9311 total pages
    239527 pages available
     13306 pages in heap but not gc'd + pages needed for gc marking
    262144 maximum pages
Value = NIL

Here is another Aldor version SandBox Category of Graphs 2