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

[Michał A. <ant...@gm...>]

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

> 611:  #procedure replaces nodes between sets and checks if that change is
profitable
> 612:  proc ::struct::graph::op::cut {G U V param} {
> 613:
> 614:          upvar $U var1
> 615:          upvar $V var2

I believe that it is more idiomatic to write

       proc ::struct::graph::op::cut {G Uvar Vvar param} {
               upvar $Uvar U
               upvar $Vvar V

I.e. to make explicit that the arguments are variable names, in their names,
and to name the variables they are linked to in the scope after them. 'var1'
and 'var2' are very non-explanatory names.

Corrected. Sometimes, I tend to come up with a lot of names, which at that
moment I recon as not well suiting and then I choose something as bad as
"param", which says nothing to reader :)

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

>>Even so, some other thing to consider in the longer-term future would be
an investigation into optimization of the countEdges >>calls in the loop.
Because, as only one node N has moved, only its edges can affect the count
(all outgoing edges of N which >>were to the same set are now to the other
set (+), and all edges to the other set are now to the same set (-)). This
would >>avoid a full recount. And also, actually allow us to compute the new
value before moving the node at all.

I think good idea, would be storing all optimizations and other tasks
planned somewhere in the future, in a document. I'm going to create such doc
and add to SVN, so going back to those tasks will be easier.


> 654:  #Removing element from the list - auxiliary procedure
> 655:  proc ::struct::graph::op::lremove {listVariable value} {
> 656:      upvar 1 $listVariable var
> 657:      set idx [lsearch -exact $var $value]
> 658:      set var [lreplace $var $idx $idx]
> 659:  }

>>Alternative to lremove is to add

    >>   package require struct::list

>>and then use
>>       struct::list delete

>>Doesn't need to be done yet. If we have only one place where we need this
it is more effective to stay with the local 'lremove' >>instead of pulling
in another big package we use only a very small part of.

Okey, so I am not changing it for now.


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


       if {($v in $U) && ($u in $V)} { ; # e is arc U -> V

> 678:                          incr value
> 679:                  }
> 680:                  if { [lsearch $U $u] >=0 && [lsearch $V $v] >=0 } {

       if {($u in $U) && ($v in $V)} { ; # e is arc V -> U

> 681:                          incr value
> 682:                  }
> 683:          }
> 684:
> 685:          return $value
> 686:  }

>>Hm. Lets try an alternate ...

       foreach u $U {
               foreach e [$G arcs -out $u] {
                       set v [$G arc target $e]
                       if {$v ni $V} continue
                       incr value
               }
       }
       foreach v $V {
               foreach e [$G arcs -out $v] {

>
>                        set u [$G arc target $e]
>                        if {$u ni $U} continue
>                        incr value
>                }
>        }
>
> The main point to the alternate is that the iteration over U and V
> eliminates one lsearch/in/ni query, because we know that the node is in the
> set, and which ...
>
> Time complexity of the original: O(#arcs * #nodes). The #nodes because of
> the lsearch, which is linear.
> Time complexity of the alternate: O(#nodes * ?). The ? could be #arcs, as
> we go over all arcs, just scattered across the nodes. The time constants
> might be lower (because of the reduced number of lsearch/in ops).
>
>
Right. Corrected.

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

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

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

Best Regards,
Michał Antoniewski