tcllib-devel — Discussion of development for tcllib

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

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

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.

For metric TSP (i.e., the triangle inequality holds), you're not 
allowed to exceed the weight of the shortest path between the endpoints 
anyway.

There's also the issue that the size of (number of bits needed to 
encode) the weights sometimes becomes the deciding factor for the 
complexity of graph algorithms, but that mostly figures in arguments 
that goes: Well you've constructed an example where this algorithm 
appears to have a higher complexity than we claimed it did, but that's 
just because you've used gigantic weights, and if you do your math 
carefully you'll see that the basic bitsize of your example grows much 
faster than the number of edges in it. Probably not so relevant for 
TSP, but (if I recall correctly) important for some classical max-flow 
algorithms. 8-)}

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

Lars Hellström

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

[KATO K. <k.k...@gm...>]

Hi,
> However, we are here talking about the manipulation of graphs in memory,
> to compute things like distances between nodes,
> and "standard" representations, like Adjacency matrices and lists.

huddle can contain the data has plural different structures,
and can support for additional data structures e.g. graphs and tree.
(However there is needed to improbe for self-recursive data structure)

If we need to talk about this more deeply,
I have to read codes for the graph libarary...

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

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
>> Hello.

Comments between the lines of code


 > 433:	#Metric Travelling Salesman Problem (TSP) - 2 approximation algorithm
 > 434: 
#-------------------------------------------------------------------------------------
 > 435:	#Travelling salesman problem is a very popular problem in graph theory, 
where
 > 436:	#we are trying to find minimal Hamilton cycle in weighted complete 
graph. In other words:
 > 437:	#given a list of cities (nodes) and their pairwise distances (edges), 
the task is to find
 > 438:	#a shortest possible tour that visits each city exactly once.
 > 439:	#TSP problem is NP-Complete, so there is no efficient algorithm to 
solve it. Greedy methods
 > 440:	#are getting extremely slow, with the increase in the set of nodes.
 > 441:	#
 > 442:	#For this algorithm we consider a case when for given graph G, the 
triangle inequality is
 > 443:	#satisfied. So for example, for any three nodes A, B and C the distance 
between A and C must
 > 444:	#be at most the distance from A to B plus the distance from B to C. 
What's important
 > 445:	#most of the considered cases in TSP problem will satisfy this condition.
 > 446:	#
 > 447:	#Input: weighted and complete graph G
 > 448:	#Output: approximated solution of minimum Hamilton Cycle - closed path 
visiting all nodes,
 > 449:	#each exactly one time.
 > 450:	#
 > 451:	#Reference: http://en.wikipedia.org/wiki/Travelling_salesman_problem
 > 452:	#
 > 453:	
 > 454:	proc ::struct::graph::op::MetricTravellingSalesman { G } {
 > 455:		
 > 456:		#checking if all weights are set
 > 457:		VerifyWeightsAreOk $G
 > 458:		
 > 459:		#create minimum spanning tree for graph G
 > 460:		set T [struct::graph::op::prim $G]


 > 461:		#graph algorithm is working on - spanning tree of graph G
 > 462:		set TGraph [struct::graph]
 > 463:		
 > 464:		#fill TGgraph with nodes
 > 465:		foreach n [$G nodes] {
 > 466:			$TGraph node insert
 > 467:		}
 > 468:		
 > 469:		#fill TGraph with arcs
 > 470:		foreach e $T {
 > 471:			set v [$G arc source $e]
 > 472:			set u [$G arc target $e]
 > 473:			$TGraph arc insert $u $v $u$v
 > 474:			$TGraph arc insert $v $u $v$u
 > 475:			$TGraph arc setweight $u$v [$G arc getweight $e]
 > 476:			$TGraph arc setweight $v$u [$G arc getweight $e]
 > 477:		}

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.




 > 478:		
 > 479:		set tourvar 0

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

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

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

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




 > 496:	proc ::struct::graph::op::Christofides { G } {
 > 497:		#checking if all weights are set
 > 498:		VerifyWeightsAreOk $G
 > 499:		
 > 500:		#create minimum spanning tree for graph G
 > 501:		set T [prim $G]
 > 502:		

 > 503:		#graph algorithm is working on - spanning tree of graph G
 > 504:		set TGraph [struct::graph]

 > 506:		#fill TGgraph with nodes
 > 507:		foreach n [$G nodes] {
 > 508:			$TGraph node insert
 > 509:		}
 > 510:		#fill TGraph with arcs
 > 511:		foreach e $T {
 > 512:			set v [$G arc source $e]
 > 513:			set u [$G arc target $e]
 > 514:			$TGraph arc insert $u $v $u$v
 > 515:			$TGraph arc setweight $u$v [$G arc getweight $e]
 > 516:		}
 > 517:				

See my comments above regarding lines 461-477.



 > 505:		set oddTGraph [struct::graph]

I moved this out of the block setting up TGraph to make the separation of the 
two graphs clearer and also that the block can be factored into a helper for 
clarity.

 > 518:		#################
 > 519:	
 > 520:		set oddNodes {}
 > 521:		foreach v [$TGraph nodes] {
 > 522:			if { [ expr {[$TGraph node degree $v] % 2} ] eq 1 } {

Superfluous nested use of expr, and bogus use of string equality operator 'eq' 
over regular (numeric) equality operator '=='.

Strings => 'eq'
Numbers => '=='

 > 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}] } {

Superfluous nested 'expr' command. Just use (...).

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

 > 531:					$oddTGraph arc insert $v $u $v$u
 > 532:				}
 > 533:			}
 > 534:		}
 > 535:		####
 > 536:		#		MAX MATCHING HERE!!!
 > 537:		####
 > 538:		set M {}		
 > 539:				
 > 540:		foreach e [$oddTGraph arcs] {
 > 541:			if { [lsearch $M $e] < 0 } {

Possible alternative:	![struct::set contains $M $e]

(The struct::set commands may have hashtable underneath, making the check faster).


 > 542:				$oddTGraph arc delete $e
 > 543:			}
 > 544:		}
 > 545:		
 > 546:		#operation: M + T
 > 547:		foreach e [$oddTGraph arcs] {
 > 548:			set v [$oddTGraph arc source $e]
 > 549:			set u [$oddTGraph arc target $e]
 > 550:			$TGraph arc insert $u $v $u$v
 > 551:		}
 > 552:		
 > 553:		#################
 > 554:		


 > 555:		set tourvar 0
 > 556:		isEulerian? $TGraph tourvar
 > 557:		
 > 558:		lappend result [$TGraph arc source [lindex $tourvar 0]]
 > 559:		
 > 560:		foreach i $tourvar {
 > 561:			set u [$TGraph arc target $i]
 > 562:			
 > 563:			if { [lsearch $result $u] < 0 } {
 > 564:				lappend result $u
 > 565:			}
 > 566:		}
 > 567:		
 > 568:		return $result
 > 569:		
 > 570:	}

Missing: Deletion of the temporary graph TGraph. This is a memory leak.
	Ditto missing deletion of oddTGraph.

Also, identical to the end of MetricTravelingSalesMan (MTS), worthy of putting 
into a common helper command for both.

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

(Yes, you mentioned this in your mail, however that was a bit low-level a 
description and I had not seen the code yet).



>> I'm writing to clear some matters about Christofides Algorithm:
> 
> Ok. Note, please update the algorithm status info in the timeline at 
> http://wiki.tcl.tk/23203
> 
>> I implemented it with a empty space for MaxMatching use. It still needs 
>> some refactoring but I want to clear some things first.

I agree that the last part of MTS and Christofides, i.e. construction of euler 
tour and hamilton cycle can be put into a helper command common to both.



>>  
>> Both 2-approximation algorithm and Christofides uses some similar steps 
>> but I thought it's not worth to divide them into procedures - this way 
>> it looks more clear and intuitive IMHO.
> 
> I see. Can't comment on that yet, will do after I had my look through the new code.

After seeing the code I believe the opposite to be true.


And some of the operations, like M+T, look like they could be of very general 
use, and maybe something fro th graph structure itself. We can postpone that 
however. This also ties a bit in Lars's message about possible functional 
groups, which I still haven't answered.



>>  
>> Next update - MAX-CUT. I want to catch up with timeline, but I'm still 
>> working on those TSP too.

