tcllib-devel — Discussion of development for tcllib

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.

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

[Lars H. <Lar...@re...>]

Andreas Kupries skrev:
> Lars Hellström wrote:
>> Michał Antoniewski skrev:
>>> - for each Gi^2 we seek for maximum independent set Mi. Just to clear:
>>> finding maximal is of course NP hard, we seek for maximum set.
>>
>> You've got maximum and maximal the wrong way round here. Finding one 
>> maximal (w.r.t set inclusion) independent set is easy (add vertices 
>> until you've covered the graph). Finding one that achieves the maximum 
>> cardinality is hard.
> 
> Yes. I just googled for
>     weighted metric k-center
> and found the PDF
> 
> http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf
> 
> which seems to be the basis of Michal description, it is very similar.

Very similar indeed! Should probably be provided as reference.

> And it also describes it as finding maximal, not maximum, the latter 
> being NP-hard.
> 
>>
>> But now that I think about it... is this really what you want? The 
>> next steps being
>>
>>> - let the j be the min index, such that |Mj| <= k.
>>>
>>> - return Mj.
>>
>> it would seem more natural to seek a set which is somehow minimum here 
>> (as that would make it easier to meet this condition) than to pick the 
>> maximum. Indeed, given that
> 
> The pdf explains a bit more, maybe that helps.

Yes, it does. The algorithm approximates the minimal cost from _below_ 
rather than above, as far as the selection of edges is concerned; I 
hadn't expected that. Also, I hadn't fully noticed the "G must be a 
complete graph" condition... This, of course, means any nonempty set of 
vertices is dominating (= a vertex cover), so one can't get it wrong, 
only suboptimal.

Concerning that "complete graph" condition, though... Stylistically, 
it's a bit backwards to have a command that takes a graph as input, if 
only complete graphs are valid input. (Stretching a bit, it's kind of 
like having a command accepting a list of numbers as input, with the 
constraint that the numbers must all be equal to 1.) Even if the 
implementation very naturally exercises [struct::graph]s, one might 
want to take the time to think about whether a [struct::graph] is the 
most natural form for the input. If the implementation needs to 
preprocess the graph so that it is metrically complete, then maybe the 
output from the command that computes all shortest distances would be 
more practical, but if it can do the completion implicitly (which seems 
plausible for this algorithm; add uw at cost c(uv)+c(vw) to the queue 
once uv and vw have been processed) then a [struct::graph] as input 
becomes much more appropriate. In the latter case, the command 
documentation should take the "distance in general graph" point of 
view, rather than speaking about costs of individual edges.

Lars Hellström

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

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

>>A graph with a Hamilton cycle is said to be /Hamiltonian/, so I suppose
the term you were looking for here is "non->>Hamiltonian".

That's right. Thanks.

>>You've got maximum and maximal the wrong way round here. Finding one
maximal (w.r.t set inclusion) independent set is >>easy (add vertices until
you've covered the graph). Finding one that achieves the maximum cardinality
is hard.

Oh, I've mistaken the endings...AL with UM...sorry for confusion.

>>Lars Hellström wrote:
>>You've got maximum and maximal the wrong way round here. Finding one
maximal (w.r.t set inclusion) independent set is >>easy (add vertices until
you've covered the graph). Finding one that achieves the maximum cardinality
is hard.

>>Yes. I just googled for
>> weighted metric k-center
>>and found the PDF
>>http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf
>>which seems to be the basis of Michal description, it is very similar.
>>And it also describes it as finding maximal, not maximum, the latter being
NP-hard.

Actually, my main source is great book written by Vijay V. Vazirani -
Approximation Algorithms. That pdf is indeed very similar to what I've
written, I think it's possible it was based on the book I mentioned ( all
naming, as far I can see, is the same ).

I think, except that confusion with accidentally replacing the endings, the
rest of description was allright.


Best Regards,
Michał Antoniewski

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

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

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.

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.

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


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.

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.

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

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

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


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.


Best Regards,
Michal Antoniewski

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

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

Lars Hellström wrote:
> Michał Antoniewski skrev:
>> - for each Gi^2 we seek for maximum independent set Mi. Just to clear:
>> finding maximal is of course NP hard, we seek for maximum set.
> 
> You've got maximum and maximal the wrong way round here. Finding one 
> maximal (w.r.t set inclusion) independent set is easy (add vertices 
> until you've covered the graph). Finding one that achieves the maximum 
> cardinality is hard.

Yes. I just googled for
	weighted metric k-center
and found the PDF

http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf

which seems to be the basis of Michal description, it is very similar.

And it also describes it as finding maximal, not maximum, the latter being NP-hard.

> 
> But now that I think about it... is this really what you want? The next 
> steps being
> 
>> - let the j be the min index, such that |Mj| <= k.
>>
>> - return Mj.
> 
> it would seem more natural to seek a set which is somehow minimum here 
> (as that would make it easier to meet this condition) than to pick the 
> maximum. Indeed, given that

The pdf explains a bit more, maybe that helps.

>> The goal is to find such S, that |S| = k, and maxv { connect(v,S) } is as
>> small as possible.
> 
> it seems more like you're after a minimal covering than a maximal 
> independent set. Going to the square complicates the picture somewhat, 
> but it still looks to me as though your algorithm won't work.
> 
> Consider the case that Gi is the path u--v--w. The square of this is 
> the complete graph on these vertices, so a maximal independent set 
> contains one vertex. If you pick u or w, then you won't cover all of 
> Gi, which seems bad (it can be argued that connect(w,{u}) is infinite).
> 
> Also, there is the brute force approach of simply iterating over all 
> k-subsets S of V, computing maxv { connect(v,S) } for all. For small 
> fixed k this seems faster than what you're about to do, so it might be 
> considered as an alternative algorithm for solving the problem as 
> stated. (It could of course be that this range of parameters if fairly 
> uninteresting.)

Andreas.

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

[Lars H. <Lar...@re...>]

Michał Antoniewski skrev:
> - for each Gi^2 we seek for maximum independent set Mi. Just to clear:
> finding maximal is of course NP hard, we seek for maximum set.

You've got maximum and maximal the wrong way round here. Finding one 
maximal (w.r.t set inclusion) independent set is easy (add vertices 
until you've covered the graph). Finding one that achieves the maximum 
cardinality is hard.

But now that I think about it... is this really what you want? The next 
steps being

> - let the j be the min index, such that |Mj| <= k.
> 
> - return Mj.

it would seem more natural to seek a set which is somehow minimum here 
(as that would make it easier to meet this condition) than to pick the 
maximum. Indeed, given that

> The goal is to find such S, that |S| = k, and maxv { connect(v,S) } is as
> small as possible.

it seems more like you're after a minimal covering than a maximal 
independent set. Going to the square complicates the picture somewhat, 
but it still looks to me as though your algorithm won't work.

Consider the case that Gi is the path u--v--w. The square of this is 
the complete graph on these vertices, so a maximal independent set 
contains one vertex. If you pick u or w, then you won't cover all of 
Gi, which seems bad (it can be argued that connect(w,{u}) is infinite).

Also, there is the brute force approach of simply iterating over all 
k-subsets S of V, computing maxv { connect(v,S) } for all. For small 
fixed k this seems faster than what you're about to do, so it might be 
considered as an alternative algorithm for solving the problem as 
stated. (It could of course be that this range of parameters if fairly 
uninteresting.)

Lars Hellström

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

[Lars H. <Lar...@re...>]

Michał Antoniewski skrev:
> Hello.
> 
> I updated some tests for Max-Cut ( testing subprocedures seperately ).
> 
> And now TSP.
> 
> After some rethinking I came up with such solution to handle those
> uncomplete graphs:
> - first step filling graph with edges to have a complete graph. At the same
> time saving set of original Edges. Weights on new edges are set to Inf. [ In
> practise algorithm is avoiding them anyway, so maybe it's even not needed to
> take that step ].

As Andreas has already remarked, this will typically violate the 
triangle inequality, thus rendering the TSP instance non-metric. But 
the proof that converting a tour to a cycle by taking shortcuts doesn't 
increase the combined weight requires the problem to be metric, so 
you'd be in trouble here.

[snip]
> - what I described assumes that we accept doubled occurances of nodes in
> solution. Going back to definition of the problem - it says that there
> shouldn't be such situations ( TSP problem is finding shortest Hamilton
> Cycle, with only one occurance of each vertex ). So, now it's time to
> decide, what to do: give that solution I describe above, or in such case
> return error that it's not Hamilton's graph ( don't know if I wrote it well,
> but I mean graph without proper Hamilton cycle ).

A graph with a Hamilton cycle is said to be /Hamiltonian/, so I suppose 
the term you were looking for here is "non-Hamiltonian".

"Hamilton's graph" _might_ be taken as a reference to the dodekahedron, 
because of the icosian game: http://en.wikipedia.org/wiki/Icosian_game


Lars Hellström

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

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

Andreas Kupries wrote:
>  >  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)} {

I thought about this a bit more, on the way home yesterday, and sleeping over 
it. Not to be meant as criticism, the code here feels like a direct translation 
of the mathematical definition of G**2 graphs. It basically works by generating 
all pairs of nodes and then testing the distance between them, where the 
distance code is particular inefficient by using a dijkstra which computes the 
data for all nodes, and then throws 99% of it away.

We can do it better ... In essence, generate the node pairs in such a way that 
a distance check is not required, because the way the generation works ensures 
that the distance <= 2 condition holds true.

For this we have to unravel the definition of distance a bit, i.e. what does 
distance <= 2 mean ? We can analyze this easier by splitting it into 2 cases, i.e.
	distance == 1,
and	distance == 2.

So, distance (u,v)== 1 means ?
	That node u can be reached from v in one hop
<=>	u and v are connected by an edge in G	(a)
<=>	u is a "neighbour of v in G".		(b)	(X)

In other words, the G**@ graph has all edges of the original graph, and we can 
generate them either through translating (a) or (b) into code, i.e.

(Ad a)	for all e edge in G, with end nodes u, v
		add edge (u,v) to G**2

(Ad b)	for all nodes u in G
		for all nodes v neighbour of u in G
			add edge (u,v) to G**2, if u != v

Of these two fragments I prefer (b), for reasons explained when I am dealing 
with distance 2.


(Ad X)	As the input graph is considered unidirectional its neighbourhood is
	all adjacent nodes, whether conected by incoming or outgoing arcs.


Now, distance(u,v) == 2 means ?

	That node u can be reached from v in two hops
<=>	It exists a node z in G connected to both u and v
	with edges in G.			(c)

<=>	u is a neighbour of a neighbour of v in G,
	but not a neighbour of v, nor v.	(d)

Definition (c) doesn't translate that well to code, but (d) does.

(Ad d)	for all nodes u in G
		for all nodes z neighbour of u in G
			for all nodes v neighbour of z in G
				add edge (u,v) to G**2
					if	u != v and
						no edge (u,v) existing already.

The if condition at the end takes care of the "but not ..." terms in (d).

This also looks very similar to the code for (b), indeed the two fragements can 
be merged into one fragment which takes of both at the same time. Which is why 
I prefered fragment (b) here.

what we are in essence doing is to execute the two steps of dijkstra needed to 
find the nodes at distances 1 and 2 for all nodes, but no more. As this 
directly generates the nodes at the distance we are interested in the distance 
test becomes irrelevant. It is always true, by construction.

While it doesn't look like the mathematical definition any longer, and as such 
needs more comments to make the relation to it clear, it should also be more 
efficient than the naive code.


Now, looking at the overall algorithm,, as described in the other mail, i.e one 
level higher, about the series of G(i) of G(i)**2 we are apparently searching 
from G(1), G(2), ... on up one important question to ask is

	Do we have to compute all the G(i), G(i)**2 from the ground up ?

Complementary phrasing:
	Can we generate the G(i), G(i)**2 incrementally from the previous
	graph G(i-1), G(i-1)**2 ?	

In our case the answer is yes, we can do this incrementally.

	Assuming G(i-1), G(i-1)**2 exist, then

		G(i) = G(i-1) + edge Ei.

		G(i)**2 = (G(i-1)**2 + Ei + additional edges.
		These additional edges can be computed from Ei!
		Let Ei = (u,v). Then the nodes
			z in neighbours(u,G)-v are distance 2 to v
		and	z in neighbours(v,G)-u are distance 2 to u
		Easy to ocmpute and add.

	And the induction is started with G(0) == G(0)**2 == The graph
	containing just the nodes of the input graph, and no edges.

	The upshot of this is, we need only create one graph X in the code,
	which we initialize to contain G(0)**2, and during the loop iterating
	over our sorted edges we then extend this graph in each round using the
	above rules with Ei and distance-2 edges to contain G(i)**2.

Instead of createTwoSquaredGraph a better helper procedure will be 
extendTwoSquaredGraph


Andreas

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

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

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

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

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

As not much time left to midterm-evaluation - another update with some
subprocedures for K Center problem and a little description of the problem.

We are given undirected and completed graph G, where edge weights satisfy
triangle inequality (Metric).

Let the k be positive integer.
Let V be set of nodes and E be set of edges for G.
For any set S, which is a subset of V and node v (v is a element of V), let
connect(v, S) be the min cost of the edge, which connects node v with any
node in S.
The goal is to find such S, that |S| = k, and maxv { connect(v,S) } is as
small as possible.

In other words, we are searching for such subset of V, that it will be made
from k nodes, and the max value of connect function will be as small as
possible.

Generally, how algorithm works:

- first step is to sort edges E = {e1.....em} with their costs in not
decreasing order: cost(e1) <= .... <= cost(em)

- now we construct m graphs Gi like this: Gi = (V, Ei). So, set of nodes
remains the same, but we use only Ei edges.
e.g. E5 = {e1,e2,e3,e4,e5} - procedure createGi

- each graph Gi much be two squared -> Gi^2. Gi^2 is such graph that is has
an edge between nodes u and v, if and only if, the distance between those
nodes (in edges, not weights!) is not greater than 2. In other words, we can
go from u to v using max 2 edges. ---> procedure createTwoSquaredGraph

- for each Gi^2 we seek for maximum independent set Mi. Just to clear:
finding maximal is of course NP hard, we seek for maximum set.

- let the j be the min index, such that |Mj| <= k.

- return Mj.

So this is how it works in general. I think with more code and
updates things will get more clear, but for now just a quick look at what it
is planned to achieve.


Best Regards,
Michal Antoniewski

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

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

Michał Antoniewski wrote:
> 
> Hello.
>  
> I updated some tests for Max-Cut ( testing subprocedures seperately ).

Ok, will review.

> And now TSP.
>  
> After some rethinking I came up with such solution to handle those 
> uncomplete graphs:
> - first step filling graph with edges to have a complete graph. At the 
> same time saving set of original Edges. Weights on new edges are set to 
> Inf. [ In practise algorithm is avoiding them anyway, so maybe it's even 
> not needed to take that step ].

> - further, algorithm goes the same, until creating Hamilton Cycle ( 
> procedure findHamiltonCycle ).

> - what we were given was the set of nodes ( Hamilton cycle ) given based 
> on found Eulerian tour. But when graph is not complete edges based on 
> tour might not exist. So, at each step of adding next node to the result 
> ( Hamilton cycle ), algorithm checks, if edge between given nodes 
> exists. If it exists, it's allright - we don't need to change nothing. 
> If not - we have to search for the shortest path between current two 
> nodes and add this path to solution.
>  
> - what I described assumes that we accept doubled occurances of nodes in 
> solution. Going back to definition of the problem

 > it says that there
> shouldn't be such situations ( TSP problem is finding shortest Hamilton 
> Cycle, with only one occurance of each vertex ).

My understanding of the above is that this (only one occurence) is or can be 
true only for complete graphs. Given that we started from an incomplete graph I 
cannot see us able to avoid duplication in some cases. Namely when the hamilton 
cycle computed in the regular manner would be forced to use edges of infinite 
weight ...

Wait, triangle inequality (TIE) ... This gives us something we can reason with 
... A graph with edges of infinite weight will not satisfy this inequality in 
general (*), and so they are not really suitable for the metric-tsp algorithms.

Example:
	Assume nodes a b c, and edges

		a-b weight X,
		a-c weight Y,

	with X, Y not infinite, and edge

		b-c weight +Inf

	Then
		|b-c| > |b-a|+|a-c|,

	therefore TIE is violated.

And any incomplete graph we make complete in this manner (adding +Inf edges) 
will have at least one such triangle as in the example above.

Which means, our making the graph complete in this manner makes it 
automatically also unsuitable as input to the metric algorithms. So if we apply 
them anyway we should expect anomalies like a solution with duplicated nodes, 
or a solution which goes through an edge of +Inf weight.

Does that make sense ?


(Ad *) One exception is if all edges have the same weight of +Inf. Another set 
of exceptions are all graphs where the edges of finite weights are scattered 
around so that no two such share a node. Then all triangles in the completed 
graph have at least 2 edges of +Inf weight and satisfy TIE. But for these 
graphs the min spanning tree has to contain edges of +Inf weight. Before 
completion the graph was a forest, a set of connected pairs of nodes without 
other connections.

 > So, now it's time to
> decide, what to do: give that solution I describe above, or in such case 
> return error that it's not Hamilton's graph ( don't know if I wrote it 
> well, but I mean graph without proper Hamilton cycle ).

Given that we are extending the algorithm for use on graphs it is technically 
not suited for per my reasoning above returning a solution which is not quite 
satisfying the original constraints (each node only once) is not really an 
error IMVHO (in my very humble opinion). We will have to make this clear in the 
docs however.


> Implementation is at SVN now.

Ok, review added to work queue ...

 > I debugged it step by step and it worked
> for examples I was testing it, but still there can be some cases needed 
> consideration - I am on it. When I ran Christofides for it's Tight 
> Example it gave me the solution that reaches maximum approximation 
> factor ( for graph with 7 nodes, where OPT* was 6, it found solution 
> with cost 9 ).
> It still needs some upgrades ( like probably variable originalEdges will 
> be erased, as we need at that step whole original graph anyway...and 
> other), so you don't have to check implementation very strictly now, I 
> just wanted to show the main idea and next step in work.

> [*] By OPT and ALG, I used to name OPTimal solution and solution given 
> by ALGorithm.

Andreas.

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

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

Michał Antoniewski wrote:
> Regarding mails before:
>  
> Crush and crash....yeah my mistake:) I went with wrong letter...:) thx:)

