Menu
▾
▴
Re: [Tcllib-devel] GSoC Graph. Review revision 25
|
From: Andreas K. <and...@ac...> - 2009-06-25 23:00:53
|
Andreas Kupries wrote:
> Michał Antoniewski wrote:
>> Hello.
>>
>> I updated some tests for Max-Cut ( testing subprocedures seperately ).
>
> Ok, will review.
> 515: #create complete graph
> 516: foreach v [$oddTGraph nodes] {
> 517: foreach u [$oddTGraph nodes] {
> 518: if { ![$oddTGraph arc exists $u$v] & ($u ne $v)
This triggered when I was reading the max-cut code. Tcl does short-cut
evaluation of conditions. In other words, the code above will
currently always look for a loop-edge for u == v. It is better to
write the simple condition u != v first, and when it returns false the
more complex 'arc exists' check is never done.
Also note that using & is likely a bug. The &-operator is the
bitwise-and. You likely want the &&-operator, the 'logical and'.
if { ($u ne $v) && ![$oddTGraph arc exists $u$v] } {
> 554:
> 555: proc ::struct::graph::op::findHamiltonCycle {G originalEdges
originalGraph} {
> 556:
> 557: isEulerian? $G tourvar
> 558: lappend result [$G arc source [lindex $tourvar 0]]
> 559:
> 560: lappend tourvar [lindex $tourvar 0]
> 561:
> 562: foreach i $tourvar {
> 563: set u [$G arc target $i]
> 564:
> 565: if { $u ni $result } {
> 566: set va [lindex $result end]
> 567: set vb $u
> 568:
> 569: if { ("$va $vb" in $originalEdges) || ("$vb $va" in $originalEdges) } {
[list $va $vb] etc. in all places (i.e. createCompleteGraph). The use
of "" still allows the construction of colliding edge names.
Ah, I note that the code in line 643 actually uses [list] to create
arc names. So, no collisions, but still a bug. Because you have to use [list]
here as well, when searching for the arcs. With the current code I can
give you node names which become arc names you will not find.
Example nodes 'a b' and 'c', the arc name constructed by [list] from
that is '{a b} c', and you are searching for 'a b c' because of "..." instead
of list.
An optimization to consider in the future is to make the case of a
complete graph as input fast again. I.e. createCompleteGraph could
note when it did not add any arcs, and this information can be used
here to avoid the searches by 'in'. An alternative providing the same
information would be to record the arcs which were added instead of
the originals, and then replace the condition with the complement,
i.e. 'arc ni addedArcs'. A third alternative would be to special case
this procedure, i.e. check if no arcs were added first, and use the
original code and loop in that case, without checking at each step.
> 570: lappend result $u
> 571: } else {
> 572:
> 573: set path [dict get [struct::graph::op::dijkstra $G $va] $vb]
> 574:
> 575: #reversing the path
> 576: set path [lreverse $path]
> 577: #cutting the start element
> 578: lremove path [lindex $path 0]
Cutting the start element is easier by using the builtin command 'lrange'.
set path [lrange $path 1 end]
Even a direct use of 'lreplace' is easier than to run lindex, then
lsearch (inside of lremove), and then lreplace. We know it is in
index 0, no search is needed.
The builtins lindex, lrange, lreplace are all index based.
> 579:
> 580: #adding the path and the target element
> 581: lappend result $path
The result is a list of nodes. What is added here is not a node as element,
but a list of node, making the result a list of (nodes and lists of nodes).
Likely meant is
lappend result {*}$path
which puts the nodes in the path into the result as independent nodes,
and not as single list (list expansion operator).
> 582: lappend result $vb
> 583: }
> 584: }
> 585: }
> 586:
> 587: set path [dict get [struct::graph::op::dijkstra $originalGraph
[lindex $result 0]] [lindex $result end]]
> 588: set path [lreverse $path]
> 589:
> 590: lremove path [lindex $path 0]
See above at line 578.
> 591: if { $path ne {} } {
path is a list, should be checked using a list operation. 'ne' is a string
operation.
if {[llength $path]} ...
> 592: lappend result $path
See above at line 581.
> 593: }
> 594: lappend result [$G arc source [lindex $tourvar 0]]
> 595: return $result
> 596: }
> 597:
> 628: proc ::struct::graph::op::createCompleteGraph {G originalEdges} {
> 629:
> 630: upvar $originalEdges st
> 631: set st {}
> 632: foreach e [$G arcs] {
> 633: set v [$G arc source $e]
> 634: set u [$G arc target $e]
> 635:
> 636: lappend st "$v $u"
Use [list] instead of "...", see above at line 569.
> 637: }
> 638:
> 639: foreach v [$G nodes] {
> 640: foreach u [$G nodes] {
> 641: if { ("$v $u" ni $st) && ("$u $v" ni $st) && ($u ne $v) && ![$G arc
exists [list $u $v]] } {
Use [list] instead of "...", see above at line 569 as well
Also, move the condition ($u ne $v) to the front, see my comments at
line 518 about short-cut evaluation of conditions.
> 642: $G arc insert $v $u [list $v $u]
> 643: $G arc setweight [list $v $u] Inf
Use of [list] is good.
> 650: proc ::struct::graph::op::lreverse l {
> 651: set result {}
> 652: set i [llength $l]
> 653: incr i -1
> 654: while {$i >= 0} {
> 655: lappend result [lindex $l $i]
> 656: incr i -1
> 657: }
> 658: return $result
> 659: }
This procedure is not needed. Tcl 8.5 has a lreverse builtin command.
> 780: #K Center Problem - 2 approximation algorithm
> 781:
#-------------------------------------------------------------------------------------
> 782: #
> 783: #
> 784: #
> 785: #
> 786: #
> 787:
> 788: #subprocedure creating graph with given set of edges
> 789: proc ::struct::graph::op::createGi {G E} {
> 790:
> 791: set Gi [struct::graph]
> 792:
> 793: foreach v [$G nodes] {
> 794: $Gi node insert $v
> 795: }
> 796:
> 797: foreach e $E {
> 798: set v [$G arc source $e]
> 799: set u [$G arc target $e]
> 800:
> 801: $Gi arc insert $v $u $e
> 802: }
> 803:
> 804: return $Gi
> 805: }
> 806:
> 807: #subprocedure creating from graph G two squared graph
> 808: #G^2 - graph in which edge between nodes u and v exists,
> 809: #if and only if, when distance (in edges, not weights)
> 810: #between those nodes is not greater than 2 and u != v.
> 811:
> 812: proc ::struct::graph::op::createTwoSquaredGraph {G} {
> 813:
> 814: set H [struct::graph]
> 815: set copyG [struct::graph]
> 816:
> 817: foreach v [$G nodes] {
> 818: $H node insert $v
> 819: $copyG node insert $v
> 820: }
> 821:
> 822: foreach e [$G arcs] {
> 823: set v [$G arc source $e]
> 824: set u [$G arc target $e]
> 825:
> 826: $copyG arc insert $v $u [list $v $u]
> 827: $copyG arc setweight [list $v $u] 1
> 828: }
> 829:
> 830: foreach v [$copyG nodes] {
> 831: foreach u [$copyG nodes] {
> 832: if { [distance $copyG $v $u] <= 2 && ![$H arc exists [list $u $v]]
&& ($u ne $v)} {
My understanding is that copyG is simply an exact copy of G, just with
arc weights forced to 1 for the distance calculation, right ?
Move condition ($u ne $v) to the front to stop execution of the
expensive distance check for u == v. I believe that we should move
the 'arc exists' check before the distance computation as well.
Right now we even compute distances which do not matter because of the
other conditions.
An optimization should be possible here ... The distance command is
dijsktra underneath, which has approx complexity O(n**2) in the number
of nodes (depending on the complexity of our prioqueue we may get
O(n*log n + e) ... The double loop around the distance calls here is
complexity O(n**2), for a total of O(n**4) complexity.
If we run dijkstra for each node once, saving the distance results
then we have O(n**3) complexity, with the double loop here reduced to
O(n**2), not that it then matters.
> 833: $H arc insert $v $u [list $v $u]
> 834: }
> 835: }
> 836: }
> 837:
copyG is not deleted, memory leak.
> 838: return $H
> 839: }
Andreas
|