Andreas.

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

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

Michał Antoniewski wrote:
> Hello.
>  
> I'm writing to clear some matters about Christofides Algorithm:

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

> I implemented it with a empty space for MaxMatching use. It still needs 
> some refactoring but I want to clear some things first.

Ok, I will have a look.

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

 > and then
> working on complete graph - those high costing added edges won't be 
> taken under consideration in finding optimal tour. Would you like to 
> handle those graphs at the beginning of procedure or just assume we get 
> complete graph at input?

> Now it is working, assuming that graph is complete but I can add this 
> feature - I think it is good idea.

Having the code handling non-complete graphs automatically is likely a major 
convenience for users of the command.


> Christofides implementation:
> It uses some graphs: firstly it creates minimum spanning tree graph 
> (TGraph), next is graph for MAx MAtching created by nodes with odd 
> degree from TGraph (oddTGraph). Then oddTGraph is changed to have only 
> edges we need to add to TGraph, and in next step we do M + T, so TGraph 
> gets new edges created by MaxMatching to assure its eulerian. The rest 
> goes like before.
>  
> As max matching is not availible yet I'm testing it by placing correct 
> values returned by max-matching, and checking if all code paths work 
> good. I think for now good idea would be to implement some greedy 
> max-matching, which can be helpful to place some test code (Graphs for 
> tests are ready).

How complicated is the max-matching ? Which is an indirect way of asking, how 
much effort would have to be put into implementing it ?


>  
> Both 2-approximation algorithm and Christofides uses some similar steps 
> but I thought it's not worth to divide them into procedures - this way 
> it looks more clear and intuitive IMHO.

I see. Can't comment on that yet, will do after I had my look through the new code.

>  
> Next update - MAX-CUT. I want to catch up with timeline, but I'm still 
> working on those TSP too.

Andreas.

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

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

> Ok.
>  
> Next update will be on Sunday - both TSP algorithms, implementation + 
> tests.

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.

> Considering approximation algorithms there are some inconvenient cases 
> about testing. For example, when I was trying to perform tests showing 
> case with Max Approximation factor, it strongly depends of what 
> algorithms ( which approximation algorithms use in their implementation 
> ), are going to return, e.g. in 2-approximation algorithm for TSP - when 
> we create input graph that is tight example, it will give the worst 
> solution, if the spanning tree found by for example Prim Algorithm will 
> have a proper look. Hence, for graphs I tested it found sligthly better 
> solutions.

Can you explain this in shorter sentences ? I tried to read and understand it 
several times and keep getting confused. Likely the problem is on my side, it 
is Monday morning, I did not sleep that well, my brain is buggered.

> Of course those Tight Example graphs, should and will be taken into 
> account in documentation.
>  
> About finding spanning tree - should there be option where user can 
> specify, if he wants use kruskal or prim to find minimum spanning tree? 

So the approximation algorithm is finding a spanning tree as part of its work ?

> It would make tests more resistant to changes, for example changing 
> spanning tree algorithm in implementation won't make all tests crush.

My understanding here is that by making the spanning tree algorithm STA used by 
the approx algorithm AA a configurable option of AA you can use both STAs we 
have in the tests of AA and thus make sure that the results are not influenced 
by the choice of STA ?


> 2-approximation algorithm is done. Christofides algorithm uses in it's 
> implementation Max Matching algorithm so I'm trying to simulate it for 
> now, as Max Matching implementation is placed in last week of the 
> timeline.

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 was thinking about implementing, only for now, greedy Max
> Matching but it doesn't return optimal solution, so it will decrease 
> good approximation of Christofides ( 3/2 ).

Another option would be to move Christofides back in the timeline after the 
Max-Matching and then move some other algorithm to the free spot.

I see from the most recent mail (I got today) that you have chosen to do 
Christofides, and faking the results you need from max-matching. Certainly also 
a way forward, with the understanding that Christofides needs re-checking when 
we have the actual max-matching implementation in Week 9+

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 ?



~~~
(Ad *) I could now with our IMAP system, if I were to install Thunderbird at 
home. Except that at home I do wish to be away from work. Note here that the 
GSoC mentoring does not count as work, that is something I can do at home as 
well, and during the weekend.

Andreas.

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

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

KATO Kanryu wrote:
> If you have a hard time to describe/manipulate graph data,
> do you use the huddle library?
> 
> I use this for the yaml library :)

I am not sure what you are thinking of here. If this is about the serialization 
of a graph structure for storeage and/or transfer, then huddle certainly a 
possibility, among others, like various XML notations.

However, we are here talking about the manipulation of graphs in memory, to 
compute things like distances between nodes, and "standard" representations, 
like Adjacency matrices and lists. I do not see how huddle could of use for 
that. It is, as far as I understand it, a helper for serialization.

Andreas

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

[KATO K. <k.k...@gm...>]

If you have a hard time to describe/manipulate graph data,
do you use the huddle library?

I use this for the yaml library :)

Ciao!

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

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

Andreas Kupries wrote:
> Now, I noticed that you changed the tests for adjlist a bit. It seems that the 
> results did not change in their essence, but only in the order nodes were 
> sorted in the various (sub)lists, right ?
> 
> In other words the changed results are in the same equivalence class as the 
> previous ones. There is no significant difference between
> 
> 	{n1 {n2 n3} n2 n1 n3 n1}
> and	{n2 n1 n1 {n3 n2} n3 n1},
> 
> just order, which is irrelevant for our dictionaries.
> 
> This is another issue often seen with test suites. That we check results for 
> exact identity, causing the rejection of perfectly correct results because they 
> are not exactly identical to whatever the previous algorithm created as its result.
> 
> 
> This was particular seen in test suites, here in Tcllib, when the Tcl core went 
> from 8.4 to 8.5. The hash table implementation of the core changed in that 
> transition, causing the results of 'array get' and 'array names' to change, 
> i.e. elements were returned in a different order. This tripped all the 
> testsuites which were not prepared to handle the equivalence class of correct 
> results and tested exactly instead.
> 
> The solution we implemented was to 'lsort' and 'dictsort' (*) the results of 
> the tested commands, projecting all results in an equivalence class to a 
> canonical form for that class. This canonical form can then be tested for exactly.
> 
> For the two adjlist algorithms you implemented it was simply details in the 
> implementation which changed the order.
> 
> I do not believe that we have to update the testsuite right now to take this 
> possibility into account, however please be aware this in the future.

And as a very concrete example I ran the testsuite of modules/struct, with the 
critcl implementation of struct::graph active (*), here is an excerpt:

==== graphop-gcritcl-scritcl-stcritcl-qcritcl-BellmanFord-1.9 BellmanFord, some 
weights set to 0 FAILED
==== Contents of test case:

         SETUP_PARTIALLYZEROWEIGHTED
         set result [struct::graph::op::BellmanFord mygraph node1]
         mygraph destroy
         set result

---- Result was:
node4 1 node3 0 node2 0 node1 0
---- Result should have been (exact matching):
node2 0 node3 0 node4 1 node1 0
==== graphop-gcritcl-scritcl-stcritcl-qcritcl-BellmanFord-1.9 FAILED

The result is correct, it simply presents the nodes in a different order.
For this simple data structure (dictionary) our projection to canonical
can be done by the helper 'dictsort', i.e. by changing

	set result [struct::graph::op::BellmanFord mygraph node1]
to
	set result [dictsort [struct::graph::op::BellmanFord mygraph node1]]

and changing the expected result to
	{node1 0 node2 0 node3 0 node4 1}
i.e. sorting it.

==========================================================
NOTE:
	This is _not_ a request to fix the testsuite now.
	I rather prefer to catch up on our timeline a bit
	This is polish, and can be done at/near the end.
==========================================================

~~~
(*) It is an implementation of struct::graph in C, and part of the differences
     to the Tcl implementation is a the changed order of nodes/arcs returned by
    [G nodes], [G arcs], etc.

Andreas

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

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
>> Update 2: Floyd-Warshall Algorithm.
>>  
>> Implementation + tests.
>>  
>> Possible extension can be enabling option to use Floyd-Warshall's as 
>> negative-cycle finder. Now it finds those cycles occurances and throws 
>> an error - the same as previous algorithms.
> 
> Will look into this either in the afternoon, or tomorrow.
> Updated the wiki timeline info.

