dev/notes.text

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