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...
Best regards,
Axel
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
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...
---------------
/ \
/ \
+---+ 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
Jacob Fugal wrote:
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).
Or, for example, consider the recent Barrel of Monkeys quiz, which
connected 26 letter-of-the-alphabet nodes by songs that begin/end with
the letters they connect.
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.
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.
Yeah, I think I like that example even better (mine felt a little contrived).
Jacob Fugal
On 5/9/05, Phrogz <gavin@refinery.com> wrote:
Or, for example, consider the recent Barrel of Monkeys quiz, which
connected 26 letter-of-the-alphabet nodes by songs that begin/end with
the letters they connect.