[cl-graph-devel] Problems with vertex identity using in-cycle-p

[Daniel Katz]

Hi again -

I'm trying to determine if I have a cycle in a directed graph, and  
I'm having some trouble with in-cycle-p.  In particular, I have the  
following:

----------------
;;; Return a non-connected graph with a cyclic component (a -> b -> c  
-> a) and a
;;; non-cyclic component (d -> e)
(defun mk-graph ()
     (let ((graph (cl-graph:make-graph 'cl-graph:graph-container
				    :vertex-test #'equal)))
     (cl-graph:add-vertex graph "a")
     (cl-graph:add-vertex graph "b")
     (cl-graph:add-vertex graph "c")
     (cl-graph:add-vertex graph "d")
     (cl-graph:add-vertex graph "e")
     (cl-graph:add-edge-between-vertexes graph "a" "b" :edge- 
type :directed)
     (cl-graph:add-edge-between-vertexes graph "b" "c" :edge- 
type :directed)
     (cl-graph:add-edge-between-vertexes graph "c" "a" :edge- 
type :directed)
     (cl-graph:add-edge-between-vertexes graph "d" "e" :edge- 
type :directed)
     graph))
----------------

and I then run the following:

----------------
 > (let ((graph (mk-graph)))
     (cl-graph:in-cycle-p graph (car (cl-graph:vertexes graph))))
----------------

and end up in the debugger:

----------------
Vertex #<b> not found in #<GRAPH-CONTAINER [5,4] {11939969}>
    [Condition of type CL-GRAPH:GRAPH-VERTEX-NOT-FOUND-ERROR]

Restarts:
0: [ABORT] Return to SLIME's top level.
1: [ABORT] Exit debugger, returning to top level.

Backtrace:
   0: ((SB-PCL::FAST-METHOD CL-GRAPH:FIND-VERTEX
        (CL-GRAPH:BASIC-GRAPH #1="#<...>" . #1#))
       #<unused argument>
       #<unused argument>
       #<CL-GRAPH:GRAPH-CONTAINER [5,4] {11939969}>
       #<b>
       T)
   1: ((LAMBDA (CL-GRAPH::V)) #<b>)
   2: (METABANG.UTILITIES:GRAPH-SEARCH
       (#<b>)
       #<CLOSURE (LAMBDA #) {11943CC5}>
       #<FUNCTION (LAMBDA #) {122BF3E5}>
       #<FUNCTION APPEND>)
   3: ((SB-PCL::FAST-METHOD CL-GRAPH:IN-CYCLE-P
        (CL-GRAPH:BASIC-GRAPH CL-GRAPH:BASIC-VERTEX))
       #<unavailable argument>
       #<unavailable argument>
       #<CL-GRAPH:GRAPH-CONTAINER [5,4] {11939969}>
       #<a>)
   4: (SB-INT:SIMPLE-EVAL-IN-LEXENV
       (LET ((GRAPH #))
         (CL-GRAPH:IN-CYCLE-P GRAPH (CAR #)))
       #<NULL-LEXENV>)
   5: (SWANK::EVAL-REGION
       "(let ((graph (mk-graph)))
      	  (cl-graph:in-cycle-p graph (car (cl-graph:vertexes graph))))
      "
       T)
----------------

Considering that I got the vertexes out of the same graph object I'm  
looking for them in, the message "Vertex #<b> not found..." doesn't  
really seem reasonable.

I also tried a variant of the graph where the vertexes were defined  
by symbols rather than by strings, but still got the same error  
message (well, the same except that the vertex in question was  
represented as #<B> rather than #<b> thanks to the reader doing some  
auto-upcasing...)

Any suggestions?

Thanks!

Dan