(depth g) doesn't report correctly

[neilernst]

The depth function doesn't seem to be working; it always reports 0 for depth.

Example:

(setq 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))
(depth g)
0

From the API description, this should return 2, should it not? I'm running CCL on MacOSX using cl-graph with quicklisp. (many thanks for the library, btw!)

[gwkkwg]

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,

[neilernst]

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

[gwkkwg]

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").

[neilernst]

It returns

(#<D> #<E>)

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

[neilernst]

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.

[gwkkwg]

Hi Neil,

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