From: Nuralanur@...
Date: 2006-06-29T08:04:59+09:00
Subject: Re: flexible graph library - sans hash

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

Dear Ara,
 
the first thing that comes to mind would be to represent a graph using an  
incidence
matrix - where the entry (a_ik) represents the strength with which node i  is
connected to node k (non-symmetrically, in the first place).
Unfortunately, I don't know of a graph library that uses matrices (too  much
memory required, probably), but I
think you can still solve any problem of multiply-connected graphs  using
hashes, as in rgl, but you'll need several such graphs.
 
An example. Let g be a graph with nodes={New York,Los Angeles,Toronto}  and
edges indicating whether there is a flight connection between these  cities
every day. Let's distinguish that for airlines {a,b,c}.
 
Now, if there are 14 flights from New York to Los Angeles daily,  12 flights 
from
New York to Toronto etc.,
 
a connection matrix (incidence matrix) would look like this,  say:
 
        NY    LA    TT
NY    0        14    12
LA    15      0        8
TT    12      12    0
 
To this corresponds to a matrix detailing how many flights are operated by  
the
individual airlines (a,b,c) ,say  :
 
 
NY                LA            TT
NY    (0,0,0)        (1,2,11)        (3,9,0)
LA    (5,5,5)          (0,0,0)        (2,4,2)
TT    (3,5,4)         (1,1,10)        (0,0,0)
 
But this means that you can replace the first matrix above with three  
matrices,
such that M_total=M_a+M_b+M_c holds for the entries.
The entries of the matrices M_i then say whether  any ordered pair of  cities
is connected using airline i, and how strongly (no flight from New York to  
Toronto
using airline c).
The matrix below can be represented using three hashes with one value  only:
 
get_away_using_airline_a={'ny->la',1,'ny->tt',3,'la->ny',5,'la->tt',2,'tt->ny'
,3,'tt->la',1}

 
get_away_using_airline_b={'ny
->la',2,'ny->tt',9,'la->ny',5,'la->tt',4,'tt->ny',5,'tt->la',1}
 
get_away_using_airline_c={'ny->la',11,'la->ny',5,'la->tt',2,'tt->ny',4,'tt->la
',1}
 
Maybe one still needs the total connectedness


get_away_at_all={'ny->la',14,'ny->tt',12,'la->ny',15,'la->tt',8,'tt->ny',12,'t
t->la',12}
 
Best regards,
 
Axel 

-------------------------------1151535891--