No problem :) Should you ever read fanfiction you will find that things can be 
very much worse when it comes to mangling the english language ... Even 
mistakes like canon/cannon role/roll etc. are quite harmless compared to some 
atrocities seen.


>  >>Now that I am focused on this I do however see one possible problem 
> with the naming. Consider two arcs X and Y, the first >>between the 
> nodes 'a' and 'bc' and the second between 'ab' and 'c.
>  >>       X => $u$v = 'a' + 'bc' = 'abc'
>  >>       Y => $u$v = 'ab' + 'c' = 'abc'
>  
> Oh, I accidentaly ommited that case... Right, the same problem was 
> considering Bellman's Ford, but this time I did one bad assumption and 
> lost it. Anyways, just changing keys to lists this time didn't do the 
> trick, because there was a problem during execution of isEulerian? 
> method.

Uh. That is then a bug in isEulerian?. We should be able to handle all types of 
node names.

 > Fleury method ( used by Eulerian ) returns error, when it's
> given such graphs.

Definitely sounding like a bug in the existing code.

 > I will have to take a deeper look into it as firstly
> I wanted to end the new TSP implementation. Probably, it's not a big 
> problem, will see....

Please file a bug report for isEulerian?/Fleury about this (*) _if_ the search 
for the bug in Fleury takes to much of your time.

