Re: [Tcllib-devel] GSoC Graph. Review revision 25

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

Michał Antoniewski wrote:
> New update available. A little description, what's new.
>  
> 1. I found out, what was wrong with Fleury procedure.
>  
> struct::set subtract arcs $arc - that line (1630) doesn't delete any 
> edges from current set of edges, when edge looks like this
>  [list $u $v], so it was causing trouble.

Hm. A bug in the struct::set implementation ?! Can you send me your example 
where Fleury failed without your change ? I will then go through it and see 
what I can find what struct::set is doing ...

Ah ... Now I see ... We are trying to subtract a single arc, but 'subtract' 
takes a _set_ as second argument. That is ok only as long as the $arc name 
doesn't contain whitespace. The moment it does the code tries to remove the 
parts of the name, considering them the elements, and they are not found, 
naturally.

So, changing 'subtract' to 'exclude' is also a fix for this bug. That is the 
correct method for removing a single element from a set.

The bug was in fleury, not in struct::set. Whew.

Please file a bug about this at the tcllib bug tracker at sourceforge.

A quick look over graphops.tcl showed me at least one other place where this is 
wrong, TarjanSub. I have to review the whole graphops.tcl to see if there are 
more. I will then also add test cases which would trigger the problem before 
the fix(es) got in.

Your fix works, because arcs is in essence a duplicate of the set of arcs in 
copy, as you saw.

> set arcs [$copy arcs] -  I replaced it with that line, which 
> straightly sets current set of edges used by algorithm from the copy of 
> graph algorithm is working on. Actually, IMHO that variable "arcs" can 
> be erased from that implementation.

In principle yes. In practice I (or Alejandro) believe that using the set is 
faster than to continuously query the copy for its arcs. I.e. trading off 
memory against speed.


> Now, all tests are passed and "ab c/a bc" problem is corrected in TSP 
> implementations.

Ok.

>  
> 2.  Christofides is using Greedy Max Matching implementation now. For 
> graph which is a Tight Example, Max Matching finds right solution, and 
> Christofides goes well too, reaching max approximation factor.

Ok.

> I've created sorting set of edges for a graph as a subprocedure, as it 
> can be useful. It is used in Max Matching to choose edges with lowest 
> cost at first. It will be also useful for K-Center problems.

Ok.

> Tests for both TSP problems are updated. I will quickly add some more 
> for Christofides in next update.

Yes, saw them.

>  
> I'm placing tests for subprocedures in files, where tests for procedures 
> which use them are....should I change it and create separate test files 
> for them?

No need to change this, having them in the same file is ok.

 > And should they be tested treating like separate procedures?
> What I mean, is for example: is the assumption that weights on arcs in 
> graph given at input properly set proper ( because previous 
> procedure, which uses that subprocedure, checks that before ), or there 
> should be at the beginning:
>  
> $VerifyWeightsAreOk $G and appropriate tests for it.

As it is a helper procedure for a specific caller there is no need to recheck 
the conditions caller has already checked.

Even if we wish to make this helper available to users of the graph ops package 
it is better to write and export a small wrapper procedure to perform the 
necessary checks, and keep them out of the helper itself.

>  
> I've added also condition for checking, if given graph is connected.

Ok.

> 3. Changes in implementation, considering remarks from previous mails 
> for Max-Cut and TSP problems.

> Next coming, Vertices Cover and further implementations and corrections 
> for Metric K-Center.

And now for the code of rev 26 ...


 >  528:				if { $u != $v } {
 >  529:					if { ![$oddTGraph arc exists [list $u $v]] } {
 >  530:						$oddTGraph arc insert $v $u [list $v $u]
 >  531:						$oddTGraph arc setweight [list $v $u] [distance $G $v $u]
 >  532:					}
 >  533:				}

Note that when I said to pull the ($u ne $v) condition to the front I
did not really meant to make it a separate if command, just to change
the order in the existing command. That is what the shortcut
evaluation of conditions is about, namely that the code

		if { ($u ne $v) && ![$oddTGraph arc exists [list $u $v]] } {
			...
		}

