examples/doc/graph-walk.shape

   1 /** This file is part of Shapes.
   2  **
   3  ** Shapes is free software: you can redistribute it and/or modify
   4  ** it under the terms of the GNU General Public License as published by
   5  ** the Free Software Foundation, either version 3 of the License, or
   6  ** any later version.
   7  **
   8  ** Shapes is distributed in the hope that it will be useful,
   9  ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  ** GNU General Public License for more details.
  12  **
  13  ** You should have received a copy of the GNU General Public License
  14  ** along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  **
  16  ** Copyright 2014 Henrik Tidefelt
  17  **/
  18
  19 ##needs ..Shapes..Data / seq-support
  20
  21 ##lookin ..Shapes
  22 ##lookin ..Shapes..Data
  23
  24 /** Helper function for converting a sequence to a string, with elements separated by spaces.
  25  **/
  26 seq_sep_string: \ seq → [seq_string [separate ` ´ seq]]
  27
  28 /** Set up a graph to work with. **/
  29 g: [graph undirected:true
  30      nodes: [list 'a 'b 'c 'd]
  31      edges: [list (> 'a 'b <) (> 'a 'c <) (> 'b 'c <) (> 'd 'b <) (> 'd 'a <)]
  32    ]
  33
  34 /** Define a walk directly in terms of edges of the graph.  Usually, the edges are
  35  ** the result of some kind of search of traversal, but this time we just pick
  36  ** the edges by hand.
  37  **/
  38 w: [walk [list
  39            [g.the_u_edge 'a 'b]
  40            [g.the_u_edge 'b 'd]
  41            [g.the_u_edge 'd 'a]
  42            [g.the_u_edge 'a 'd]
  43            [g.the_u_edge 'd 'b]
  44            [g.the_u_edge 'b 'c]
  45          ]
  46     ]
  47
  48 /** Examine the walk. **/
  49 IO..•stdout << `Length of walk: ´ << w.edge_count << "{n}
  50 IO..•stdout << `Simple?:        ´ << w.simple? << "{n}
  51 IO..•stdout << `Node cover?:    ´ << w.node_cover? << "{n}
  52 IO..•stdout << `Edge cover?:    ´ << w.edge_cover? << "{n}
  53 IO..•stdout << `Open or closed: ´ << [if w.open? `open´ `closed´] << "{n}
  54 IO..•stdout << `Edges in the walk: ´ << [seq_sep_string w.edges] << "{n}
  55
  56 /** Visit all nodes along the walk. **/
  57 IO..•stdout << `Node keys along the walk: ´ << w.start.key
  58 ignore [] [w.edges.foldsl
  59   \ n e •dst →
  60   {
  61     next: [n.trace e]
  62     •dst << ` ´ << next.key
  63     next
  64   }
  65   w.start
  66   IO..•stdout
  67 ]
  68 IO..•stdout << "{n}
  69
  70 /** Prevent empty output error. **/
  71 Graphics..@spot