Edit detail for SandBox Category of Graphs revision 2 of 2

FriCAS currently has a subsystem forgraphs. The discussion below is morstly of historical interest. Note that some names in code below are the same as names in current implementation which causes conflicts and weird error messages...

We want an implementation of the mathematical concept of graphgraph* 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 FriCAS in the most general way possible.

Axiom Version

(1) -> )version

"FriCAS 1.3.10 compiled at Wed 10 Jan 02:19:45 CET 2024"

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/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/graphcat.as 
      using Aldor compiler and options 
-O -Fasy -Fao -Flsp -lfricas -Mno-ALDOR_W_WillObsolete -DFriCAS -Y $FRICAS/algebra -I $FRICAS/algebra
      Use the system command )set compiler args to change these 
      options.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/graphcat.as", line 1: 
#include "axiom.as"
^
[L1 C1] #1 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

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/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/fgraph.as 
      using Aldor compiler and options 
-O -Fasy -Fao -Flsp -lfricas -Mno-ALDOR_W_WillObsolete -DFriCAS -Y $FRICAS/algebra -I $FRICAS/algebra
      Use the system command )set compiler args to change these 
      options.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/fgraph.as", line 1: 
#include "axiom.as";
^
[L1 C1] #1 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

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

 \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)

   FiniteGraph(Integer) is a category, not a domain, and declarations 
      require domains.

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

source(e)$FiniteGraph(INT)

   The right-hand side of the $ operator must be a package or domain 
      name, but FiniteGraph(Integer) is a category.

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/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as
      using Aldor compiler and options 
-O -Fasy -Fao -Flsp -lfricas -Mno-ALDOR_W_WillObsolete -DFriCAS -Y $FRICAS/algebra -I $FRICAS/algebra
      Use the system command )set compiler args to change these 
      options.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as", line 1: 
#include "axiom.as"
^
[L1 C1] #1 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

Example 2: create a simple finite graph:

g:FiniteGraph(INT)

   FiniteGraph(Integer) is a category, not a domain, and declarations 
      require domains.

)lisp (room)

   Your user access level is compiler and this command is therefore not
      available. See the )set userlevel command for more information.

Here is another Aldor version SandBox Category of Graphs 2