dev/notes.text

   1 #|
   2 (in-package cl-graph)
   3
   4 (let ((g (make-instance 'graph-container
   5            :default-edge-type :directed)))
   6   (add-edge-between-vertexes g :a :b)
   7   (add-edge-between-vertexes g :a :c)
   8   (add-edge-between-vertexes g :b :d)
   9   (graph->dot g t))
  10 -> (prints)
  11 digraph G {
  12 graph [];
  13
  14 3 []
  15 1 []
  16 0 []
  17 2 []
  18 1->3 []
  19 0->1 []
  20 0->2 []
  21 }
  22 #<GRAPH-CONTAINER 4 #x17D9B526>
  23
  24 (defclass* weighted-directed-edge (directed-edge-mixin weighted-edge)
  25   ())
  26
  27 (let ((g (make-instance 'graph-container
  28            :default-edge-class 'weighted-directed-edge)))
  29   (add-edge-between-vertexes g :a :b)
  30   (add-edge-between-vertexes g :a :c)
  31   (add-edge-between-vertexes g :b :d :weight 2.5)
  32   (graph->dot g t
  33               :edge-formatter
  34               (lambda (e s) (format s "weight=~D" (weight e)))))
  35 -> (prints)
  36 graph G {
  37 graph [];
  38
  39 3 []
  40 1 []
  41 0 []
  42 2 []
  43 0--1 [dir=forward, ]
  44 1--3 []
  45 0--2 []
  46 }
  47 -> (returns)
  48 #<GRAPH-CONTAINER 4 #x17DAFE36>
  49
  50
  51 (defun weighted-sum-of-connected-vertexes (vertex)
  52   (let ((sum 0))
  53     (iterate-target-edges
  54      vertex
  55      (lambda (e)
  56        (incf sum (* (weight e) (element (other-vertex e vertex))))))
  57     sum))
  58
  59 graph-roots
  60 |#
  61
  62
  63 (in-package metabang.graph)
  64
  65 (in-package cl-graph)
  66 (defun is-connected-p (g)
  67   (let ((count 0))
  68     (cl-graph::breadth-first-visitor g (first-item g) (lambda (v)
  69                                                         (declare (ignore v))
  70                                                         (incf count)))
  71     (= count (size g))))
  72
  73 (let ((g (make-container 'graph-container))
  74       )
  75   (loop for v in '(a b c d e) do
  76         (add-vertex g v))
  77   (loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
  78         (add-edge-between-vertexes g v1 v2))
  79   g
  80   (is-connected-p g))
  81
  82 (let ((g (make-container 'graph-container))
  83       )
  84   (loop for v in '(a b c d e) do
  85         (add-vertex g v))
  86   (loop for (v1 . v2) in '((a . b) (a . c) (b . d)) do
  87         (add-edge-between-vertexes g v1 v2))
  88   g
  89   (is-connected-p g))
  90
  91
  92
  93 #|
  94 searching functions
  95 |#
  96
  97 #|
  98 nearest-common-descendent
  99 adjacentp
 100 adjacentp*
 101 all-next-vertexes
 102 all-next-vertexes*
 103 all-previous-vertexes
 104 all-previous-vertexes*
 105 |#
 106
 107 add-edge doesn't use force-new? or other args
 108
 109 I'd like to be able to (setf (edges g a b) c) or something
 110
 111 pull id-pools from AFS to use for graph and edge id's
 112
 113
 114 ;;; ---------------------------------------------------------------------------
 115
 116 ok - do vertexes know their graph? edges their vertexes?
 117 ok - edges can be defined 'generically'
 118 ok - in-undirected-cycle-p uses loop instead of iterate-vertexes
 119