[cl-graph-devel] Problem with find-connected-components

[Gary King]

Hi Daniel,

The problem you ran into was caused by some bit-rot in subgraph- 
containing. I'll be updating the project soon but if you want to keep  
experimenting, replace the current definition of find-connected- 
components with this:

(defmethod find-connected-components ((graph basic-graph))
   (collect-elements
    (make-iterator (connected-components graph) :unique t :transform  
#'parent)
    :transform
    (lambda (component)
      (subgraph-containing graph (element component)
                           :depth most-positive-fixnum))))

(I.e., add the :depth keyword before most-positive-fixnum).

Your test example also requires a minor change before it will work as  
expected: the vertexes of a graph are kept in a hashtable whose test   
is controlled by the vertex-test keyword argument to make-graph and  
which defaults to #'eq. Since you vertexes are _strings_, they won't  
in general be #'eq so when I run your code, I end with 13-vertexes  
instead of 5. To make things work as expected, you can either change  
the vertexes to symbols or numbers or anything that compares with  
#'eq or change the vertex-test to #'equal. Here is my definition:

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

I I then run this code:

>
> (loop for component in
>      (cl-graph:find-connected-components (foo))
>      for index from 1 do
>      (format t "~&Component ~D (~d node~:p and ~d edge~:p)"
> 	     index (vertex-count component) (edge-count component))
>      (iterate-edges component (lambda (edge)
> 				(format t "~&  ~a to ~a"
> 					(source-vertex edge)
> 					(target-vertex edge))))
>      (format t "~%"))


I get this output:

> Component 1 (2 nodes and 1 edge)
>   #<d> to #<e>
> Component 2 (3 nodes and 3 edges)
>   #<a> to #<b>
>   #<c> to #<a>
>   #<b> to #<c>


Please let me know if you run into any other problems and thanks for  
letting me know about the issue.
--
Gary Warren King, metabang.com
Cell: (413) 559 8738
Fax: (206) 338-4052
gwkkwg on Skype * garethsan on AIM