The code and tests look good.


Andreas.

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

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
> 
>> Update 1 (Revision 12):    New version of Adjacency List.
>>  
>> What's new:
>> - changed the implementation considering your regards - now undirected 
>> case is simpler
>> - lsearch isn't used now  --> lsort
>> - and other lesser changes.
>>  
>> You were of course right about implementation, now it looks much 
>> simpler.

Sometimes you have to just look at things from a slightly different angle.

Ok, yes, that looks much nicer. And it should be easier to understand as well.

Now, I noticed that you changed the tests for adjlist a bit. It seems that the 
results did not change in their essence, but only in the order nodes were 
sorted in the various (sub)lists, right ?

In other words the changed results are in the same equivalence class as the 
previous ones. There is no significant difference between

	{n1 {n2 n3} n2 n1 n3 n1}
and	{n2 n1 n1 {n3 n2} n3 n1},

just order, which is irrelevant for our dictionaries.

This is another issue often seen with test suites. That we check results for 
exact identity, causing the rejection of perfectly correct results because they 
are not exactly identical to whatever the previous algorithm created as its result.


This was particular seen in test suites, here in Tcllib, when the Tcl core went 
from 8.4 to 8.5. The hash table implementation of the core changed in that 
transition, causing the results of 'array get' and 'array names' to change, 
i.e. elements were returned in a different order. This tripped all the 
testsuites which were not prepared to handle the equivalence class of correct 
results and tested exactly instead.

The solution we implemented was to 'lsort' and 'dictsort' (*) the results of 
the tested commands, projecting all results in an equivalence class to a 
canonical form for that class. This canonical form can then be tested for exactly.

For the two adjlist algorithms you implemented it was simply details in the 
implementation which changed the order.

I do not believe that we have to update the testsuite right now to take this 
possibility into account, however please be aware this in the future.

Maybe not as easy to write a specialized sorting routine which collapses 
equivalence classes of results into a canonical form, but after such is done 
algorithm changes may not require testsuite changes because of leaked 
implementation details.


(*) And custom sorting commands for more complex data structures.

Andreas.

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

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

Michał Antoniewski wrote:
> Update 2: Floyd-Warshall Algorithm.
>  
> Implementation + tests.
>  
> Possible extension can be enabling option to use Floyd-Warshall's as 
> negative-cycle finder. Now it finds those cycles occurances and throws 
> an error - the same as previous algorithms.

Will look into this either in the afternoon, or tomorrow.
Updated the wiki timeline info.

> Next updates are TSP algorithms.
>  
>  
> Best Regards,
> Michał Antoniewski

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

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

Michał Antoniewski wrote:

Administrivia: I reworked the timeline at the bottom of 
http://wiki.tcl.tk/23203 into a table, and added a status column where we can 
track what is done, what is being worked on, etc.

I have filled in the data for the previous weeks, as far as I knew it.
Please check my edits for inaccuracies.

We also have to put the graph coloring algorithms we wish to implement instead 
of the matrix multiplication method into the timeline.

> Update 1 (Revision 12):    New version of Adjacency List.
>  
> What's new:
> - changed the implementation considering your regards - now undirected 
> case is simpler
> - lsearch isn't used now  --> lsort
> - and other lesser changes.
>  
> You were of course right about implementation, now it looks much 
> simpler.

I would not say 'of course'. I can be wrong as well.
I will have a look either this afternoon, or tomorrow.


 > However, now I've got one concern about weighted version.
> Suppose we've got a graph G with edges from node A to B and B to A, but 
> with different wages.

> For that case, there is a question: how the AdjacencyList should look 
> when using -weights option:
> 1) should it place for each node two occurances of an edge with 
> different weight
> 2) trying to pick one edge looks like bad solution....
> 3) graphs such as G are considered as wrong.

To me (1) looks like the right solution. What does adjacency list look look 
like if the we have such edges, with identical weight ?

Similarly, what does the result look like for parallel edges A -> B of some 
and/or different weight ?

> My call would be first solution and current version works like this:
> - if we got edges edgeAB and edgeBA between nodes A and B, with weights 
> successively X and Y, for node A there will exist {{B X} {B Y}} and for 
> node B  {{A X} {A Y}} in their solutions. When X = Y, it's considered as 
> a single edge.

Ok.

> Pros: it prevents from cutting the set of possible graphs for procedure.
> Cons: - a bit unusual look of AdjacencyList (due to but option -weights 
> is supplementary, so maybe it's not bad.
> - inaccuracy: if for different weights we've got both arcs, shouldn't 
> there be also both arcs in solution for cases with same weights?

It might be more consistent, yes. I.e. when we have -weights, represent all 
edges without special cases.

> So the main question is, do we make a restriction for procedure 
> AdjacencyList to work only with simple graphs ( graphs without loops and 
> doubled edges) - which apparently in my opinion isn't so bad, as most 
> graphs considered are simple graphs.
> Or we consider those double edges, which isn't a problem as well.

I would prefer to handle loops and (anti-)parallel edges. I am erring on the 
side of having more information in the result rather than less. An algorithm 
using adjacency information and needing/wanting less can then reduce as it sees 
fit. Whereas if it needs information and doesn't have it it is stuck.

Andreas.

[Tcllib-devel] BWidget bugfix and development

[Harald O. <Har...@El...>]

Dear community,

This is an anouncement how BWidget may develop and how interested people
may help.

Current state:
- Jeffrey Hobbs and Damon Courtney have maintaned BWidget and are
  available for support
- I have started integrating bug fixes and small features reported on
  sourceforge into current CVS
- Johann Oberdorfer has sent me a ttk extended version of BWidget
- I have read on clt, that there are quite a few people extending
  BWidgets with ttk abilities.

Proposed steps and timeline:

1) Bug fixing of present BWidget
   (in June 2009)

- I will review all bugs and integrate them eventually into cvs
- Release at end of June of BWidget 1.9 (Bug fix release)
Tasks for the Cummunity:
- please be shure that any bug you have found is reported on sourceforge

2) Move current BWidget to use ttk widgets if available
   (July and August 2009)

- Review and Integrate the patches of Johann
- Review and Integrate eventually other patches
- Release a BWidget 2.0 release end of August 2009.

This release should:
- still run with older tcl/tk
  (I think, BWidgets runs with tcl/tk 8.0 at the moment)
- use ttk widgets if required
- be mostly compatible but for example remove configuration
  options, which are now themed

Tasks for the Cummunity:
- Please publish any patches (in any form) on sourceforge as patches.
  You may just zip your files but please publish them there.

  Johann, please do this with your version, if it is ready.
- Please comment any patches and help me integrating them

Please comment and discuss on the tcllib-devel mailing list.

Regards,
Harald

Re: [Tcllib-devel] BWidget Bug Fixing Help

[Harald O. <Har...@El...>]

Damon Courtney schrieb:
>> Thanks very much for triaging the bwidgets bug area.  I am cc'ing
>> Damon, who had assisted in maintenance before, and tcllib-devel in
>> general to let them know you have been added in and will be poking
>> around that area.  If anybody else has the time and will to assist
>> Harald, that would be appreciated.
>>
>> When you feel BWidgets needs a "release", ping back and we'll work on
>> cementing one.
> 
> I can help with this.  I haven't looked at the BWidget code in a long
> while, but I'm still very familiar with all of it and how everything
> comes together.  Just let me know if you have any questions, or if you
> need some advice or help on the release.  Like Jeff says, when you think
> you're ready for a release, we'll hammer one together.  Lords knows it
> could use one. 0-]
> 
> Damon

Hi Damon, Hi Jeff, hi community,
thank you, so I may start.
I would also appreciate if you monitor my activities.
I am new in this field.
I will contact you in case of any ideas.

Harald

Re: [Tcllib-devel] BWidget Bug Fixing Help

[Damon C. <da...@tc...>]

> Thanks very much for triaging the bwidgets bug area.  I am cc'ing  
> Damon, who had assisted in maintenance before, and tcllib-devel in  
> general to let them know you have been added in and will be poking  
> around that area.  If anybody else has the time and will to assist  
> Harald, that would be appreciated.
>
> When you feel BWidgets needs a "release", ping back and we'll work  
> on cementing one.

