dev/notes.text

   1 The only reasons we rely on cl-mathstats are
   2
   3 ;    /Users/gwking/.fasls/allegro-8.0m-macosx-x86/Users/gwking/darcs/cl-graph/dev/graphviz/graphviz-support.fasl
   4 Warning: While compiling these undefined functions were referenced:
   5          cl-graph::matrix-trace from position 7424 in
   6            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp
   7          cl-graph::matrix-multiply from position 7424 in
   8            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp, 7827 in
   9            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp
  10          cl-graph::normalize-matrix from position 7424 in
  11            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp
  12
  13 ;;; move to l0-arrays? or metatilities?
  14          cl-graph:: sum-of-array-elements from position 7424 in
  15            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp, 7827 in
  16            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp
  17          cl-graph::combination-count from position 5742 in
  18            /Users/gwking/darcs/cl-graph/dev/graph-metrics.lisp
  19
  20 some other things might be +e+, degrees->radians and radians->degrees,
  21   combination-count, permutation-count, sum-of-array-elements
  22
  23
  24 - Use samep in samep for associative containers
  25
  26 optimize : find-edge-between-vertexes-if
  27 (defmethod find-edge-between-vertexes-if ((graph graph-container)
  28                                           (vertex-1 graph-container-vertex)
  29                                           (value-2 t)
  30                                           fn
  31                                           &key error-if-not-found?)
  32   (let ((v2 (find-vertex graph value-2 error-if-not-found?)))
  33     (when v2
  34       (find-edge-between-vertexes-if
  35        graph vertex-1 v2 fn
  36        :error-if-not-found? error-if-not-found?))))
  37
  38 ;;; ---------------------------------------------------------------------------
  39
  40 (defmethod find-edge-between-vertexes-if ((graph graph-container)
  41                                           (value-1 t)
  42                                           (vertex-2 graph-container-vertex)
  43                                           fn
  44                                           &key error-if-not-found?)
  45   (let ((v1 (find-vertex graph value-1 error-if-not-found?)))
  46     (when v1
  47       (find-edge-between-vertexes-if
  48        graph v1 vertex-2 fn
  49        :error-if-not-found? error-if-not-found?))))
  50
  51
  52 Hmm, should probably write a macro that created all four method [ (t t), (t vertex), (vertex t) and (vertex vertex)] magically...
  53
  54
  55 Should have delete-item-at-1
  56
  57 delete-edge : equal or eql
  58
  59
  60 #|
  61 (in-package cl-graph)
  62
  63 (let ((g (make-instance 'graph-container
  64            :default-edge-type :directed)))
  65   (add-edge-between-vertexes g :a :b)
  66   (add-edge-between-vertexes g :a :c)
  67   (add-edge-between-vertexes g :b :d)
  68   (graph->dot g t))
  69 -> (prints)
  70 digraph G {
  71 graph [];
  72
  73 3 []
  74 1 []
  75 0 []
  76 2 []
  77 1->3 []
  78 0->1 []
  79 0->2 []
  80 }
  81 #<GRAPH-CONTAINER 4 #x17D9B526>
  82
  83 (defclass* weighted-directed-edge (directed-edge-mixin weighted-edge)
  84   ())
  85
  86 (let ((g (make-instance 'graph-container
  87            :default-edge-class 'weighted-directed-edge)))
  88   (add-edge-between-vertexes g :a :b)
  89   (add-edge-between-vertexes g :a :c)
  90   (add-edge-between-vertexes g :b :d :weight 2.5)
  91   (graph->dot g t
  92               :edge-formatter
  93               (lambda (e s) (format s "weight=~D" (weight e)))))
  94 -> (prints)
  95 graph G {
  96 graph [];
  97
  98 3 []
  99 1 []
 100 0 []
 101 2 []
 102 0--1 [dir=forward, ]
 103 1--3 []
 104 0--2 []
 105 }
 106 -> (returns)
 107 #<GRAPH-CONTAINER 4 #x17DAFE36>
 108
 109
 110 (defun weighted-sum-of-connected-vertexes (vertex)
 111   (let ((sum 0))
 112     (iterate-target-edges
 113      vertex
 114      (lambda (e)
 115        (incf sum (* (weight e) (element (other-vertex e vertex))))))
 116     sum))
 117
 118 graph-roots
 119 |#
 120
 121
 122 (in-package metabang.graph)
 123
 124 (in-package cl-graph)
 125 (defun is-connected-p (g)
 126   (let ((count 0))
 127     (cl-graph::breadth-first-visitor g (first-item g) (lambda (v)
 128                                                         (declare (ignore v))
 129                                                         (incf count)))
 130     (= count (size g))))
 131
 132 (let ((g (make-container 'graph-container))
 133       )
 134   (loop for v in '(a b c d e) do
 135         (add-vertex g v))
 136   (loop for (v1 . v2) in '((a . b) (a . c) (b . d) (c . e)) do
 137         (add-edge-between-vertexes g v1 v2))
 138   g
 139   (is-connected-p g))
 140
 141 (let ((g (make-container 'graph-container))
 142       )
 143   (loop for v in '(a b c d e) do
 144         (add-vertex g v))
 145   (loop for (v1 . v2) in '((a . b) (a . c) (b . d)) do
 146         (add-edge-between-vertexes g v1 v2))
 147   g
 148   (is-connected-p g))
 149
 150
 151
 152 #|
 153 searching functions
 154 |#
 155
 156 #|
 157 nearest-common-descendent
 158 adjacentp
 159 adjacentp*
 160 all-next-vertexes
 161 all-next-vertexes*
 162 all-previous-vertexes
 163 all-previous-vertexes*
 164 |#
 165
 166 add-edge doesn't use force-new? or other args
 167
 168 I'd like to be able to (setf (edges g a b) c) or something
 169
 170 pull id-pools from AFS to use for graph and edge id's
 171
 172
 173 ;;; ---------------------------------------------------------------------------
 174
 175 ok - do vertexes know their graph? edges their vertexes?
 176 ok - edges can be defined 'generically'
 177 ok - in-undirected-cycle-p uses loop instead of iterate-vertexes
 178