(Ad *) At https://sourceforge.net/tracker/?group_id=12883&atid=112883

>  >>This command makes the command ::struct::graph available as ::graph
>  >>The test environment masked the bug.
>  >>As reminder for myself to get rid of this
>  >>https://sourceforge.net/tracker/?func=detail&aid=2811747&group_id=12883&atid=112883 
> <https://sourceforge.net/tracker/?func=detail&aid=2811747&group_id=12883&atid=112883>
>  
> Oh, right... so now it's obvious why tests went good everytime.... I'm 
> glad that by accident it helped to find a bug.

I'm glad as well.

>  >>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
>  
> Interesting! Actually, now after spending some time coding in Tcl, I'm a 
> bit surprised, how it happened that Tcl was almost fully omitted during 
> classes at my University.... We was using Tcl scripts for example, when 
> doing some simulations on computer networks, but when it came to 
> subjects about programming in script languages, there was nothing about 
> Tcl...weird.

Tcl is sometimes called the best-kept secret among the scripting languages.
Companies don't want you to know the secret of their success, you might be came 
as effective as them in writing solutions in this easily used language. This is 
a bit tongue-in-cheek, but also has a kernel of truth.

Hopefully we, the community, manage to change that.

Andreas

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

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

Regarding mails before:

Crush and crash....yeah my mistake:) I went with wrong letter...:) thx:)