I can help with this.  I haven't looked at the BWidget code in a long  
while, but I'm still very familiar with all of it and how everything  
comes together.  Just let me know if you have any questions, or if you  
need some advice or help on the release.  Like Jeff says, when you  
think you're ready for a release, we'll hammer one together.  Lords  
knows it could use one. 0-]

Damon

Re: [Tcllib-devel] BWidget Bug Fixing Help

[Jeff H. <je...@ac...>]

Hi Harald,

On 09/06/2009 8:42 AM, Harald Oehlmann wrote:
> Jeff Hobbs schrieb:
>> On 07/05/2009 1:35 AM, Harald Oehlmann wrote:
>>> in a recent discussion about BWidget, you spoke about little
>>> resources to fix bugs or accept patches in BWidgets.
>>>
>>> Could I help here ? I could do administrative, code and
>>> testing tasks on windows and linux.
>> It is always helpful if someone triages the bugs list, weeded out the
>> ones that are no longer reproducible, or confirming more clearly the
>> vaguely worded bugs with reproducible steps.
>>
>> However the harder part would be the general maintenance and fixes.
>> Kevin Walzer already looked into it and decided that indeed the core
>> coding of BWidgets is rather complicated.
>>
>> However, it should still have some life in it should you choose to do a
>> bug triage.
> 
> I started the bug triage last week.
> There are now 3 patches which might just fix issues.
> 
> What would be a good way to apply patches and finally maintain the code.
> 
> Could you grant me privilegies to do so or is there another way ?

Thanks very much for triaging the bwidgets bug area.  I am cc'ing Damon, 
who had assisted in maintenance before, and tcllib-devel in general to 
let them know you have been added in and will be poking around that 
area.  If anybody else has the time and will to assist Harald, that 
would be appreciated.

When you feel BWidgets needs a "release", ping back and we'll work on 
cementing one.

Thanks again,

Jeff

[Tcllib-devel] struct::graph API functional groups

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

The struct::graph::op manpage says

    Despite being a companion the package is not directly
    dependent on struct::graph, only on the API defined by
    that package. I.e. the operations of this package can be
    applied to any and all graph objects which provide the
    same API as the objects created through struct::graph.

Now, I suppose this is meant to cover things like cgraph, i.e., C 
reimplementations of struct::graph, but one could also consider 
applying it to things which provide a struct::graph-ish interface even 
though they don't implement all of it. Such a development could be 
furthered if the struct::graph API was split up in smaller pieces, 
since providing all of it is quite a mouthful, and few (if any) 
struct::graph::op commands are likely to exercise all of it.

One basic division that can be made is into broad areas of functionality:

   * Graph structure
   * Attributes, which can be futher split up into:
        - arc attributes
        - node attributes
        - overall graph attributes
   * Weight (which has a separate API, although it is mostly
             like an arc attribute)
   * Object nature (assign, reverse assign, etc.)

A second division which I find it useful to make is that between 
mutating and functional operations, i.e., operations that change the 
graph object versus those that don't, since many graph-ish objects 
would really be images of something else, and thus not necessarily 
support being modified at the graph level. For example, a (partial) 
latin square can be viewed as a (partial) edge-colouring of a bipartite 
graph, but adding an edge between two vertices in the same partition 
doesn't correspond to any operation that can be performed on the latin 
square, so there's no sensible way for a latin square to support the 
"arc insert" operation.

According to these categories, the struct::graph API divides as follows:


Graph structure:
================

Functional:
-----------
graphName arc exists arc
graphName arc source arc
graphName arc target arc
graphName arcs  ? -filter cmdprefix ?   ? 
-in|-out|-adj|-inner|-embedding node node... ?
graphName node degree  ? -in|-out ?  node
graphName node exists node
graphName node opposite node arc
graphName nodes  ? -filter cmdprefix ?   ? 
-in|-out|-adj|-inner|-embedding node node... ?
graphName walk node  ? -order order ?   ? -type type ?   ? -dir 
direction ?  -command cmd

Mutating:
---------
graphName arc delete arc  ? arc ... ?
graphName arc flip arc
graphName arc insert start end  ? child ?
graphName arc rename arc newname
graphName arc move-source arc newsource
graphName arc move-target arc newtarget
graphName arc move arc newsource newtarget
graphName node delete node  ? node... ?
graphName node insert  ? node... ?
graphName node rename node newname
graphName swap node1 node2


Arc attributes:
===============

Functional:
-----------
graphName arc attr key
graphName arc attr key -arcs list
graphName arc attr key -glob globpattern
graphName arc attr key -regexp repattern
graphName arc get arc key
graphName arc getall arc  ? pattern ?
graphName arc keys arc  ? pattern ?
graphName arc keyexists arc key
graphName arcs  ? -key key ?   ? -value value ?

Mutating:
---------
graphName arc append arc key value
graphName arc lappend arc key value
graphName arc set arc key  ? value ?
graphName arc unset arc key


Node attributes:
================

Functional:
-----------
graphName node attr key
graphName node attr key -nodes list
graphName node attr key -glob globpattern
graphName node attr key -regexp repattern
graphName node get node key
graphName node getall node  ? pattern ?
graphName node keys node  ? pattern ?
graphName node keyexists node key
graphName nodes  ? -key key ?   ? -value value ?

Mutating:
---------
graphName node append node key value
graphName node lappend node key value
graphName node set node key  ? value ?
graphName node unset node key


Graph attributes:
=================

Functional:
-----------
graphName get key
graphName getall  ? pattern ?
graphName keys  ? pattern ?
graphName keyexists key

Mutating:
---------
graphName append key value
graphName lappend key value
graphName set key  ? value ?
graphName unset key


Weights:
========

Functional:
-----------
graphName arc getunweighted
graphName arc getweight arc
graphName arc hasweight arc
graphName arc weights

Mutating:
---------
graphName arc setunweighted  ? weight ?
graphName arc setweight arc weight
graphName arc unsetweight arc


Object:
=======

Functional:
-----------
graphName serialize  ? node... ?

Mutating:
---------
graphName = sourcegraph
graphName --> destgraph
graphName deserialize serialization
graphName destroy


As stated above, quite a mouthful! There are however ways to reduce the 
burden.

One thing that can be observed is that attribute management is mostly 
orthogonal to the graph structure; each node or arc is a key to some 
dictionary of attributes, but it matters very little that this key is 
something in the graph. Hence it would be possible to define e.g. a 
snit::type A that adds attribute functionality to a "naked" 
(attribute-less) graph G it owns as a component; methods that care 
about attributes would be handled in A, whereas methods targeting the 
graph structure would be delegated to G.

As an example of such a "naked" graph, here is an ensemble implementing 
(most of) the functional graph structure group for the Petersen graph 
(with 2-subsets of {1,2,3,4,5} as nodes, and pairs of nodes as arcs, 
two nodes being adjacent iff they are disjoint as sets):


namespace eval Petersen {
     namespace export {[a-z]*}
     namespace ensemble create

     namespace eval node {
         namespace export {[a-z]*}
         namespace ensemble create

         proc exists {name} {
             expr {[string match {[1-5] [1-5]} $name] &&\
               [lindex $name 0] < [lindex $name 1]}
         }
         proc degree {args} {
             expr {[llength $args]==1 ? 6 : 3}
         }
         proc opposite {node arc} {
             lindex $arc [expr {[lindex $arc 0] eq $node}]
         }
     }

     proc Disjoint {L1 L2} {
         expr {[llength $L1] + [llength $L2] ==\
           [llength [lsort -unique [concat $L1 $L2]]]}
     }

     proc arc {op name} {
         switch -- $op "source" {
             lindex $name 0
         } "target" {
             lindex $name 1
         } "exists" {
             expr {
                 [string match {{[1-5] [1-5]} {[1-5] [1-5]}} $name] &&
                 [lindex $name 0 0]<[lindex $name 0 1] &&
                 [lindex $name 1 0]<[lindex $name 1 1] &&
                 [Disjoint {*}$name]
             }
         }
     }

     proc nodes {args} {
         if {[llength $args]} then {
             return -code error\
               "Option \"[lindex $args 0]\" not implemented (sorry)"
         }
         set res {}
         foreach i {1 2 3 4 5} {
             foreach j {1 2 3 4 5} {
                 if {$i<$j} then {lappend res [list $i $j]}
             }
         }
         return $res
     }

