Chapter 8. find-islands function

89 views
Skip to first unread message

Larynx

unread,
Feb 1, 2015, 7:28:56 AM2/1/15
to land-o...@googlegroups.com
Hi. 
I'm a novice in CLISP programming.
In chapter 8, I'm stuck in the function, find-islands. 



(defun find-islands (nodes edge-list)
 
(let ((islands nil))
   
(labels ((find-island (nodes)
               
(let* ((connected (get-connected (car nodes) edge-list))
                     
(unconnected (set-difference nodes connected)))
                 
(push connected islands)
                 
(when unconnected
                   
(find-island unconnected)))))
     
(find-island nodes))
    islands
))


I create a sample edge-list and the results are as follows.



; My test edge-list : ((25 . 6) (6 . 4) (25 . 17) (20 . 3))

(get-connected 25 '((25 . 6) (2 . 4) (25 . 17) (20 . 3)))      ;=> (17 6 25)

(find-islands '
(25 6) '((25 . 6) (6 . 4) (25 . 17) (20 . 3)))  ;=> (17 4 6 25)

(connect-with-bridges '
((17 4 6 25)))                          ;=> NIL


My graph structure can be expressed like this.

a
)  25 -> 6 -> 4,  25 -> 17
b)  20 -> 3


In my test edge-list, 25 is not connected 20 or 3. 
But, find-islands function can't find isolated islands in my test edge-list.

I tried to understand this problem, but it very hard for me.
I need some hints. 

Thanks.











Mauricio

unread,
Feb 1, 2015, 6:49:05 PM2/1/15
to land-o...@googlegroups.com
Hi, maybe, just to be consistent with the book try to make your edges indirected (in other words you need both (25 . 6) and (6 . 25), also do provide the whole list of nodes to find-islands, I did run find-islands against your sample using all nodes and I get.

((3 20) (3) (17 4 6 25))

The reason 3 is an island is that there is no (3 , 20) in the list just (20 . 3), so there is a way to get to it but you cannot get from it to anywhere else.

The key here is to understand get-connected, find-islands simply goes fromthe first node, finds everything that is connected to it, and elminate those nodes from the list, creating a unconnected list, and then goes to the firs element of that unconnected list recursively, at the end you get groups of nodes that are isolated from each other.

you can use (trace find-islands get-connected) to see how te code runs.After you finish you can (untrace) probably that will help you visualize what is happening.

Larynx

unread,
Feb 2, 2015, 12:18:11 AM2/2/15
to land-o...@googlegroups.com
Thanks Mauricio. 

I read your reply and I check the code thoroughly again and again.  
I changes my test nodes and edge-list, and finally I got it. 

; My test edge-list : ((25 . 6) (6 . 4) (25 . 17) (20 . 3))
(get-connected 25 '((25 . 6) (6 . 4) (25 . 17) (20 . 3)))    
(find-islands '
(25 20) '((25 . 6) (6 . 4) (25 . 17) (20 . 3)))  ;=>  ((3 20) (17 4 6 25))

I think I was confused the expected result from find-islands function.
When I got ((3 20) (17 4 6 25)) in above test, I got to know the exact meaning of the word "island".

a. island can't be a single number
   Because edge-list is a list with many dotted lists, island can't be a single node.
b. the argument "nodes" is very important to find islands
   When I test find-islands function with nodes (25 6), the result was ((17 4 6 25)).





Simon Nicolussi

unread,
Feb 2, 2015, 6:29:32 PM2/2/15
to land-o...@googlegroups.com
> a. island can't be a single number
> Because edge-list is a list with many dotted lists, island can't be
> a single node.

The make-edge-list function just collects *edge-num* random edge pairs.
Nothing requires a node to act as an endpoint to any edge, so an island
consisting of a single node is certainly possible:

CL-USER> (find-islands '(1 2 3) '((2 . 3) (3 . 2)))
((3 2) (1))

A node that forms an island by itself won't show up in the edge list,
but it might if make-edge-list wouldn't discard loops.

> b. the argument "nodes" is very important to find islands
> When I test find-islands function with nodes (25 6), the result was
> ((17 4 6 25)).

Your second observation is correct.

--
Simon Nicolussi <si...@sinic.name>
http{s,}://{www.,}sinic.name/

Win Treese

unread,
Feb 3, 2015, 2:43:24 PM2/3/15
to land-o...@googlegroups.com
It looks to me like the test case you want to use for find-islands
needs to include all the nodes of interest in the nodes argument.

So you would call
(find-islands ‘(25 6 4 17 20 3) test-edge-list)

Otherwise, it simply doesn’t look for anything containing
nodes 20 or 3. One way to see this is to walk through the
evaluation of
(find-island ‘(25 6))
that is, the inner function defined with labels.

The local variable connected will get everything connected
to node 25 (which is the car of nodes). Then unconnected
is the set-difference of the original nodes list and connected,
which is empty, because the test only asked it to look for
nodes 25 and 6.

Hope this helps.

 - Win

--
You received this message because you are subscribed to the Google Groups "Land of Lisp" group.
To unsubscribe from this group and stop receiving emails from it, send an email to land-of-lisp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply all
Reply to author
Forward
0 new messages