>>Now that I am focused on this I do however see one possible problem with
the naming. Consider two arcs X and Y, the first >>between the nodes 'a' and
'bc' and the second between 'ab' and 'c.
>>       X => $u$v = 'a' + 'bc' = 'abc'
>>       Y => $u$v = 'ab' + 'c' = 'abc'

Oh, I accidentaly ommited that case... Right, the same problem was
considering Bellman's Ford, but this time I did one bad assumption and lost
it. Anyways, just changing keys to lists this time didn't do the trick,
because there was a problem during execution of isEulerian? method. Fleury
method ( used by Eulerian ) returns error, when it's given such graphs. I
will have to take a deeper look into it, as firstly I wanted to end the new
TSP implementation. Probably, it's not a big problem, will see....

>>This command makes the command ::struct::graph available as ::graph
>>The test environment masked the bug.
>>As reminder for myself to get rid of this
>>
https://sourceforge.net/tracker/?func=detail&aid=2811747&group_id=12883&atid=112883

Oh, right... so now it's obvious why tests went good everytime.... I'm glad
that by accident it helped to find a bug.

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

Interesting! Actually, now after spending some time coding in Tcl, I'm a bit
surprised, how it happened that Tcl was almost fully omitted during classes
at my University.... We was using Tcl scripts for example, when doing some
simulations on computer networks, but when it came to subjects about
programming in script languages, there was nothing about Tcl...weird.