     proc arcs {args} {
         if {[llength $args]} then {
             switch -- [lindex $args 0] "-in" {
                 set fromL [nodes]
                 set toL [lrange $args 1 end]
             } "-out" {
                 set fromL [lrange $args 1 end]
                 set toL [nodes]
             } "-inner" {
                 set fromL [lrange $args 1 end]
                 set toL [lrange $args 1 end]
             } default {
                 return -code error\
                   "Option \"[lindex $args 0]\" not implemented (sorry)"
             }
         } else {
             set fromL [nodes]
             set toL $fromL
         }
         set res {}
         foreach u $fromL {
             foreach v $toL {
                 if {[Disjoint $u $v]} then {
                     lappend res [list $u $v]
                 }
             }
         }
         return $res
     }
}


Missing here is only the "walk" method and some options on the "nodes" 
and "arcs" methods, since dotting all the i's would take us too far 
astray (also, one can make a similar argument about having a wrapper 
provide those). Additionally missing are the mutating parts of the API, 
but that's kind of implicit, since once you start modifying the 
Petersen graph it won't be the Petersen graph anymore!


So where am I going with this?

Well, I was thinking that /if/ a partition of the struct::graph API was 
made /and/ it was documented for each command of struct::graph::op 
which parts it needed /then/ chances would be better that something 
merely struct::graph-ish (like the [Petersen] above) could make use of 
these commands. I have, at times, toyed with an idea for constructing a 
layout that at each step would involve a strongly connected components 
computation -- said components would then be in a graph implicitly 
constructed from the data structure representing a partial layout, and 
thus not sensibly supporting the whole struct::graph API, but the graph 
would change several times as the layout was being filled in -- so in 
order to rely on [struct::graph:op::tarjan] I would have had to know 
(preferably from documentation rather than source-diving) that it could 
make do with the methods I can provide.

OTOH, it can probably be argued that pretty much any struct::graph::op 
command has complexity at least O(V)+O(E), so an initial step copying 
the entire graph into a [struct::graph] wouldn't be dominant anyway. 
But it's not always the asymptotically dominant term that hurts you...

Lars Hellström

Re: [Tcllib-devel] Graph Manip

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

Michał Antoniewski wrote:
> Hello.
>  
>  >>Using the following graph as example:
>  >>       A -(2)-> B -(-1)-> C
>  >>       A, B, C nodes
>  >>       2, -1 arcs weights
>  >>       no names for the arcs.
>  >>
>  >>       - so now, for graph G with N nodes:
>  >>             1.    "1 A" gives something like this:    { node1 
> .....                        nodeN }  { list of nodes adjacent to node1 
> } ......  >>{ list of nodes                        adjacent to nodeN   }
>  >>
>  >>      result = {A B C} {{B} {A C} {B}}
>  >>Is my understanding of your description correct ?
>  
> Hmmm, I meant something else. It was bad idea to send this description - 
> I should send the code at once.

Sometimes is code is easier to understand, correct. Even so, a good non-code 
description is vital as well, for the documentation.


> Actually, regarding dictionary usage - I wanted to do this just like you 
> said using dicts from the beginning, but on the other hand procedure 
> toAdjacencyMatrix is done using lists and I thought both procedures 
> should have similar return values. It would be more suitable for users 
> and I thought they shouldn't differ a lot.
>  
> In new version I did Adjacency List using dictionaries - it's surely 
> better solution.

Note that toAdjacencyMatrix returns (by definition) a matrix. For that a 
nestetd list of lists is a usable representation.

For adjacency _lists_ the dictionary form of a nested list-representation 
matches our desires better.

While making return values is similar or identical is a worthwhile goal we 
always also have to balance it against the suitability of the representation we 
are copying or mimicking. Using an unsuitable representation just for the sake 
of similarity will hurt us in the long run.


> About options:
> I searched for actual potential usages in algorithms of -edges option I 
> mentioned before and ..... it's hard to find anything important. It 
> could be useful in some cases but I think it's not useful enough.

Ok.

 > So, I
> erased it from the code. Now there are two options -directed ( for 
> directed graphs ) and -weights ( for weighted graphs ).

Ok.

> Tests for Adjacency List:
>      I've created some new graphs and test cases for them (and others 
> created before):
>          - firstly tests considering missing args...
>          - logical tests: e.g. lack of weights, wrong options.
>          - proper returning values: besides standard tests ( proper 
> option usage, cases with special graphs e.g. no edges and others) also 
> some cases directly concerning implementation, e.g. case when we have 2 
> edges between 2 nodes in directed graph, checking proper usage when arcs 
> are auto-named ( it's important case when considering all possible paths 
> that code can go through ) and different edge weight cases.

> So, that's all for now. I've got pretty crazy time at university now, 
> but I'll try to set at SVN Floyd-Warshall's implementation and maybe 
> some new tests tomorrow.

Ok. Note, please do not burn yourself out to force adherence to the schedule. 
Relaxation time is important as well. And a project like GSoC is a good 
real-life experience showing where problems in a project can come from, 
including outside factors.

 > About docs, I would like to catch up with it
> later, if that's okay with you.

Yes.

> You can find new tcllib at ver4 folder and I prepared different file 
> with toAdjacencyList and easy graph example just to run it and look what 
> exactly it returns ( Trunk/ver1/AdjacencyList ).
>  
> I'm using those verX folders because that way it's more clear for me. 
> When having those assembla revisions (they note every single update )  I 
> won't remeber which number exactly was which update and when I need to 
> find something from any version before, I've got it at one place ( on my 
> local repository too ) nicely arranged in my folders:) 

I see. That sounds to me that you are using the folders as a means of 'tagging' 
revisions, and as replacement for log messages.

Please have a look at
	http://svnbook.red-bean.com/

This is an online book about subversion, titled
	'Version Control with Subversion'.

The 2 chapters I believe are most likely relevant to your problem are

(1)	http://svnbook.red-bean.com/en/1.5/svn.tour.history.html
	Examining History
and
(2)	http://svnbook.red-bean.com/en/1.5/svn.branchmerge.tags.html
	Tags

The remainder of the book should be useful however as well.

... Ok, I wanted to ask if you are using 'log messages', but then looked back 
at the notification messages sent by assembla and I now see that it says 'No 
message'. Missing that was an oversight on my side, my apologies.

Not using log messages is a bad idea. The messages entered for each commit will 
help you, and any future maintainer to see what was happening in the repository 
at the high level.

See	svn help commit

for the syntax to enter log messages.

Using these the output of 'svn log' becomes actually useful. Together with tags 
you will have everything to not need to remember what was in each 
update/commit, as you can ask svn for the information.

As examples for log messages see the file 'ChangeLog' in the struct directory, 
and all the other packages in Tcllib. This should give you an idea of what is 
looked for in such messages.

~~~~

On to the code (revisions 10, 11) ... Your implementation of the undirected 
case is a bit complex because you are handling all adjacent edges in one loop, 
and then have to use 'G arc source|target' to switch how to handle the edge.

Consider splitting this loop into two, handling the incoming and outgoing edges 
separately.

Another trick you could use to simplify your life here is 'dict lappend' (See 
http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M17).

How is that useful ? Instead of collecting the adjnodes in your loop and then 
setting them all in a single 'dict set' at the end you can add them directly in 
the loop.

Actually ... Having this operation it might be possible to generate the whole 
result by iterating over the edges alone, instead of the vertices and then 
edges per vertex, I think.

Roughly:
	foreach e [$G arcs] {
		set va [G arc source e]
		set vb [G arc target e]

		dict lappend AdjacencyList $va $vb
		dict lappend AdjacencyList $vb $va
	}

Hm ... Ok, we need one loop over the nodes to initialize the dict first, so 
that we capture nodes without neighbours as well ...

	foreach v [G nodes] {
		dict set AdjacencyList $v {}
	}

Not sure about multiple edges between two nodes ... Of course, as you provided 
a test case for that any reworking of the implementation can be quickly checked.

Other things I noted. In

    if { [lsearch $adjNodes [$G arc source $e]] eq -1 } {
        lappend adjNodes [$G arc source $e]
    }

the 'eq -1' is bad. 'eq' is string comparison, -1 is a number. For this '==' is 
the better operator, using '< 0'.