is internally evaluated exactly as you now wrote explicitly.

We can now leave it as is however, your call.

 >  562:	
 >  563:	#Greedy Max Matching procedure, which finds maximal ( not maximum ) 
matching
 >  564:	#for given graph G. It adds edges to solution, beginning from edges 
with the
 >  565:	#lowest cost.
 >  566:	
 >  567:	proc ::struct::graph::op::GreedyMaxMatching {G} {
 >  568:		
 >  569:		set copyG [struct::graph]

The copyG doesn't seem to be necessary. I see only two places where it
is used: 572-574, adding the nodes, and then line 595, where it is
destroyed.

 >  570:		set maxMatch {}
 >  571:		
 >  572:		foreach v [$G nodes] {
 >  573:			$copyG node insert $v
 >  574:		}
 >  575:		
 >  576:		foreach e [sortEdges $G] {
 >  577:			set v [$G arc source $e]
 >  578:			set u [$G arc target $e]
 >  579:			set neighbours [$G arcs -adj $v $u]
 >  580:			set param 1

param seems to mean 'e has no adjacent arcs in the matching'.
Maybe name it 'ok' ? Or 'noAdjacentArc' ?

 >  581:			
 >  582:			lremove neighbours $e
 >  583:			
 >  584:			foreach a $neighbours {
 >  585:				if { $a in $maxMatch } {
 >  586:					set param 0

The moment we have found one adjacent arc in the matching there is no
need to check any other. I.e. we can

					break

the loop.

 >  587:				}
 >  588:			}
 >  589:			if { $param } {
 >  590:				lappend maxMatch $e
 >  591:			}
 >  592:		}
 >  593:		
 >  594:		
 >  595:		$copyG destroy
 >  596:		return $maxMatch
 >  597:	}


 >  599:	#Subprocedure which for given graph G, returns the set of edges
 >  600:	#sorted with their costs.
 >  601:	proc ::struct::graph::op::sortEdges {G} {
 >  602:		set weights [$G arc weights]
 >  603:			
 >  604:		set sortedEdges {}
 >  605:		
 >  606:		foreach val [lsort [dict values $weights]] {
 >  607:			foreach x [dict keys $weights] {
 >  608:				if { [dict get $weights $x] == $val } {
 >  609:					set weights [dict remove $weights $x]
 >  610:					lappend sortedEdges $x ;#[list $val $x]
 >  611:				}
 >  612:			}
 >  613:		}
 >  614:		
 >  615:		return $sortedEdges
 >  616:	}

It took me a while to understand this procedure. Iteration over the
sorted weights, and adding all arcs with that weight to the result,
and removed from the input ... It should work ...

For comparison, in such a situation I usually do the sorting like this

	set tmp {}
	foreach {arc weight} [$G arc weights] {
		lappend tmp [list $arc $weight]
	}
	set sortedEdges {}
	foreach item [lsort -index 1 $tmp] {
		lappend sortedEdges [lindex $item 0]
	}

The first loop transforms a list of the form
	{a1 w1 a2 w2 ...}
into the form
	{{a1 w1} {a2 w2} ...}

Then we can use the -index option of lsort to sort the {aX wX}
elements by the second element, i.e. the weights.

At last, the second loop then pulls the arcs out of the sorted list.


If we were using Tcl 8.6, which we don't, we could even write

	return [dict keys [lsort -stride 2 -index 1 [$G arc weights]]]

Here the -stride 2 does the grouping of my first loop internally, just
for the comparison. The result is the dictionary sorted by weight, and
then we can pull the arcs as the keys of that list.


 >  918:				if { $u != $v } {
 >  919:					if { ![$H arc exists [list $u $v]] } {
 >  920:						if { [distance $copyG $v $u] <= 2 } {
 >  921:							$H arc insert $v $u [list $v $u]
 >  922:						}
 >  923:					}
 >  924:				}

See also my notes at 528-533, and the big mail where I reconstructed the whole 
thing.