Best Regards,
Michal Antoniewski

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

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

Hello.

I updated some tests for Max-Cut ( testing subprocedures seperately ).

And now TSP.

After some rethinking I came up with such solution to handle those
uncomplete graphs:
- first step filling graph with edges to have a complete graph. At the same
time saving set of original Edges. Weights on new edges are set to Inf. [ In
practise algorithm is avoiding them anyway, so maybe it's even not needed to
take that step ].

- further, algorithm goes the same, until creating Hamilton Cycle (
procedure findHamiltonCycle ).

- what we were given was the set of nodes ( Hamilton cycle ) given based on
found Eulerian tour. But when graph is not complete edges based on tour
might not exist. So, at each step of adding next node to the result (
Hamilton cycle ), algorithm checks, if edge between given nodes exists. If
it exists, it's allright - we don't need to change nothing. If not - we have
to search for the shortest path between current two nodes and add this path
to solution.

- what I described assumes that we accept doubled occurances of nodes in
solution. Going back to definition of the problem - it says that there
shouldn't be such situations ( TSP problem is finding shortest Hamilton
Cycle, with only one occurance of each vertex ). So, now it's time to
decide, what to do: give that solution I describe above, or in such case
return error that it's not Hamilton's graph ( don't know if I wrote it well,
but I mean graph without proper Hamilton cycle ).

Implementation is at SVN now. I debugged it step by step and it worked for
examples I was testing it, but still there can be some cases needed
consideration - I am on it. When I ran Christofides for it's Tight Example
it gave me the solution that reaches maximum approximation factor ( for
graph with 7 nodes, where OPT* was 6, it found solution with cost 9 ).
It still needs some upgrades ( like probably variable originalEdges will be
erased, as we need at that step whole original graph anyway...and other), so
you don't have to check implementation very strictly now, I just wanted to
show the main idea and next step in work.



[*] By OPT and ALG, I used to name OPTimal solution and solution given by
ALGorithm.

Best Regards,
Michał Antoniewski

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

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

Andreas Kupries wrote:
>>  > 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.

In the testsuite, we run the file
	XOpsControl

which sources the file
	XSetup

which runs
	namespace import -force struct::graph

as its first command.

This command makes the command ::struct::graph available as ::graph

The test environment masked the bug.

As reminder for myself to get rid of this
https://sourceforge.net/tracker/?func=detail&aid=2811747&group_id=12883&atid=112883

Andreas.

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.

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

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

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

Review of changes to the TSP code in revision 19 ...

 > 462:		set TGraph [struct::graph]
 > 463:		
 > 464:		#filling graph TGraph with edges and nodes
 > 465:		set TGraph [createTGraph $G $T 0]

We seem to create TGraph twice here. ... Yes, createTGraph also
creates the graph.  So we still have a leaked graph object, created on
line 462. I guess that line 462 can be deleted, was forgotten.

 > 488:		#graph algorithm is working on - spanning tree of graph G
 > 489:		set TGraph [struct::graph]
 > 490:		set TGraph [createTGraph $G $T 1]