Further, the whole searching likely makes things O(V^2) ... A different way of 
achiving the same things:

(1)	Just lappend nodes without care for duplicates.
	At the end run 'lsort -unique' over the adjacency lists in the
	dictionary to remove all duplicates, if any.

(2)	package require struct::set
	struct::set include adjNodes $v

	The 'set add', especially the C version uses a hashtable underneath,
	making duplicate checks asymptotically O(1) (lsearch is O(n)).

Last, if you have lots of repeated uses of the same large expression, say

	[list [$G arc source $e] [$G arc getweight $e]]

then it is sensible to store the value in a variable and to just refer to that 
later on, instead of computing the data multiple times.

~~~~

The shaw.ca address I added is my home address, should you wish to talk to me 
over the weekend.

Andreas

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Andreas Kupries skrev:
> Lars Hellström wrote:
>> As an example, one kind of manipulation that seems useful (especially 
>> when you get to the flow algorithms, in a couple of weeks) would be an 
>> operation that splits every vertex in two, where one part receives the 
>> incoming edges and the other gets the outbound edges, with a new edge 
>> from in-part to out-part. (This is a classical trick for reducing flow 
>> problems with capacities on vertices to flow problems with capacities 
>> only on the edges.)
> 
> I would put such an operation into a graph::ops procedure, and export it 
> from the ops package. I.e. a helper, but valuable enough to be a regular 
> public operation. Which of such helpers we then move to the foundation 
> class, i.e. struct::graph, can then be discussed separately.

Well, although the operation is useful, I'd have to add that an 
operation which does exactly this feels very much like a lame special 
case of some more general "insert gadget" operation, and it is really 
this general operation that should be implemented. The catch is that 
there's no generally accepted formalism (that I know of) for describing 
the very intuitive operation of replacing every vertex by some gadget. 
(Actually, I have done some work on such matters -- see 
http://abel.math.umu.se/~lars/diamond/paper-gr.pdf, Section 4 -- but 
that approach is far from immediately applicable to struct::graph.)

>>>  > As it is in
>>>> timeline I started with Bellman-Ford and Johnson's.
>>
>> In general, I think time is better spent implementing one algorith 
>> each for doing A, B, and C, than three different algorithms for doing 
>> A, but YMMV.
> 
> The three distances algorithms (dijkstra, bellman-ford, johnson) have 
> different time complexities and limitations. As such also different 
> areas of application, depending on the graphs to be expected as inputs. 

Yes, but each of them solves maybe 80% of all graph distance problems 
users will pose. The question is then whether one prioritises the 
remaining 20% of this problem class A, or the first 80% of some other 
problem class B...

> And automatic selection based on the input is often not possible.

And usually a Bad Idea, even when it is possible.

> Information like this, i.e. raw time complexities and limitations, and 
> then at the higher level which algorithm is better in what situation is 
> definitely something we have to put into the documentation.
> 
> 
>> Also, I find the rule applied in struct::graph::op about naming 
>> commands after algorithms that is a bit curious. There's certainly a 
>> point in doing so when you've got many algorithms for doing the same 
>> thing, but on the other hand it renders code employing these commands 
>> more obscure.
> 
> Maybe. It depends a bit on the audience. Assuming that the reader knows 
> graph theory I see now problem.

Well, if one is regularly teaching a graph theory course that covers 
these algorithms, then I suppose one immediately knows Prim from 
Kruskal, but otherwise I'm not so sure. Often one remembers algorithms 
in vaguer terms, such as the edge- or vertex-oriented respectively 
algorithm for solving the problem in question -- when one remembers 
individual algorithms at all. A lot of the time, it is sufficient to 
recall for what problems a polynomial algorithm exists; sorting out the 
details can typically be delayed until one starts coding.

There is also the issue that case conventions can make the names harder 
to recognise. I recognise "kruskal" and "dijkstra" as names even in 
all-lower-case, but found "prim" and "tarjan" far more mysterious on 
first sight.

Another problem is that some persons have discovered several 
algorithms, and for those this naming scheme isn't unique anymore.

> Another thing using code can do is to 
> define aliases mapping from, for example, 'distance', to 'dijkstra'. 
> That location would then also be a good place for the user to comment on 
> why a specific algorithm was chosen, see above about that.

Yes. Furthermore it could be a good idea to have an overview section 
/before/ the long list of command descriptions. This section would be 
organised by topic (e.g.: paths, trees, network flows, connectivity, 
etc.) and mention what algorithms are available (preferably with 
hyperlinks to command descriptions).

