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