See above, about lines 462, 465. TGraph created twice, object of line 489 leaked.

 > 501:		#create complete graph
 > 502:		foreach v [$oddTGraph nodes] {
 > 503:			foreach u [$oddTGraph nodes] {
 > 504:				if { ![$oddTGraph arc exists $u$v] & !($u eq $v) } {

Ah, I missed something in my first review. I didn't see the !
operator, I guess due to the nested expr nearby. The complement to
the eq'ual operator is 'ne' for 'not equal.

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

Also a reminder about the $u$v problem, nodes a/bc vs ab/c giving us identical 
arc names.

 > 534:	#Finds Hamilton cycle in given graph G
 > 535:	#Procedure used by Metric TSP Algorithms:
 > 536:	#Christofides and Metric TSP 2-approximation algorithm
 > 537:	
 > 538:	proc ::struct::graph::op::findHamiltonCycle {G} {
 > 539:		isEulerian? $G tourvar
 > 540:		
 > 541:		lappend result [$G arc source [lindex $tourvar 0]]
 > 542:		
 > 543:		foreach i $tourvar {
 > 544:			set u [$G arc target $i]
 > 545:			
 > 546:			if { [lsearch $result $u] < 0 } {

'ni' operator.

 > 547:				lappend result $u
 > 548:			}
 > 549:		}
 > 550:		lappend result [$G arc source [lindex $tourvar 0]]
 > 551:		return $result
 > 552:	}
 > 553:	
 > 554:	#Creating graph from sets of given nodes and edges
 > 555:	#In option param we decide if we want edges to be
 > 556:	#duplicated or not
 > 557:	#0 - duplicated (Metric TSP 2-approximation algorithm)
 > 558:	#1 - single (Christofides Alogrithm)
 > 559:	
 > 560:	proc ::struct::graph::op::createTGraph {G Edges param} {

Naming. param => 'doublearcs' or similar.

 > 561:		set TGraph [graph]

Does that (graph) work? Shouldn't it be 'struct::graph' ? Because we
are in the struct::graph::op namespace, which doesn't have a
struct::graph::op::graph command. Nor do we have a ::graph
command. Well, we should not. We might have one in the testsuite,
masking the problem.


Andreas.

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

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

Andreas Kupries wrote:
> And for me it is now time to look at the max-cut code you committed yesterday.
> After a bit of regular work.

 > 572:	#Maximum Cut - 2 approximation algorithm
 > 573:	#----------------------------------------------------------------------
 > 574:	#
 > 575:	#
 > 576:	#
 > 577:	#
 > 578:	#
 > 579:	#Reference:
 > 580:	#
 > 581:	
 > 582:	proc ::struct::graph::op::MaxCut {G U V} {
 > 583:	
 > 584:		upvar $U _U
 > 585:		upvar $V _V
 > 586:		set nodeNumber [llength [$G nodes]]
 > 587:		set _U {}
 > 588:		set _V {}
 > 589:		set counter 0
 > 590:		
 > 591:		foreach v [lsort -dict [$G nodes]] {
 > 592:			if { [expr {$counter % 2}] eq 0 } {

	if {($counter % 2) == 0} {

 > 593:				lappend _U $v
 > 594:			} else {
 > 595:				lappend _V $v
 > 596:			}
 > 597:			incr counter
 > 598:		}

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
	}

For the list {a b c d e} the variables u and v are assigned

	u=a, v=b
	u=c, v=d
	u=e, v=""

This should also explain the check done before extending the list _V. For a 
list of odd length the last round through the loop will leave the variable v empty.

 > 599:		
 > 600:		set val 1
 > 601:		set ALG 0
 > 602:		while {$val>0} {
 > 603:			set val [cut $G _U _V [countEdges $G $_U $_V]]
 > 604:			if { $val > $ALG } {
 > 605:				set ALG $val
 > 606:			}
 > 607:		}
 > 608:		return $ALG
 > 609:	}
 > 610:	
 > 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.



 > 616:		set _V {}
 > 617:		set _U {}
 > 618:		set value 0
 > 619:		
 > 620:		set maxValue $param

 > 621:		set _U [reset $var1]
 > 622:		set _V [reset $var2]

See my notes blow on 'reset', leaving mean to wonder why not just

		set _U $var1
		set _V $var2

because that is what is currently happening with the current definition of 'reset'.

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

 > 627:				lappend _U $v
 > 628:				lremove _V $v
 > 629:				set value [countEdges $G $_U $_V]
 > 630:			} else {
 > 631:				lappend _V $v
 > 632:				lremove _U $v
 > 633:				set value [countEdges $G $_U $_V]
 > 634:			}
 > 635:			
 > 636:			if { $value > $maxValue } {
 > 637:				set var1 [reset $_U]
 > 638:				set var2 [reset $_V]
 > 639:				set maxValue $value
 > 640:			} else {
 > 641:				set _V [reset $var2]
 > 642:				set _U [reset $var1]
 > 643:			}
 > 644:		}

In the above, is it necessary to have a single loop ?

If not, we could maybe two loops, one over the nodes in V, the other over the 
nodes in U, obviating the need to perform the 'lsearch check'.

The one trouble I see with my idea is that the changes (moves of nodes to the 
other set) made by the first loop would affect the second one. Or, to avoid 
this, more book-keeping is needed to know which nodes moved and can be ignored 
by the second loop. So at second glance maybe better not, it doesn't feel 
anymore as if the code would be simpler. Same complexity I guess. Ah well.

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.


 > 645:	
 > 646:		set value $maxValue
 > 647:		
 > 648:		if { $value > $param } {
 > 649:			return $value
 > 650:		} else {
 > 651:			return 0
 > 652:		}
 > 653:	}
 > 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.


 > 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:	}

