Re: flexible graph library - sans hash

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 A.,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 A. 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs