[cl-graph-devel] Bayesian networks

[Gary King]

Hi Joel,

CL-Graph should be a good fit for Bayesian Networks. You can create  
directed graphs either by creating a graph with a default-edge-type  
of :directed

> (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 []
> }

Or by using the edge-type parameter of add-edge-between-vertexes  
(here is a graph with different kinds of edges):

> (let ((g (make-instance 'graph-container)))
>   (add-edge-between-vertexes g :a :b :edge-type :directed)
>   (add-edge-between-vertexes g :a :c)
>   (add-edge-between-vertexes g :b :d)
>   (graph->dot g t))
> -> (prints)
> graph G {
> graph [];
>
> 3 []
> 1 []
> 0 []
> 2 []
> 0--1 [dir=forward, ]
> 1--3 []
> 0--2 []
> }
> -> (returns)
> #<GRAPH-CONTAINER 4 #x17DAFE36>

All edges have an element slot and you can use a weighted-edge to get  
a weight slot. If you want a weighted-directed-edge, you'll need to  
make a new class (which is a bit weird, sigh).

> (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)
> digraph G {
> graph [];
>
> 3 []
> 1 []
> 0 []
> 2 []
> 1->3 [weight=2.5]
> 0->1 [weight=1.0]
> 0->2 [weight=1.0]
> }

> Is it possible to sum up all the paths through a cl-graph such as  
> that the value of each non-root vertex is the weight of the edge  
> coming into it multiplied by the value of the vertex that the edge  
> connects to?
>

Something like this should work:

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

HTH,
-- 
Gary Warren King
metabang.com
http://www.metabang.com/