From: Ara.T.Howard@...
Date: 2005-05-09T03:44:23+09:00
Subject: Re: Representing Undirected Edges (advice, please)

On Mon, 9 May 2005, Gavin Kistner wrote:

> The Problem
> ==================================
> Any path that links a few nodes together should be able to be
> represented by its edges. So, for example, the path from 'a' to 'd'
>     a <-----> b <-----> c  <-----> d

i think you must also add the concept of direction to path.  for example, if i
tell you walk around my block on a particular path i'd say

   - start at my house and go NORTH
   - when you hit the corner turn WEST
   - when you hit the next corner turn SOUTH
   - when you hit the corner turn EAST
   - when you hit the corner turn NORTH and continue until you see my house

so a Path might be represented as someting like

   class Edge
     def <=> other
       raise NotConnectedError unless connected_to? other or parallel_to? other
       case other.start_node
         when end_node
           -1
         when start_node
           0
         else
           1
       end
     end
     def connected_to? other
       start_node == other.end or other.end_node == start_node
     end
     def parallel_to? other
       start_node == other.start_node and end_node == other.end_node
     end
   end

   class Path
     def initialize
       @edges = []
     end
     def add_edge edge
       @edges << edge
       @edges.sort!
     end
   end

in otherwords a Path is a set of ordered (directed) edges

> is represented by the ordered list of three edges:
>     <Edge @start_node=a @end_node=b>
>     <Edge @start_node=b @end_node=c>
>     <Edge @start_node=c @end_node=d>

so this is a path


> If I want to recreate the list of nodes visited, I can just loop
> through the edges and pick out the nodes. ... Except I can't, because
> if these are non-directional edges, the list might look like:
>     <Edge @start_node=b @end_node=a>
>     <Edge @start_node=b @end_node=c>
>     <Edge @start_node=d @end_node=c>

but this is not - there is no way described here to get from a to c

in summaray: i think adding a Path class, where paths are lists of connected
(or parallel) edges may help abstract the problem.  then again maybe not ;-)
how does the RGL handle this?

cheers.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| renunciation is not getting rid of the things of this world, but accepting
| that they pass away. --aitken roshi
===============================================================================