This whole procedure seems to be equivalent to

	proc ::struct::graph::op::reset {U} {
		return $U
	}

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.



 > 668:	#procedure counts edges that link two sets of nodes
 > 669:	proc ::struct::graph::op::countEdges {G U V} {
 > 670:		
 > 671:		set value 0
 > 672:		
 > 673:		foreach e [$G arcs] {
 > 674:			set v [$G arc source $e]
 > 675:			set u [$G arc target $e]
 > 676:			
 > 677:			if { [lsearch $U $v] >=0 && [lsearch $V $u] >=0 } {

See comments regarding line 626. Operations 'in' and ni'.

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



Andreas

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

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

Just to avoid confusion:

>>About TSP:

>>One thing this would depend on is whether the route found is required to
be a cycle, or can visit vertices more than once.

>>I would stick to definition of the problem, which says that we are looking
for path (with minimal cost) which visits each node >>exactly once, and ends
in the starting node.

I meant it considering complete graph, on which algorithm is working. For
graphs that are not complete it's possible that algorithm will pick an edge
that was not in that graph before ( generally, it shouldn't ... that's why
we add huge weights on additional edges ) and there will be a jump from node
to node with unexisting arc. That's why at the end those jumps have to be
changed into shortest paths between those nodes using existing edges ( total
cost can't be worser -> metric ). In that case we have some nodes occur more
than once in the final solution.

Best Regards,
Michał Antoniewski

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

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

Michał Antoniewski wrote:
> 
> 
>  
>  > 478:          
>  > 479:          set tourvar 0
> 
>  >Why is the variable initialized to a number, when it becomes a list 
> after the call ?
>  
> When I tested this implementation, sometimes occured that graph wasn't 
> Eulerian, so this was my way to prevent it from crushing when variable 

to crush	to make something very compact by putting pressure on it from
		all sides. like - to crush a car into a block of metal.

to crash	to abort the execution of the application in non-standard
		manner. in the context of cars, having a accident. like
		to crash the car into a railing, wall, or other obstacle.

> tourvar is not assigned. As I mentioned before this code needed still 
> some refactoring, now line 479 isn't needed, forgot to delete it.

Ah, I see.

>  > 523:                          $oddTGraph node insert $v
>  > 524:                  }
>  > 525:          }
>  > 526:                  
>  > 527:          #create complete graph
>  > 528:          foreach v [$oddTGraph nodes] {
>  > 529:                  foreach u [$oddTGraph nodes] {
>  > 530:                          if { ![$oddTGraph arc exists $u$v] & 
> ![expr {$u eq $v}] } {
> 
>  >>nother problem, maybe: This queries oddTGraph for the existence of 
> arcs, but at this point oddTGraph contains only nodes >>(added by lines 
> 521-524). This means that the first part of the condition is always true 
> and superfluous, right ? Or should this >>condition have queried the 
> TGraph ?
>  
> This procedure adds only edges, and when there is an edge between pair 
> of nodes we don't want another - that's why line 530 looks like this. 
> So, before adding (e.g. for node X and Y) we are checking if this edge 
> were added before ( for Y and X ). Loops are also unwelcome.

Ah. Right, of course. We start with nodes and no arcs, and any arc added is an 
arc the condition can trigger later on. Not much thinking on my side when 
looking at this, apparently.

This also explains why you are naming the arcs, i.e. the $u$v, this allows you 
to quickly check without additional data structures, right ? I was wondering, 
but decided it wasn't important enough to ask.

Now that I am focused on this I do however see one possible problem with the 
naming. Consider two arcs X and Y, the first between the nodes 'a' and 'bc' and 
the second between 'ab' and 'c.

	X => $u$v = 'a' + 'bc' = 'abc'
	Y => $u$v = 'ab' + 'c' = 'abc'

The condition will wrongly prevent the addition of Y. It believes that ythe 
arcs are parallel while they are not. This is like the index into an array or 
dictionary, where you had to define the key as

	set key [list $u $v]

to have enough structure to prevent such accidental identities. It was for the 
Bellman-Ford/Johnson algorithm's where we talked about that before, if I 
remember correctly.

> Now I'm going to add adding edges to handle uncomplete graphs. As a 
> consequence those graphs can have repeated nodes in the return value ( 
> the same nodes can occur more than once ).

Ok. Good luck.

And for me it is now time to look at the max-cut code you committed yesterday.
After a bit of regular work.

Andreas.

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

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

Michał Antoniewski wrote:
> 
>         Ok. Note, please update the algorithm status info in the
>         timeline at http://wiki.tcl.tk/23203 

> Updated.

Thank you.

>  >>Ok. Although I am a bit behind on my mail here. Looking at the time 
> this mail missed me by a few minutes on Friday. And I >>am not reading 
> office mail from the home system (*). Can I entice you to send your 
> mails not only to me, but
>  >>      Tcllib Developers <tcl...@li... 
> <mailto:tcl...@li...>>
>  >>as well ? That will reach me at home too, as I subscribed both office 
> and personal email adresses to the list.
>  
> No problem:) I didn't write at your home address, cause I didn't want to 
> bother you during weekend too...:)

That is no trouble. Either I am outside walking some park, without net 
connection (= not bothered at all), or I am inside reading, and then I can 
reading about graphs as well.


>  >>A bit of chiding here. A reason that the mentors ask the students for 
> the timeline of their project is to have them think about >>and become 
> aware of such dependencies.
>  
> I know it's not a good sequence that TSP using MaxMatching is before 
> MaxMatching itself, but I strongly wanted to have MaxMatching at the 
> end, cause as far as I know it's implementation can be troublesome, so 
> when I have everything other done and there is only Max Matching it 
> would easier to focus and it won't cause any delays in timeline, as I 
> estimated it could when done earlier. Maybe, it will turn out that 
> implementation will go smoothly, without any problems and those "safety 
> measures" were not required ( I hope:) ).

I see. Sort of what I often do ... Get the small stuff/fry out of the way 
first, working up to the more complex pieces.

So it was intentional, not an oversight. For future projects to note, I believe 
that it is a good idea to explicitly document such decisions to avoid questions 
later.

> About TSP:
>  
>  >>One thing this would depend on is whether the route found is required 
> to be a cycle, or can visit vertices more than once.
>  
> I would stick to definition of the problem, which says that we are 
> looking for path (with minimal cost) which visits each node exactly 
> once, and ends in the starting node.
>  
>  
> One more way to handle MaxMatching case can be implementing greedy 
> MaxMatching, for graphs with even number of nodes.
> Then, it's possible to write test cases, forcing test graphs to have 
> even number of nodes in their minimal spanning tree found in the first 
> step of the algorithm. That way, we can test the TSP procedure and only 
> add some tests when proper MaxMatching is done ( tight examples for 
> Christofides also have even number of nodes in min spanning tree).
>  
> Regarding your notes about both TSP algorithms, I'm going to divide them 
> into some auxiliary procedures.

Looking forward to it.

Andreas.

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

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

Lars Hellström wrote:
> Andreas Kupries skrev:
>> Michał Antoniewski wrote:
>>> Generally, TSP is problem concerning complete graphs, but there is a 
>>> way of handling other graphs by adding edges with very big weights
>>
>> Can these big weights be 'Inf'inity ? Or do they have to be tailired 
>> to the existing weights in some way ?
> 
> One thing this would depend on is whether the route found is required to 
> be a cycle, or can visit vertices more than once. Finding a Hamiltonian 
> cycle in the complete graph is easy, finding one in a sparser graph is 
> not so easy.

 From my look at the two algorithms it seems to create a cycle where vertices 
are visited once.

>> Greedy max-matching ... Is my understanding correct that this would 
>> find a matching, but not necessarily the maximal one ? Or not the best 
>> maximal per the weights ?
> 
> Note the following fine distinction:
> 
> MaximUM matching: One that is at least as great (in e.g. size or total 
> weight) as any other matching.
> 
> MaximAL matching: One that is not a proper subset of any other matching, 
> and thus maximal w.r.t. set inclusion in the set of all matchings.
> 
> A greedy algorithm would probably return a maximal matching, with no 
> guarantee of it being maximum. (The "no guarantee" part is not so 
> surprising; checking whether a given matching is maximum is easily seen 
> to be a problem in co-NP.)

Thanks for the clarification.

Andreas.

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

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

 This block of lines, 461-477, looks to me as something which should be put
> into its own command. I see that Christofides uses a variant of this (lines
> 503-517, without 505), just putting in the arcs instead of duplicating them.
> That can be folded into a single helper, and the duplication of arcs
> controlled by a single boolean argument.


Done.

> 478:
> 479:          set tourvar 0

>Why is the variable initialized to a number, when it becomes a list after
the call ?

When I tested this implementation, sometimes occured that graph wasn't
Eulerian, so this was my way to prevent it from crushing when variable
tourvar is not assigned. As I mentioned before this code needed still some
refactoring, now line 479 isn't needed, forgot to delete it.

> 480:          isEulerian? $TGraph tourvar
> 481:          lappend result [$TGraph arc source [lindex $tourvar 0]]
> 482:
> 483:          foreach i $tourvar {
> 484:                  set u [$TGraph arc target $i]
> 485:
> 486:                  if { [lsearch $result $u] < 0 } {
> 487:                          lappend result $u
> 488:                          set hh [$TGraph arc getweight $i]

 >>      Where is the value 'hh' used ? I do not see anything. If it is not
used
 >>      we can eliminate this I would say. On the other hand, if it should
have
 >>      been used, then something else is missing.

The same as previous one :) Corrected.


> 489:                  }
> 490:          }
> 491:          lappend result [$TGraph arc source [lindex $tourvar 0]]
> 492:          return $result
> 493:
> 494:  }

>>My understanding of this algorithm is that a min-spanning tree is made,
its arcs are then duplicated, and the euler tour >>through that graph is
then reduced into a hamilton cycle by ignoring every node already put into
the result.

>>And the approximation comes from the use of the minimal spanning tree.

Correct. Duplicating arcs gives us confidence that graph is Eulerian.
Finding Eulerian tour gives us sequence of visiting nodes in Hamilton cycle.


>>Missing: Deletion of the temporary graph TGraph. This is a memory leak.

Corrected.

> 496:  proc ::struct::graph::op::Christofides { G } {

>>See my comments above regarding lines 461-477.

Corrected. Other code problems that were noted, corrected as well.


> 523:                          $oddTGraph node insert $v
> 524:                  }
> 525:          }
> 526:
> 527:          #create complete graph
> 528:          foreach v [$oddTGraph nodes] {
> 529:                  foreach u [$oddTGraph nodes] {
> 530:                          if { ![$oddTGraph arc exists $u$v] & ![expr
{$u eq $v}] } {

>>nother problem, maybe: This queries oddTGraph for the existence of arcs,
but at this point oddTGraph contains only nodes >>(added by lines 521-524).
This means that the first part of the condition is always true and
superfluous, right ? Or should this >>condition have queried the TGraph ?

This procedure adds only edges, and when there is an edge between pair of
nodes we don't want another - that's why line 530 looks like this. So,
before adding (e.g. for node X and Y) we are checking if this edge were
added before ( for Y and X ). Loops are also unwelcome.


>>And Christofides becomes a bit clearer to me. Start with minimal spanning
tree, then create a max matching over the nodes >>of odd degree for
side-ways connections, instead of duplicating each arc in the tree. From
this we then construct euler tour >>and hamilton cycle like in the
'MetricTravelingSalesMan'.

Right.

So summarizing:
- added new commands for both TSP algorithms: findHamiltonCycle and
createTGraph.
- correcting code regardning remarks that were mentioned

Now I'm going to add adding edges to handle uncomplete graphs. As a
consequence those graphs can have repeated nodes in the return value ( the
same nodes can occur more than once ).

Best Regards,
Michał Antoniewski

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

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

>  Ok. Note, please update the algorithm status info in the timeline at
>> http://wiki.tcl.tk/23203
>
>
Updated.

>>Ok. Although I am a bit behind on my mail here. Looking at the time this
mail missed me by a few minutes on Friday. And I >>am not reading office
mail from the home system (*). Can I entice you to send your mails not only
to me, but
>>      Tcllib Developers <tcl...@li...>
>>as well ? That will reach me at home too, as I subscribed both office and
personal email adresses to the list.

No problem:) I didn't write at your home address, cause I didn't want to
bother you during weekend too...:)

>>A bit of chiding here. A reason that the mentors ask the students for the
timeline of their project is to have them think about >>and become aware of
such dependencies.

I know it's not a good sequence that TSP using MaxMatching is before
MaxMatching itself, but I strongly wanted to have MaxMatching at the end,
cause as far as I know it's implementation can be troublesome, so when I
have everything other done and there is only Max Matching it would easier to
focus and it won't cause any delays in timeline, as I estimated it could
when done earlier. Maybe, it will turn out that implementation will go
smoothly, without any problems and those "safety measures" were not required
( I hope:) ).

About TSP:

>>One thing this would depend on is whether the route found is required to
be a cycle, or can visit vertices more than once.

I would stick to definition of the problem, which says that we are looking
for path (with minimal cost) which visits each node exactly once, and ends
in the starting node.


One more way to handle MaxMatching case can be implementing greedy
MaxMatching, for graphs with even number of nodes.
Then, it's possible to write test cases, forcing test graphs to have even
number of nodes in their minimal spanning tree found in the first step of
the algorithm. That way, we can test the TSP procedure and only add some
tests when proper MaxMatching is done ( tight examples for Christofides also
have even number of nodes in min spanning tree).

Regarding your notes about both TSP algorithms, I'm going to divide them
into some auxiliary procedures.

Best Regards,
Michał Antoniewski