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.