MathAction SandBox Category of Graphs in SPAD

Topics

FrontPage
- SandBox
  - SandBox Category of Graphs
    - SandBox Category of Graphs in SPAD <-- You are here.

First we define the general category of graphs.

spad

)abbrev category GRAPHS GraphCategory
GraphCategory(nodes:Type, edges:Type): Category == with
  source:edges->nodes
  target:edges->nodes

spad

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/7569958594964485335-25px001.spad using 
      old system compiler.
   GRAPHS abbreviates category GraphCategory 
------------------------------------------------------------------------
   initializing NRLIB GRAPHS for GraphCategory 
   compiling into NRLIB GRAPHS 

;;;     ***       |GraphCategory| REDEFINED
Time: 0 SEC.

   finalizing NRLIB GRAPHS 
   Processing GraphCategory for Browser database:
--->-->GraphCategory((source (nodes edges))): Not documented!!!!
--->-->GraphCategory((target (nodes edges))): Not documented!!!!
--->-->GraphCategory(constructor): Not documented!!!!
--->-->GraphCategory(): Missing Description
------------------------------------------------------------------------
   GraphCategory is now explicitly exposed in frame initial 
   GraphCategory will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/GRAPHS.NRLIB/code

Now we define finite graphs as follows:

spad

)abbrev domain FGRAPHS FiniteGraph

FiniteGraph(nodes: BasicType): exports == implementation where
  edges ==> Record(source:nodes,target:nodes)
  exports == GraphCategory(nodes,edges) with
    new: () -> %
    addNode: (%,List nodes) -> List nodes
    addNode: (%,nodes) -> List nodes
    addEdge: (%,nodes,nodes) -> edges
    edgeList: (%) -> List edges
    nodeList: (%) -> List nodes

  implementation == add
    Rep == Record(node: List nodes, edge: List edges)

    new:% == 
      n:List(nodes):=[]
      e:List(edges):=[]
      [n,e]$Rep pretend %

    addNode(g:%,n:List nodes):List nodes ==
      G:Rep:=g pretend Rep;
      if #G.node=0 then
        G.node:=n
      else
        concat!(G.node,n)
      n

    addNode(g:%,n:nodes):List nodes == addNode(g,[n])

    addEdge(g:%,src:nodes,tar:nodes):edges ==
      G:Rep:=g pretend Rep;
      if #G.edge=0 then
        G.edge:=[[src,tar]$edges]
      else
        concat!(G.edge,[[src,tar]$edges])
      [src,tar]$edges

    edgeList(g:%):List edges ==
      G:Rep:=g pretend Rep;
      G.edge
    nodeList(g:%):List nodes ==
      G:Rep:=g pretend Rep;
      G.node

    source(ed:edges):nodes == ed.source
    target(ed:edges):nodes == ed.target

spad

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/3160513407949145091-25px002.spad using 
      old system compiler.
   FGRAPHS abbreviates domain FiniteGraph 
   processing macro definition edges ==> Record(source: nodes,target: nodes) 
------------------------------------------------------------------------
   initializing NRLIB FGRAPHS for FiniteGraph 
   compiling into NRLIB FGRAPHS 
   compiling exported new : () -> $
Time: 0.01 SEC.

   compiling exported addNode : ($,List nodes) -> List nodes
Time: 0.08 SEC.

   compiling exported addNode : ($,nodes) -> List nodes
Time: 0 SEC.

   compiling exported addEdge : ($,nodes,nodes) -> Record(source: nodes,target: nodes)
Time: 0.02 SEC.

   compiling exported edgeList : $ -> List Record(source: nodes,target: nodes)
Time: 0 SEC.

   compiling exported nodeList : $ -> List nodes
Time: 0 SEC.

   compiling exported source : Record(source: nodes,target: nodes) -> nodes
      FGRAPHS;source;Rnodes;7 is replaced by QCAR 
Time: 0 SEC.

   compiling exported target : Record(source: nodes,target: nodes) -> nodes
      FGRAPHS;target;Rnodes;8 is replaced by QCDR 
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |FiniteGraph| REDEFINED

;;;     ***       |FiniteGraph| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor FiniteGraph
      Time: 0.11 seconds

   finalizing NRLIB FGRAPHS 
   Processing FiniteGraph for Browser database:
--->-->FiniteGraph((new (%))): Not documented!!!!
--->-->FiniteGraph((addNode ((List nodes) % (List nodes)))): Not documented!!!!
--->-->FiniteGraph((addNode ((List nodes) % nodes))): Not documented!!!!
--->-->FiniteGraph((addEdge (edges % nodes nodes))): Not documented!!!!
--->-->FiniteGraph((edgeList ((List edges) %))): Not documented!!!!
--->-->FiniteGraph((nodeList ((List nodes) %))): Not documented!!!!
--->-->FiniteGraph(constructor): Not documented!!!!
--->-->FiniteGraph(): Missing Description
------------------------------------------------------------------------
   FiniteGraph is now explicitly exposed in frame initial 
   FiniteGraph will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/FGRAPHS.NRLIB/code

Example 1: create a simple finite graph:

axiom