

last edited 2 years ago by test1 
1 2  
Editor: test1
Time: 2018/02/26 17:27:01 GMT+0 

Note: 
changed: Axiom currently lacks an implementation of the mathematical concept of *graph* in the sense of FriCAS currently has a subsystem for*graphs*. 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 *graph*graph* in the sense of changed: develop the concept of graph in Axiom in the most general develop the concept of graph in FriCAS in the most general changed: Make sure that FiniteGraph and GraphCategory are known to Axiom:: Make sure that FiniteGraph and GraphCategory are known to FriCAS::
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
)version
Value = "FriCAS 1.3.2 compiled at Tue Jan 16 19:11:58 UTC 2018"
See SandBox Category of Graphs in SPAD
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/axiomwiki/var/LatexWiki/graphcat.as using AXIOMXL compiler and options O Fasy Fao Flsp laxiom MnoALDOR_W_WillObsolete DAxiom Y $AXIOM/algebra I $AXIOM/algebra Use the system command )set compiler args to change these options. 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/axiomwiki/var/LatexWiki/fgraph.as using AXIOMXL compiler and options O Fasy Fao Flsp laxiom MnoALDOR_W_WillObsolete DAxiom Y $AXIOM/algebra I $AXIOM/algebra Use the system command )set compiler args to change these options. The )library system command was not called after compilation.
Make sure that FiniteGraph? and GraphCategory? are known to FriCAS:
\begin{axiom} )lisp (si::allocatecontiguouspages 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 ALLOCATECONTIGUOUSPAGES 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 righthand 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/axiomwiki/var/LatexWiki/812668914299600802825px006.as using AXIOMXL compiler and options O Fasy Fao Flsp laxiom MnoALDOR_W_WillObsolete DAxiom Y $AXIOM/algebra I $AXIOM/algebra Use the system command )set compiler args to change these options. 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)
Dynamic space usage is: 78,030, 144 bytes. Readonly space usage is: 5, 952 bytes. Static space usage is: 4, 000 bytes. Control stack usage is: 3, 568 bytes. Binding stack usage is: 736 bytes. Control and binding stack usage is for the current thread only. Garbage collection is currently enabled.
Breakdown for dynamic space: 21,281, 024 bytes for 21, 608 code objects. 19, 287, 536 bytes for 1, 205, 471 cons objects. 11, 783, 424 bytes for 108, 759 simplevector objects. 10, 500, 832 bytes for 120, 338 instance objects. 4, 463, 888 bytes for 50, 850 simplecharacterstring objects. 10, 713, 440 bytes for 189, 562 other objects. 78, 030, 144 bytes for 1, 696, 588 dynamic objects (space total.) Value = NIL
Here is another Aldor version SandBox Category of Graphs 2