# Re: flexible graph library - sans hash

**URL:** <https://www.ruby-forum.com/t/re-flexible-graph-library-sans-hash/96491>\
**Category:** Ruby\
**Created:** [June 29, 2006, 1:08am UTC](https://www.ruby-forum.com/t/re-flexible-graph-library-sans-hash/96491 "2006-06-29T01:08:04Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [June 29, 2006, 1:08am UTC](https://www.ruby-forum.com/t/re-flexible-graph-library-sans-hash/96491/1 "2006-06-29T01:08:04Z")

</div>

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