From: Ilmari Heikkinen <kig@...>
Date: 2005-05-11T14:21:53+09:00
Subject: Re: Representing Undirected Edges (advice, please)


On 9.5.2005, at 21:33, Jacob Fugal wrote:

> On 5/8/05, Nuralanur@aol.com <Nuralanur@aol.com> wrote:
>> Dear Gavin,
>>
>> Why can't you use the concept of an incidence matrix ?
>> That would be a matrix made up of all the nodes times all the nodes 
>> and
>> entries
>> '1' at position (i,j) if nodes i and j are connected and entry '0'
>> otherwise. (Or you choose
>> to assign a numeric value for the connection strength)
>> Of course, that's a symmetric matrix, so one could leave the elements 
>>  below
>> the diagonal out, and maybe rename nodes to make use of sparseness...
>
> Though an incidence graph can work (and work quite well) for a simple
> graph, Gavin's use case includes the possibility of multiple
> connections between two nodes: e.g. two distinct edges that have the
> same set of endpoints. If there are only two such edges, each being
> directed and opposite in direction, the incidence graph still works
> (one above the diagonal and one below, based on direction) but when
> you start mixing undirected edges and directed edges, or multiple
> edges with the same "direction", it breaks down.
>

Unless you handle the incidence matrix values as lists of edges.
Then you can say graph[A][B].min{|edge| weigh(edge)} and go with that.