G
Gavin Kistner
--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
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!
--
"When I am working on a problem I never think about beauty. I only
think about how to solve the problem. But when I have finished, if
the solution is not beautiful, I know it is wrong."
- R. Buckminster Fuller
--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
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!
--
"When I am working on a problem I never think about beauty. I only
think about how to solve the problem. But when I have finished, if
the solution is not beautiful, I know it is wrong."
- R. Buckminster Fuller
--Apple-Mail-2--176720861--