(depth g) doesn't report correctly about cl-graph HOT 6 CLOSED

Hi Neil,

The behavior you're seeing occurs because the CL-Graph's default is to use undirected edges. So you thought you had the graph

 a --> b --> d
   ---> c --> e

but you really had

 a <--> b <--> d
   <---> c -<-> e

which has no root and so no sense of depth. If you change your code to look like

(setq g (let ((g (make-container 'graph-container :default-edge-type :directed))) 
 (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))

(With the added :default-edge-type), then you'll see what you expected. I'll file an enhancement request to have depth report a warning or error if there are no roots to the graph.

thanks,

from cl-graph.

Good point about directed graphs. However, I still get 0 on this example. If I use (graph->dot g t) the graph is directed, so I'm not sure what's going on. I'm a lisp newbie so perhaps I'm not setting variables properly (I just surrounded your example with a (depth ).

from cl-graph.

Curious. I tried

(depth (setq g (let ((g (make-container 'graph-container :default-edge-type :directed))) 
 (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)))

and got 2.

What does (graph-roots g) return (it should be the list of the vertex "a").

from cl-graph.

It returns

(#<D> #<E>)

My quicklisp directory lists the package name as cl-graph-20101006-darcs if that matters.

from cl-graph.

Just updated quicklisp and cl-graph to quicklisp 2011-04-18 and cl-graph-20110418-git and the depth problem has disappeared. Sorry for the confusion.

from cl-graph.

Hi Neil,

Great. I was going to suggest trying to upgrade but you figured it out before I got the chance!

from cl-graph.