From: Jacob Fugal <lukfugl@...>
Date: 2005-05-10T03:33:31+09:00
Subject: Re: Representing Undirected Edges (advice, please)

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.

If you're curious about why you might have multiple edges with the
same direction between the same nodes, consider the case where each
edge carries multiple "weights" (metadata). For example, two nodes, A
and B, are connected by three possible paths. Each choice is rated for
Quickness (Q), Scenic Value (S) and Evasive Quality (E).

(forgive the ascii art if you're not reading in fixed width)

          Q:1, S:2, E:3
         ---------------
        /               \
       /                 \
  +---+   Q:3, S:1, E:1   +---+
  | A |-------------------| B |
  +---+                   +---+
       \                 /
        \ Q:2, S:3, E:2 /
         ---------------

A path-finder looking for speed will prefer the middle path. A
path-finder more concerned with a scenic route will prefer the bottom
path. And a path-finder built into Bond's (James Bond's) dashboard TEC
(Tail Evasion Computer [tm]) will prefer the top path.

True, the difference in paths could be resolved back to one edge per
pair by introducing extra intermediate nodes, but implementing the
graph with multiple edges can provide a nice abstraction for the human
that needs to build and/or manage the graph.

Jacob Fugal