From: Nuralanur@...
Date: 2005-05-12T07:27:53+09:00
Subject: Re: Representing Undirected Edges (advice, please)

-------------------------------1115850446
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit

Dear Jacob, Dear pathfinders,
 
I've now understood your point about multiple connections and I have to  
confess that
I start liking it more (maybe as much as you are starting to like it  
less...as I understand
from your last email). I would particularly like to have such a  
multiply-connected graph
model when flying from one city to another by one of several air carrier  
companies..
 
 
I can't follow your third argument about the amount of computation,  though.
I want to prepare my point by saying one thing first.
I think it is important to introduce a loss function  which maps each path
to a value how nice/suitable/etc. it is subject to one criterion or a  
collection
of criteria which are somehow weighted ( I know I am repeating  myself).
I find it really important not to associate loss to a node or a connection,  
but to a path.
This may actually remove the obfuscation you were right to complain  about.
If a solution is to be constructed, the
value of this function needs to be calculated iteratively. To do  this,  all 
the connections
from the last node of the part-path obtained so far to the next node need  to 
be evaluated -
and that's regardless of whether you choose letters as nodes and multiple  
connections
between them or songs and single connections.
So I don't think you can save on computation using a graph with a  smaller, 
fixed number
of nodes, because it's the number of connections that's critical.
 
With respect to the starting and ending question, one does indeed have to  
work
a lot - start the algorithm anew from each song that starts by an 'A'.  
Dijkstra's algorithm
would find the loss function value of the connection to any song  ending in 
'Z' , in 'one go', though.
But I want to come back to the multi-connected graph, because it would  
really be nice
to know something more about what's happening when one works with such  
graphs.
Do you have a proposal for an algorithm that could deal with such a  graph?
I'd really like to know about that.
 
Ah, regarding Steven's post, I recall an authoritative three-volume book  
about 
combinatorial problems, where one may certainly find anything of the  sort:
 
Alexander Schrijver, Combinatorial Optimization - Polyhedra and  Efficiency, 
Springer-Verlag, 2003, ISBN 3-540-44389-4.
 
I also found out that they sell a CD with C code with it ...
So a quick and dirty solution may be to use code from it in Ruby with SWIG,  
but I agree
that only a program in Ruby is really a good program...
 
Best regards,
 
Axel 

-------------------------------1115850446--