Edit detail for SandBox Category of Graphs revision 1 of 2

changed:
-
Axiom currently lacks an implementation of the mathematical
concept of *graph* in the sense of
"Graph Theory":http://en.wikipedia.org/wiki/Graph_theory.
See also:
"Graph_(mathematics)":http://en.wikipedia.org/wiki/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
\begin{axiom}
)version
\end{axiom}

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. 

\begin{aldor}[graphcat]
#include "axiom.as"
define GraphCategory(nodes:Type, edges:Type): Category == with {
  source:edges->nodes;
  target:edges->nodes;
}
\end{aldor}

Now we define finite graphs as follows:
\begin{aldor}[fgraph]
#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;
}
\end{aldor}

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:
\begin{axiom}
g:FiniteGraph(INT)
g:=new()$FiniteGraph(INT)
addNode(g,1)
addNode(g,2)
e:=addEdge(g,1,2)
source(e)
\end{axiom}

Why do I need to specify '$FiniteGraph(INT)' in this case but
not in the next example?
\begin{axiom}
source(e)$FiniteGraph(INT)
\end{axiom}

But without the category definition this seems to be ok?
\begin{aldor}
#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;
}
\end{aldor}

Example 2: create a simple finite graph:
\begin{axiom}
g:FiniteGraph(INT)
g:=new()$FiniteGraph(INT)
addNode(g,1)
addNode(g,2)
e:=addEdge(g,1,2)
source(e)
\end{axiom}

\begin{axiom}
)lisp (room)
\end{axiom}

Here is another Aldor version [SandBox Category of Graphs 2]

(1) -> )version

"FriCAS 1.4.0 compiled at Fri 16 Oct 16:10:51 CEST 2026"

#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.
#1 (Warning) Could not use archive file `libfricas.al'.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/graphcat.as", line 1: 
#include "axiom.as"
^
[L1 C1] #2 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

#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.
#1 (Warning) Could not use archive file `libfricas.al'.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/fgraph.as", line 1: 
#include "axiom.as";
^
[L1 C1] #2 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

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

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

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

g:FiniteGraph(INT)

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

source(e)$FiniteGraph(INT)

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

#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.
#1 (Warning) Could not use archive file `libfricas.al'.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as", line 1: 
#include "axiom.as"
^
[L1 C1] #2 (Error) Could not open file `axiom.as'.

   The )library system command was not called after compilation.

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.