> The kruskal and prim implementations are from last year's GSoC. Have to 
> check who wrote the docs. Might have been me, as part of the integration 
> into tcllib (The '08 operations were written outside of Tcllib first).
> 
>     As such this is not something to be done by Michal.
>     Not during the GSoC period. I am fine if he wishes
>     to do that after. By then however, I might have fixed
>     things already.
> 
> Can you (Lars) please go over the docs and file regular Tcllib bugs for 
> where you believe information is missing ?

Have filed some earlier today. Could be more on the way.

>> Also, regarding the API provided by struct::graph, I find it a bit 
>> curious that "weight" is singled out as a special property of arcs, 
>> with its own methods for setting, getting, and so on. I suspect a more 
>> practical approach for a higher level package like struct::graph::op 
>> would be that the weight was some attribute given to the arcs, and 
>> that a command for computing e.g. a shortest path would take as an 
>> argument (or option value) the name of the attribute to use as 
>> "weight" in this particular calculation.
> 
> This was also a decision made during GSoC 2008. I am not recalling 
> details at the moment. There should be something in my mail archives 
> however as I was involved, although not as primary mentor. For this I 
> however should have some mails.

Thinking a bit more about this lead me to the idea of dividing the 
struct::graph API into smaller functional groups, but that is getting 
so long that I'll write a separate mail about it.

Lars Hellström

Re: [Tcllib-devel] Graph Manip

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

Michał Antoniewski wrote:
> 
> Some remarks about Adjacency List:
>  
> For now I've done it like this:
>         -  user have 2 main options for adjacency list:
>               1.    listing each adjacent node for each node (DEFAULT - 
> 			classic form of Adjacency List) - let's call it "1 A"
>               2.    for each node: listing each edge for which that node 
> 			is a adjacent- let's call it "2 A"
>               3.    for both options (1 and 2) exists option considering 
> 			weights - let's call it "1 B" and "2 B"

How so ? ... Reading further, ok, you are adding the weight info into the result.

>               4.    additional option for recognising 
> 			directed/undirected graphs ( I tend to set directed as default )

Using the following graph as example:

	A -(2)-> B -(-1)-> C
	A, B, C nodes
	2, -1 arcs weights
	no names for the arcs.

>         - so now, for graph G with N nodes:
>               1.    "1 A" gives something like this:    { node1 ..... 
> 			nodeN }  { list of nodes adjacent to node1 } ......  { list of nodes 
> 			adjacent to nodeN   }

	result = {A B C} {{B} {A C} {B}}

Is my understanding of your description correct ?

If yes, would
	{nodeX {list of nodes adjacent to X} ...}

not be simpler ? In the terms of the example:

	result = {	A B \
			B {A C} \
			C B}

I.e. instead of two lists which are synchronized by index a single dictionary. 
It feels easier to process. Either with foreach {key value} ... or dict commands.

>               2.    "1 B" gives: { node1 ..... nodeN } { { nodeK 
> weightOfArc1->K }.....} .......  { {nodeL weightOfArcN->L} .... }

>        so for each node, there is a list of lists containing adjacent 
> node and weight of the regarding arc.

	result =	{A B C} {{{B 2}} {{A 2} {C -1}} {{B -1}}}
	?

Again a dictionary feels simpler:

	A {{B 2}} \
	B {{A 2} {C -1}} \
	C {{B -1}}

>  
>               3.    "2 A" gives: { {} node1 ..... nodeN } { node1 
> edgeK......edgeL } ......{ nodeN edgeH.......edgeM }
>  
>               4.    "2 B" gives: { {} node1 ..... nodeN } { node1 {edgeK 
> weight1-K }......{edgeL weight1-L} } ...

I am getting confused about the structure ... Because I do not understand where 
the {} before node1 comes from and why here node is in both lists.

>  
> Directed and undirected case is just, taking only edges where node is a 
> source in first case, and in latter taking all adjacent edges ( where 
> node is both source and target).


> Doubts:
> - is edge form ( 2A and 2B ) good idea? Mostly, it is used classic form 
> with node lists, but it can be some improvement to make availiable also 
> that form.

Do we have concrete algorithms needing the edge form ?
How complex would the generation of the edge forms be ? (timewise)

These are the two main factors to consider coming to my mind.

> - return value ...
>                for 1A and 1B - should (before each set of adjacent 
> nodes) there be placed a node to which next nodes are adjacent?
>                e.g. like this: { all nodes } { {node1} {node2 node3 
> node6} } ....

My understanding of this form is that you have a list of all nodes followed by 
a dictionary as I mentioned above. What is the reason for including a list of 
all nodes in the result ? Is that not implicitly the list of all keys in the 
dictionary ?

>  
> Actually, returns values can be quickly set at the end but for now, what 
> do you think of that organisation of AdjacencyList?

See all my thoughts and musing above ...

> Best Regards,
> Michał Antoniewski

Re: [Tcllib-devel] Graph Manip

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
>> Another update is available at assembla.

I have a question regarding your use of SVN.

I am noticing that you are creating a lot of verX directories,
with X in 1, 2, 3, ...

This feels odd, given that SVN is automatically handling the revisioning of 
files for you when you are commiting changes.

Can you explain the rationale/reason behind that to me ?

>> What's new:
>> - new test cases ( regarding your treatise about tests, I updated some 
>> missing cases )
>> - some of results ( for test cases ) moved into procedures - the bottom 
>> of XOpsSetup file, I wanted to stick with organisation given by XSetup 
>> file for "setup files".
>> - updated description of algorithms and code comments - graphops.tcl.
>> - corrected errors you noticed in last version.
> 
> Ok. Will review sometime today.

Looks good.

>>    -  However, I came up with option -filter ( it is used by other 
>> struct::graph procedures, for limiting the set of returned values e.g. 
>> nodes - this name will assure some logical conformity ), and $param is 
>> now $displaymode.
> 
> Hm. No comments regarding this yet, will have a look at the code first.

Ok, it is option -filter now, without any arguments. I though that you had 
added something which would take an argument, like the graph nodes/arcs methods 
and was confused how that would work.

It feels better than before, but not completely right. It is however a minor 
thing which we can change anytime later, and not worth losing time over now.
(We are getting into bikeshed territory 
(http://en.wikipedia.org/wiki/Color_of_the_bikeshed) I believe)

Andreas

Re: [Tcllib-devel] Graph Manip

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

Michał Antoniewski wrote:
> Another update is available at assembla.
> What's new:
> - new test cases ( regarding your treatise about tests, I updated some 
> missing cases )
> - some of results ( for test cases ) moved into procedures - the bottom 
> of XOpsSetup file, I wanted to stick with organisation given by XSetup 
> file for "setup files".
> - updated description of algorithms and code comments - graphops.tcl.
> - corrected errors you noticed in last version.

Ok. Will review sometime today.

> First of all, thank you for your treatise concerning tests - it has 
> surely well described approach to tests for all algorithms 

Thanks, glad that it was of help to you.

> implementations. So, in each of next steps, I'm going to stick to 
> black/white box testing principles.

>  >>So, if you now believe that writing tests for an algorithm takes at 
> least as much time as coding the algorithm, and often more time, then 
> you are completely right. It does.
>  
> Yeah, thats true:) I would even say that it takes a lot more time than 
> implementing, especially concerning easier implementations.

> This year, D. Richard Hipp had a lecture at my university and when he 
> said about proportions of test code and other code in SQLite 
> implementation... let's say I was a little bit amazed by this huge 
> disproportion :)

Heh.

sqlite is an extremely well tested piece of software
(http://sqlite.org/testing.html).

And Richard a very, very smart person. Miles ahead of myself.

>  >>Do you have web references about the algorithm, at wikipedia or other 
> website ?
> Yes, I found algorithm descriptions at wikipedia and placed into code. 
> As I'm mostly using Polish sites for theoretical info about graphs ( 
> I've got some favourites where I can find quickly everything I need :) ) 
> it's not a good idea to put those references. So, wiki websites in 
> English are used.

Thanks, and agreed that most of the audience will be lost on a Polish site.

> Identation:
>  >>May I ask what editor you use ?
> When I'm working on my notebook, I'm using Notepad++, so maybe that's 
> the cause.

Well, I do not know Notepad++ so I can't say.

 > Otherwise, I use Vim.

I seem to remember that VIM has a Tcl mode, or some such ...
Googled vim + tcl, found
	http://www.vim.org/scripts/script.php?script_id=1603

That is syntax highlighting however, not indenting ...

Aha, http://www.vim.org/scripts/script.php?script_id=178
says something about indenting.

Note: While I found these files I have not used them in any way, shape or form. 
  I.e. I have no idea about the quality of these.

	Maybe some other other readers of tcllib-devel and using vim
	will wish to jump in on this ?

> About returning values:
>    -  I changed it and now it's set to return error when there is found 
> any negative cycle.
>    -  There is no risk now, that deleting node won't happen.
>    -  Generally, graph isn't changed at all by procedure - it relates to 
> nodes as well as weights of edges.

Ok.

> About -cutdisplay option, and $param variable:
>    -  yes, you're right - those names are bad.....I just hadn't good 
> idea how to name them

Right, that can happen. And going forward is better than stalling, naming is 
something which is of a lower priority compared to most other problems.

>    -  However, I came up with option -filter ( it is used by other 
> struct::graph procedures, for limiting the set of returned values e.g. 
> nodes - this name will assure some logical conformity ), and $param is 
> now $displaymode.

Hm. No comments regarding this yet, will have a look at the code first.

>  >>I found only a quibble and a typo ...
>  >>'...UNCOHERENT...' in XOpsSetup ...
>  >>How about '...PARTIALLYCONNECTED...' instead.
>  >>Thats the quibble.
>  
> I named it uncoherent, because coherence is in Polish term for 
> [strongly] connected graphs. In most cases translating this way works, 
> but this time it turned out that not always... :)

Very true.

A similar translation problem a german coder could have is 'aktualisieren'. 
Might be tempted to translate as 'actualize'. Wrong. Correct translation is 
'update'. 'actualize' in german is 'verwirklichen'. Completely different meaning.

> It is set now to PARTIALLYCONNECTED.
>  
> Since tomorrow I will start implementing next algorithms and also some 
> updating of existing solutions to come closer to ending first's week phase.

Ok, looking forward to them.

Andreas.

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Lars Hellström wrote:
> Andreas Kupries skrev:
>> Michał Antoniewski wrote:
>>> Hello.

Hi Lars.

>>> Today, I started my work and I've got some questions.
>> Ok. I will answer to the best of my abilities. I may explicitly draw in other 
>> people and their expertise, depending on the context. As of now I will copy our 
>> conversation to tcllib-devel, allowing the community to chime in as well.
> 
> Chiming in (perhaps a bit late), then...
> 
> Is there a reason this is titled graph /manipulations/, when most of it 
>   is about implementing algorithms that take a graph as input but don't 
> aim to change it in any way? Not that I mind (I'm more comfortable 
> modelling graphs as immutable data than as mutable objects), but often 
> one wants higher level operations that modify graphs than just 
> adding/removing one edge/vertex.

It is a bit of a misnomer, and definitely my fault, I named the idea that way 
... Maybe I had the graph query and transform idea in my mind at the time.

> As an example, one kind of manipulation that seems useful (especially 
> when you get to the flow algorithms, in a couple of weeks) would be an 
> operation that splits every vertex in two, where one part receives the 
> incoming edges and the other gets the outbound edges, with a new edge 
> from in-part to out-part. (This is a classical trick for reducing flow 
> problems with capacities on vertices to flow problems with capacities 
> only on the edges.)

I would put such an operation into a graph::ops procedure, and export it from 
the ops package. I.e. a helper, but valuable enough to be a regular public 
operation. Which of such helpers we then move to the foundation class, i.e. 
struct::graph, can then be discussed separately.


>>  > As it is in
>>> timeline I started with Bellman-Ford and Johnson's.
> 
> In general, I think time is better spent implementing one algorith each 
> for doing A, B, and C, than three different algorithms for doing A, but 
> YMMV.

The three distances algorithms (dijkstra, bellman-ford, johnson) have different 
time complexities and limitations. As such also different areas of application, 
depending on the graphs to be expected as inputs. And automatic selection based 
on the input is often not possible.

Information like this, i.e. raw time complexities and limitations, and then at 
the higher level which algorithm is better in what situation is definitely 
something we have to put into the documentation.


> Also, I find the rule applied in struct::graph::op about naming 
> commands after algorithms that is a bit curious. There's certainly a 
> point in doing so when you've got many algorithms for doing the same 
> thing, but on the other hand it renders code employing these commands 
> more obscure.

Maybe. It depends a bit on the audience. Assuming that the reader knows graph 
theory I see now problem. Another thing using code can do is to define aliases 
mapping from, for example, 'distance', to 'dijkstra'. That location would then 
also be a good place for the user to comment on why a specific algorithm was 
chosen, see above about that.

>>> 2. Documentation. Should I just extend those html files in tcllib ( 
>>> graphops.html ) or write my documantation? As we talked it over before - 
>>> documentation will be made at the end.
>> Looking over the Tcllib sources I have here I do not see any file named 
>> "graphops.html". Can you tell me where you found it ?
> 
> Perhaps http://tcllib.sourceforge.net/doc/graphops.html? That one does 
> not seem to be listed in http://tcllib.sourceforge.net/doc/index.html, 
> though... ;-)

