Gavin Kistner
5/8/2005 6:06:00 PM
Thanks for the prompt reply! Response inline.
On May 8, 2005, at 11:32 AM, Aleksi wrote:
> You never explicitly write what is the problem here. It's very hard
> to suggest solutions around it.
Sorry, you're right. I sort of stated it in the summary. It's not so
much a "how can I accomplish this?" question as a "what is the 'best'
way to solve it?"
> Then list [a, b, c, d] would be right. One can deduct nodes_on_path
> list from non_directional_edges_on_path if there are no loops,
> nodes are not visited twice or other fancy issues.
I think even if there are loops and revisitations it can be deduces,
as long as non_directional_edges_on_path is ordered.
> If your definition of path is "a list of successive nodes connected
> by non-directional edges, so that one can visit all nodes or edges
> or both in order they appear in path" then your list could be of form
>
> [a, <Edge b a>, b, <Edge b c>, c, <Edge d c>, d]
>
> or
>
> [[a,b,c,d], [<Edge b a>, <Edge b c>, <Edge d c>]
>
> or something else.
>
> So by stating problem clearly you probably have your answer in it
> already.
>
>
>> * I could store both the edge list AND the node list for a path,
>> but that's not very DRY or normalized.
>>
>
> The two latter forms I've written are not repeating oneself. But if
> you're strongly against that you can verify you _must repeat
> yourself_ if the solution requires it.
Correct, they're not really a violation of DRY, but if the node list
can be deduced from the ordered edge list (which it can) then it _is_
non-normalized; if my code somehow screws up and changes either the
node list or the edge list without properly updating the other, I
have an inconsistent state stored.
> 1) If you store just nodes_on_path, then you can find which edge
> has both ends and recover edges_on_path. Except it doesn't work
> with aforementioned special cases or even with multiple edges
> between same two nodes.
Aye - the multiple-edges-between-the-same-nodes case is one that I
allow and that would mess this case up.
> Where's the repetition?
I suppose it's trivial, but it's the extra data structure and two
more pointers to the 'real' start and end. I think it's becoming
apparent that I *am* succumbing to premature optimization. :)
> If there's beef in here, feel free to forward to the list. If not,
> I don't mind :).
Thanks, I will just for the shared knowledge.
(Original email follows in full for the record.)
Begin forwarded message:
> From: Aleksi <foobar@fuzzball.org.net>
> Date: May 8, 2005 11:32:45 AM MDT
> To: Gavin Kistner <gavin@refinery.com>
> Subject: Re: Representing Undirected Edges (advice, please)
>
>
> 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
>> 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>
>>
>
> You never explicitly write what is the problem here. It's very hard
> to suggest solutions around it.
>
> For example, the latter list _is_ correct path through the graph,
> that is a list of (non-directional) edges that you progress
> through. That means that edge[1].node1 or node2 must be same as
> either edge[0].node1 or node2. And this condition is fulfilled with
> each step.
>
> If you want to use the path to state which were the nodes that were
> on the path, then you're using _different definition_ what is the
> path. Then list [a, b, c, d] would be right. One can deduct
> nodes_on_path list from non_directional_edges_on_path if there are
> no loops, nodes are not visited twice or other fancy issues.
>
> If your definition of path is "a list of successive nodes connected
> by non-directional edges, so that one can visit all nodes or edges
> or both in order they appear in path" then your list could be of form
>
> [a, <Edge b a>, b, <Edge b c>, c, <Edge d c>, d]
>
> or
>
> [[a,b,c,d], [<Edge b a>, <Edge b c>, <Edge d c>]
>
> or something else.
>
> So by stating problem clearly you probably have your answer in it
> already.
>
>
>> * I could store both the edge list AND the node list for a path,
>> but that's not very DRY or normalized.
>>
>
> The two latter forms I've written are not repeating oneself. But if
> you're strongly against that you can verify you _must repeat
> yourself_ if the solution requires it.
>
> 1) If you store just nodes_on_path, then you can find which edge
> has both ends and recover edges_on_path. Except it doesn't work
> with aforementioned special cases or even with multiple edges
> between same two nodes.
>
> 2) If you store just edges_on_path, you can't find correct order in
> case of loop (is it a->b->a->b->c or b->a->b->a->c).
>
> If you store both it might be easier to see why it's not repeating
> information by giving all things on graph an index. All nodes run
> 1..n (a=1, b=2, c=3, d=4) and all edges n+1..m (b-a=5, b-c=6, d-
> c=7). Now you can make path as an indexing array:
>
> path = [1, 6, 2, 6, 3, 7, 4]
>
> and edges_on_path = path.find_all? {|i| i <= 4}, and
> nodes_on_path = path.find_all? {|i| i => 5}.
>
> Where's the repetition?
>
> If there's beef in here, feel free to forward to the list. If not,
> I don't mind :).
>
> - Aleksi
--
(-, /\ \/ / /\/