From: Gavin Kistner Date: 2005-05-09T03:05:31+09:00 Subject: Re: Representing Undirected Edges (advice, please) --Apple-Mail-1--170645187 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed 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, , b, , c, , d] > > or > > [[a,b,c,d], [, , ] > > 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 > Date: May 8, 2005 11:32:45 AM MDT > To: Gavin Kistner > 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: >> >> >> >> 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: >> >> >> >> > > 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, , b, , c, , d] > > or > > [[a,b,c,d], [, , ] > > 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 -- (-, /\ \/ / /\/ --Apple-Mail-1--170645187--