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.