login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

# Edit detail for SandBox Category of Graphs revision 1 of 2

 1 2 Editor: Time: 2007/11/18 17:57:22 GMT-8 Note:

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.
"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}

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: %;
Rep == Record(node: List nodes, edge: List edges);

new:% == {
n:List(nodes):=[];
e:List(edges):=[];
r:Rep:=[n,e];
per(r);
};
concat(rep(g).node,n);
n;
};
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)
source(e)
\end{axiom}

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

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



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

fricas
)version
Value = "FriCAS 1.2.1 compiled at Monday July 1, 2013 at 23:26:54 "

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?.

aldor
#include "axiom.as"
define GraphCategory(nodes:Type, edges:Type): Category == with {
source:edges->nodes;
target:edges->nodes;
}
aldor
   Compiling FriCAS source code from file
/var/lib/zope2.10/instance/axiom-wiki/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.
#1 (Warning) Could not use archive file libaxiom.al'.
#2 (Warning) Could not use archive file libaxiom.al'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 4:
import from AxiomLib;
............^
[L4 C13] #3 (Error) No meaning for identifier AxiomLib'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 15:
import { true: %, false: % } from Boolean;
..................................^
[L15 C35] #4 (Error) No meaning for identifier Boolean'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 17:
string:         Literal -> %;
........................^.......^
[L17 C25] #5 (Error) No meaning for identifier Literal'.
[L17 C33] #6 (Error) There are no suitable meanings for the operator ->'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 18:
} from String;
.......^
[L18 C8] #8 (Error) No meaning for identifier String'.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/graphcat.as", line 2:
define GraphCategory(nodes:Type, edges:Type): Category == with {
.....................^.....^
[L2 C22] #10 (Error) Have determined 1 possible types for the expression.
Meaning 1: ?, ?
The context requires an expression of type Tuple(Type).
[L2 C28] #9 (Error) No meaning for identifier Type'.
"/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/graphcat.as", line 3:
source:edges->nodes;
.........^......^
[L3 C10] #11 (Error) There are 0 meanings for edges' in this context.
The possible types were:
edges: Type, a local
The context requires an expression of type Tuple(Type).
[L3 C17] #12 (Error) There are 0 meanings for nodes' in this context.
The possible types were:
nodes: Type, a local
The context requires an expression of type Tuple(Type).
[L3 C17] #13 (Fatal Error) Too many errors (use -M emax=n' or -M no-emax' to change the limit).
The )library system command was not called after compilation.

Now we define finite graphs as follows:

aldor
#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: %;
Rep == Record(node: List nodes, edge: List edges);
new:% == {
n:List(nodes):=[];
e:List(edges):=[];
r:Rep:=[n,e];
per(r);
};
concat(rep(g).node,n);
n;
};
concat(rep(g).edge,[n1,n2]);
[n1,n2];
};
source(ed:edges):nodes == ed.source;
target(ed:edges):nodes == ed.target;
}
aldor
   Compiling FriCAS source code from file
/var/lib/zope2.10/instance/axiom-wiki/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.
#1 (Warning) Could not use archive file libaxiom.al'.
#2 (Warning) Could not use archive file libaxiom.al'.
#9 (Warning) Could not use archive file libaxiom.al'.
Program fault (segmentation violation).#10 (Error) Program fault (segmentation violation).
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 4:
import from AxiomLib;
............^
[L4 C13] #3 (Error) No meaning for identifier AxiomLib'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 15:
import { true: %, false: % } from Boolean;
..................................^
[L15 C35] #4 (Error) No meaning for identifier Boolean'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 17:
string:         Literal -> %;
........................^.......^
[L17 C25] #5 (Error) No meaning for identifier Literal'.
[L17 C33] #6 (Error) There are no suitable meanings for the operator ->'.
"/usr/local/aldor/linux/1.1.0/include/axiom.as", line 18:
} from String;
.......^
[L18 C8] #8 (Error) No meaning for identifier String'.
The )library system command was not called after compilation.

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:

