| 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 |
|
|
|
|
