Re: [Tcllib-devel] ping gsoc graph work ...

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
> 
>     Actually, the whole block (lines 591-598) can be made simpler, by
>     using an advanced form of the foreach command. We can iterate using
>     multiple variables. Of the two possible forms we will want
> 
>            foreach {u v} [lsort -dict [$G nodes]] {
>                    lappend _U $u
>                    if {$v eq ""} continue
>                    lappend _V $v
>            }
> 
> Oh, thanks. Corrected. Now it looks simpler indeed.

You are welcome.

  >  > 623:
>  > 624:          foreach v [$G nodes] {
>  > 625:                  
>  > 626:                  if { [lsearch $_U $v] <0 } {
> 
> As we are using Tcl 8.5 we can use the 'in' and 'ni' operators. The 
> latter means 'not in'. They are applicable because we do not care about 
> the exact position, only about the contained/!contained information.
> 
>        if { $v ni $_U } {      ; # <=> v not in U ?
>  
> Ok. Corrected for all cases.

I wonder if I should try to compare

	in/ni (lists)
	struct::set contains (sets)
and	explicit list + array combination, or only an array

They are all about checking if a list/set contains some element, but with 
different tradeoffs regarding time complexity O(.), code complexity, 
readbility, code size, memory use ...

Which one to use is partly dependent on the size of lists we expect, but also 
if we are treating one thing sometimes as set, sometimes as list (which affects 
internal shimmering), and then comes in the judgment calls on whether to 
'package require' some supporting package or not.

Yes, I think so, I should. WEll, not immediately. This could become lengthy, 
like the essay I wrote regarding testing. A general overview not only on what 
options we have available for a reasonable small task, but also to show how to 
evaluate the differences ...

Now I am reminded of RosettaCode, a nice site for exmaple tasks implemented by 
lots of languages for comparison.

Tcl's page is
	http://www.rosettacode.org/wiki/Category:Tcl
And
	http://www.rosettacode.org/wiki/Tasks_not_implemented_in_Tcl

shows that Tcl managed to implement all 316 tasks.


>  > 660:  #Auxiliary procedure to set again proper values of two cut sets
>  > 661:  proc ::struct::graph::op::reset {U} {
>  > 662:          set value {}
>  > 663:          foreach u $U {
>  > 664:                  lappend value $u
>  > 665:          }
>  > 666:          return $value
>  > 667:  }
> 
>  >>I see an iteration over the list U which is reconstructed in the 
> variable 'value' and then returned. So value == U, thus we can >>return 
> it the argument directly. And at this point I have to ask if the 
> procedure is needed at all.
> 
> Actually, before this procedure was doing more stuff... After some cuts, 
> now it's useless, so good point:) I'm erasing it, didn't notice it 
> before....

Good to have reviews then ... More eyes ...

> About tests, I created some tests showing reaching max approximation 
> factor, and also graphs which show when the algorithm makes mistakes 
> (for example same graph but forced to choose different sets U, V at start).

These tests are maxcut-...-1.0/1.1 ? Yes ...

> TSP algorithms corrected too, regarding your remarks.
>  
>  > 561:          set TGraph [graph]
>  >>Does that (graph) work? Shouldn't it be 'struct::graph' ?
>  
> I changed back to struct::graph just to be sure, but when I was running 
> tests everything worked well...

Hm. I'll see what I can find out about this.

> Next updates: improved TSP, and some more tests for Max-Cut.
> I'm starting to work on k-center problems too.

Ok.

Revision 22 reviewed.

Andreas.