Re: Representing Undirected Edges (advice, please)

In article <[e-mail]>,
Gavin Kistner  <[e-mail]> wrote:
>--Apple-Mail-2--176720861
>Content-Transfer-Encoding: 7bit
>Content-Type: text/plain;
>	charset=US-ASCII;
>	delsp=yes;
>	format=flowed
>
>Summary
>==================================
>How do you represent and handle bidirectional links between items,  
>given that you will necessarily need two distinct variables for each  
>end? How then do you handle a directed traversal of those links?
>
>(Sorry for the length of this email; the concept is simple but I  
>wanted to be clear about the trouble I'm having.)
>
>
>Background
>==================================
>I got all caught up in the quiz I gave last week, researching graph/ 
>network theory. As a result, I'm writing a generic library for  
>finding paths. More on this library when I get closer to finishing.
>
>One thing that's causing me a bit of trouble is how to represent non- 
>directed edges between nodes. Let me explain the concept for those  
>not familiar with the terminology, and then the problem.
>
>A non-directed edge between nodes is a fancy way of saying "ObjectA  
>links to ObjectB, and vice versa". So while a directed edge would be:
>     ObjectA   ------------->  ObjectB        or       ObjectA    
><-------------  ObjectB
>an undirected edge is simply:
>     ObjectA   <------------>  ObjectB
>
>Edges also may have other information associated with them (such as a  
>'weight' for the edge), so I currently have them pulled out into  
>their own class:
>
>     class Edge
>         attr_accessor :start_node, :end_node, :weight
>
>         def initialize( start_node, end_node, directed=false,  
>weight=nil )
>             @start_node, @end_node, @weight, @directed = start_node,  
>end_node, weight, directed
>         end
>
>         def directed?
>             @directed
>         end
>     end
>
>To store both ends, I need two variables, and here's where the  
>trouble starts creeping in. In a directed edge it's necessary to  
>distinguish which node is the start and which is the end, but in an  
>undirected edge I want the class to be agnostic about this. So, for  
>example, I now have to redefine the == method to account for non- 
>directionality:
>
>         def ==( other_edge )
>             ( !@directed == !other_edge.directed? )
>             and
>             ( @weight == other_edge.weight )
>             and
>             (
>                 ( @start_node == other_edge.start_node && @end_node  
>== edge.end_node )
>                 or
>                 ( !@directed && @start_node == other_edge.end_node  
>&& @end_node == edge.start_node )
>             )
>         end
>

The thing that strikes me here is that you probably want to have an 
base edge class (or maybe actually a Mixin module to put it in more 
Ruby-ish terms) that would define the basic functionality of an edge and 
then have undirected and directed edge classes that derive from it.

In my experience, you either have a directed graph or an undirected graph 
- I've never run into a situation where a graph can have both directed 
and undirected edges (I suppose it's possible, and maybe that's what 
you're trying to plan for, but in my experience in working with graphs 
they're either one or another).  

Seperating your directed graphs and undirected graphs could greatly 
simplify things.



>So far I'm still staying afloat.
>
>
>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
>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>
>
>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>
>
>* I can't just 'flip' the edges while creating the path, because the  
>same graph might be crawled multiple times to create multiple paths.
>
>* I could use code to determine the correct node order (figuring out  
>which ends touch which) but that will be slightly messy and slower.  
>(Premature optimization is the root of all evil, but you gotta strive  
>for a good design at least.)
>
>* I could store both the edge list AND the node list for a path, but  
>that's not very DRY or normalized.
>
>* I could create a subclass of Edge which is a Link (since  
>essentially the problem is that I'm using undirected information to  
>represent directed information), but then I'd be duplicating  
>information. (Later changes to the weight of an edge would not be  
>reflected in the Link used in a Path.)
>
>* Perhaps I could create a Link class which references edges and  
>expresses directionality. (This thought just occurred to me.)
>
>
>  I know I've hit this problem a few times before in programming, and  
>have never been pleased with any of my solutions.
>
>Thanks for any insights/opinions! :)
>

One idea:
Graphs are often represented by hashes of lists, like so:

graph = {
 a => [b,c,d],
 b => [a,e],
 c => [a,e],
 d => [a],
 e => [b,c]
}

So, for example, a connects with nodes b,c and d.  You can find all the 
nodes that a connects to by iterating through the list of graph[a].  You 
can then traverse further down in the graph by taking every node in a's 
list and recursively iterating through all of their children.

If you use a Hash for representing the graph, you really don't need an 
Edge class.  You can then have a DirectedGraph class and an 
UndirectedGraph class each of which contains the connection hash - how 
you traverse through the hash will be a bit different depending on 
whether it's directed or not.  The hash of lists representation is simple 
and compact.

It can, however be useful to have an Edge class (for weighted edges, as 
you point out).  

Take a look at some other OO graph class libraries out there such as the 
Boost Graph library.  There are lots of them out there and different ones 
emphasize different things: some emphasize the nodes (as in the hash 
representation) while others emphasize the edges (each has it's 
advantages/disadvantages).

Phil