fricas
g:FiniteGraph(INT)
FiniteGraph(Integer) is a category, not a domain, and declarations
require domains.
g:=new()$FiniteGraph(INT) The right-hand side of the$ operator must be a package or domain
name, but FiniteGraph(Integer) is a category.
There are no library operations named addNode
Use HyperDoc Browse or issue
to learn if there is any operation containing " addNode " in its
name.
Cannot find a definition or applicable library operation named
Variable(g)
PositiveInteger
Perhaps you should use "@" to indicate the required return type,
or "$" to specify which version of the function you need. addNode(g,2) There are no library operations named addNode Use HyperDoc Browse or issue )what op addNode to learn if there is any operation containing " addNode " in its name. Cannot find a definition or applicable library operation named addNode with argument type(s) Variable(g) PositiveInteger Perhaps you should use "@" to indicate the required return type, or "$" to specify which version of the function you need.
There are no library operations named addEdge
Use HyperDoc Browse or issue
to learn if there is any operation containing " addEdge " in its
name.
Cannot find a definition or applicable library operation named
Variable(g)
PositiveInteger
PositiveInteger
Perhaps you should use "@" to indicate the required return type,
or "$" to specify which version of the function you need. source(e) There are no library operations named source Use HyperDoc Browse or issue )what op source to learn if there is any operation containing " source " in its name. Cannot find a definition or applicable library operation named source with argument type(s) Variable(e) 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? fricas 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? 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; } aldor  Compiling FriCAS source code from file /var/lib/zope2.10/instance/axiom-wiki/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. #1 (Warning) Could not use archive file libaxiom.al'. #2 (Warning) Could not use archive file libaxiom.al'. "/usr/local/aldor/linux/1.1.0/include/axiom.as", line 4: import from AxiomLib; ............^ [L4 C13] #3 (Error) No meaning for identifier AxiomLib'. "/usr/local/aldor/linux/1.1.0/include/axiom.as", line 15: import { true: %, false: % } from Boolean; ..................................^ [L15 C35] #4 (Error) No meaning for identifier Boolean'. "/usr/local/aldor/linux/1.1.0/include/axiom.as", line 17: string: Literal -> %; ........................^.......^ [L17 C25] #5 (Error) No meaning for identifier Literal'. [L17 C33] #6 (Error) There are no suitable meanings for the operator ->'. "/usr/local/aldor/linux/1.1.0/include/axiom.as", line 18: } from String; .......^ [L18 C8] #8 (Error) No meaning for identifier String'. "/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as", line 5: FiniteGraph(nodes: BasicType): ...................^ [L5 C20] #9 (Error) No meaning for identifier BasicType'. "/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as", line 8: source:edges->nodes; ................^ [L8 C17] #10 (Error) There are 0 meanings for nodes' in this context. The possible types were: nodes: BasicType, a local The context requires an expression of type Tuple(Type). "/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8126689142996008028-25px006.as", line 11: addNode:(%,nodes)->nodes; ...........^ [L11 C12] #11 (Error) Have determined 1 possible types for the expression. Meaning 1: with source: Record(source: nodes, t... The context requires an expression of type Tuple(Type). [L11 C12] #13 (Fatal Error) Too many errors (use -M emax=n' or -M no-emax' to change the limit). The )library system command was not called after compilation. Example 2: create a simple finite graph: fricas g:FiniteGraph(INT) FiniteGraph(Integer) is a category, not a domain, and declarations require domains. g:=new()$FiniteGraph(INT)
The right-hand side of the $operator must be a package or domain name, but FiniteGraph(Integer) is a category. addNode(g,1) There are no library operations named addNode Use HyperDoc Browse or issue )what op addNode to learn if there is any operation containing " addNode " in its name. Cannot find a definition or applicable library operation named addNode with argument type(s) Variable(g) PositiveInteger Perhaps you should use "@" to indicate the required return type, or "$" to specify which version of the function you need.
There are no library operations named addNode
Use HyperDoc Browse or issue
to learn if there is any operation containing " addNode " in its
name.
Cannot find a definition or applicable library operation named
Variable(g)
PositiveInteger
Perhaps you should use "@" to indicate the required return type,
or "$" to specify which version of the function you need. e:=addEdge(g,1,2) There are no library operations named addEdge Use HyperDoc Browse or issue )what op addEdge to learn if there is any operation containing " addEdge " in its name. Cannot find a definition or applicable library operation named addEdge with argument type(s) Variable(g) PositiveInteger PositiveInteger Perhaps you should use "@" to indicate the required return type, or "$" to specify which version of the function you need.
source(e)
There are no library operations named source
Use HyperDoc Browse or issue
)what op source
to learn if there is any operation containing " source " in its
name.
Cannot find a definition or applicable library operation named
source with argument type(s)
Variable(e)
Perhaps you should use "@" to indicate the required return type,
or "\$" to specify which version of the function you need.

fricas
)lisp (room)
Dynamic space usage is:   78,287,648 bytes.
Read-only space usage is:      5,952 bytes.
Static space usage is:         4,000 bytes.
Control stack usage is:        3,568 bytes.
Binding stack usage is:          752 bytes.
Control and binding stack usage is for the current thread only.
Garbage collection is currently enabled.
Breakdown for dynamic space:
20,718,320 bytes for    21,271 code objects.
19,527,056 bytes for 1,220,441 cons objects.
11,910,800 bytes for   106,883 simple-vector objects.
10,508,992 bytes for   120,997 instance objects.
4,897,216 bytes for    55,901 simple-character-string objects.
10,725,264 bytes for   195,143 other objects.
78,287,648 bytes for 1,720,636 dynamic objects (space total.)
Value = NIL`

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