Interesting that it is not in the index. I will ping Joe English, he maintains 
that part of the tcllib site. (This index is maintained manually so far (*))

If this is indeed the graphops.html Michal was talking about, then to clarify, 
this HTML is generated from the file 'graphops.man' in the modules/struct/ 
directory.

(*) There are some very new sak commands to help him, with intention to make it 
fully automatic in the future. Alas, afaik we are not there yet.

> 
> Regarding that previously existing manpage, I notice it documents both 
> [struct::graph:op::kruskal] and [struct::graph:op::prim] as computing a 
> minimum spanning tree (I presume that should be a minimum /weight/ 
> spanning tree) for a graph, but fails to give any distinguishing trait, 
> other than the names of the algorithms. While this may be sufficient, 
> for a reader with access to the literature, I think the average tcllib 
> user would appreciate a bit more information; in particular, I think 
> the respective complexities of the commands should be given the 
> manpage, especially since the results varies depending on how cleverly 
> an algorithm has been implemented. (E.g., looking in a textbook I see a 
> naive O(mn) implementation of Kruskal, but also a more efficient O(m 
> \log n) implementation, and a note that O(m \alpha(m,n)) is possible.)
> 
> IOW, when documenting this kind of command, please give (a good 
> estimate of) its complexity as well.

Fully agreed. See also my comments above re multiple algorithm for the same.

The kruskal and prim implementations are from last year's GSoC. Have to check 
who wrote the docs. Might have been me, as part of the integration into tcllib 
(The '08 operations were written outside of Tcllib first).

	As such this is not something to be done by Michal.
	Not during the GSoC period. I am fine if he wishes
	to do that after. By then however, I might have fixed
	things already.

Can you (Lars) please go over the docs and file regular Tcllib bugs for where 
you believe information is missing ?


> Also, regarding the API provided by struct::graph, I find it a bit 
> curious that "weight" is singled out as a special property of arcs, 
> with its own methods for setting, getting, and so on. I suspect a more 
> practical approach for a higher level package like struct::graph::op 
> would be that the weight was some attribute given to the arcs, and that 
> a command for computing e.g. a shortest path would take as an argument 
> (or option value) the name of the attribute to use as "weight" in this 
> particular calculation.

This was also a decision made during GSoC 2008. I am not recalling details at 
the moment. There should be something in my mail archives however as I was 
involved, although not as primary mentor. For this I however should have some 
mails.


Andreas.

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Andreas Kupries skrev:
> Michał Antoniewski wrote:
>> Hello.
>>
>> Today, I started my work and I've got some questions.
> 
> Ok. I will answer to the best of my abilities. I may explicitly draw in other 
> people and their expertise, depending on the context. As of now I will copy our 
> conversation to tcllib-devel, allowing the community to chime in as well.

Chiming in (perhaps a bit late), then...

Is there a reason this is titled graph /manipulations/, when most of it 
  is about implementing algorithms that take a graph as input but don't 
aim to change it in any way? Not that I mind (I'm more comfortable 
modelling graphs as immutable data than as mutable objects), but often 
one wants higher level operations that modify graphs than just 
adding/removing one edge/vertex.

As an example, one kind of manipulation that seems useful (especially 
when you get to the flow algorithms, in a couple of weeks) would be an 
operation that splits every vertex in two, where one part receives the 
incoming edges and the other gets the outbound edges, with a new edge 
from in-part to out-part. (This is a classical trick for reducing flow 
problems with capacities on vertices to flow problems with capacities 
only on the edges.)


>  > As it is in
>> timeline I started with Bellman-Ford and Johnson's.

In general, I think time is better spent implementing one algorith each 
for doing A, B, and C, than three different algorithms for doing A, but 
YMMV.

Also, I find the rule applied in struct::graph::op about naming 
commands after algorithms that is a bit curious. There's certainly a 
point in doing so when you've got many algorithms for doing the same 
thing, but on the other hand it renders code employing these commands 
more obscure.

>> 2. Documentation. Should I just extend those html files in tcllib ( 
>> graphops.html ) or write my documantation? As we talked it over before - 
>> documentation will be made at the end.
> 
> Looking over the Tcllib sources I have here I do not see any file named 
> "graphops.html". Can you tell me where you found it ?

Perhaps http://tcllib.sourceforge.net/doc/graphops.html? That one does 
not seem to be listed in http://tcllib.sourceforge.net/doc/index.html, 
though... ;-)

Regarding that previously existing manpage, I notice it documents both 
[struct::graph:op::kruskal] and [struct::graph:op::prim] as computing a 
minimum spanning tree (I presume that should be a minimum /weight/ 
spanning tree) for a graph, but fails to give any distinguishing trait, 
other than the names of the algorithms. While this may be sufficient, 
for a reader with access to the literature, I think the average tcllib 
user would appreciate a bit more information; in particular, I think 
the respective complexities of the commands should be given the 
manpage, especially since the results varies depending on how cleverly 
an algorithm has been implemented. (E.g., looking in a textbook I see a 
naive O(mn) implementation of Kruskal, but also a more efficient O(m 
\log n) implementation, and a note that O(m \alpha(m,n)) is possible.)

IOW, when documenting this kind of command, please give (a good 
estimate of) its complexity as well.


Also, regarding the API provided by struct::graph, I find it a bit 
curious that "weight" is singled out as a special property of arcs, 
with its own methods for setting, getting, and so on. I suspect a more 
practical approach for a higher level package like struct::graph::op 
would be that the weight was some attribute given to the arcs, and that 
a command for computing e.g. a shortest path would take as an argument 
(or option value) the name of the attribute to use as "weight" in this 
particular calculation.

Lars Hellström

Re: [Tcllib-devel] Graph Manipulations

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

Andreas Kupries wrote:
> Next up, the test cases ...

I found only a quibble and a typo ...

'...UNCOHERENT...' in XOpsSetup ...

How about '...PARTIALLYCONNECTED...' instead.
Thats the quibble.


Running the tests through SAK using a Tcl 8.5.7 shell ...

	% ./sak.tcl test run -l X -s ~/Abuild/bin/t modules/struct
	[    ]  Starting ...
	[    ]  [8.5.7] struct ~~ FAILS T  2568 P  2541 S    26 F     1

	% grep FAILED X.log
	==== graphop-gtcl-stcl-sttcl-qtcl-Johnsons-3.1 Johnsons, bad option used FAILED
	==== graphop-gtcl-stcl-sttcl-qtcl-Johnsons-3.1 FAILED

Looking into X.log

	---- Result was:
	Bad option given. Available options: -cutdisplay
	---- Result should have been (exact matching):
	Bad option given. Availible options: -cutdisplay
	==== graphop-gtcl-stcl-sttcl-qtcl-Johnsons-3.1 FAILED


And that's the typo, in the test case, in the expected result.


Andreas.