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.