Noob alert. I know barely any Ruby, and I''m just getting started with Rails. I effectively have a graph data structure in my database, and I''m trying to figure out how it should get modelled properly into Rails. Let''s say there''s a "nodes" table and an "edges" table. The "edges" table has fields "from_id" and "to_id" as well as several other fields to describe the edge. How do I link things so that I can do stuff like: <% for edge in @node.edges %> From: <%= edge.from.name %><br /> To: <%= edge.to.name %><br /> Length: <%= edge.length %><br /> <hr /> <% end %> -- Bob Aman
* Bob Aman (vacindak-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org) [050217 18:24]:> Noob alert. I know barely any Ruby, and I''m just getting started with Rails. > > I effectively have a graph data structure in my database, and I''m > trying to figure out how it should get modelled properly into Rails.Bob, This isn''t exactly an answer to your question, but you might also look into RGL (the Ruby Graph Library) if you''re doing a lot of graph work. I''ve done some work with that, and it''s possible to use RGL + Madeleine with just the Action Pack front-end from Rails if that fits your application better. Just speaking from experience, you can definitely do graph work with a relational database (in fact some databases, such as Oracle, have primitives such as "CONNECT BY" which support graph operations in the database), though you may well run into efficiency issues depending on the types of computations you perform on the graphs. If you''re doing, for example, content management via a stored graph, you''ll quickly run into the transitive closure problem (which nodes are reachable from this subgraph?), which behaves much like matrix multiplication -- meaning for an n-node graph you''re theoretically at best O(n^2) in answering that question, but in practice nobody gets much better than a hair under O(n^3) for general graphs. You probably know best about your particular application or graph class, though, and this may not be much of an issue (or your particular graph class may make this problem straightforward). After all that, I''d say there''s no reason why you can''t do what you''re talking about in Rails by having Nodes in a table, and edges being associations between nodes. A Node has_and_belongs_to_many other Nodes, thus edges are just the association table mapping nodes together. If you need to carry around data on the edges themselves (labels, directions, multiplicity, ordering, etc.) things get only slightly more complicated -- you just need columns in the node association (edge) table for this extra data. On the other hand you could simply have an edges table with two nodes table foreign keys. Rick -- http://www.rickbradley.com MUPRN: 788 | (exit Cross Hwy 70S random email haiku | (Kroger shopping ctr) and go | over a hill.
Completely untested, but I think this is it. class Edge < ActiveRecord::Base has_one :from, :class_name=>"Node" has_one :to, :class_name => "Node" def length # calculation goes here end end class Node < ActiveRecord::Base end On Thu, 17 Feb 2005 18:20:58 -0500, Bob Aman <vacindak-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> Noob alert. I know barely any Ruby, and I''m just getting started with Rails. > > I effectively have a graph data structure in my database, and I''m > trying to figure out how it should get modelled properly into Rails. > > Let''s say there''s a "nodes" table and an "edges" table. The "edges" > table has fields "from_id" and "to_id" as well as several other fields > to describe the edge. > > How do I link things so that I can do stuff like: > > <% for edge in @node.edges %> > From: <%= edge.from.name %><br /> > To: <%= edge.to.name %><br /> > Length: <%= edge.length %><br /> > <hr /> > <% end %> > > -- > Bob Aman > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >-- Cheers Koz
On 18.2.2005, at 03:18, Michael Koziarski wrote:> Completely untested, but I think this is it. > > class Edge < ActiveRecord::Base > has_one :from, :class_name=>"Node" > has_one :to, :class_name => "Node" > def length > # calculation goes here > end > endIn this case the foreign key fields would be in the nodes table. Shouldn''t they be in the edges table (at least the original poster seems to want that)? Anyway, you probably need to name the foreign keys explicitly because the two associations point to the same class: class Edge < ActiveRecord::Base belongs_to :from, :class_name=>"Node", :foreign_key => "from_id" belongs_to :to, :class_name => "Node", :foreign_key => "to_id" def length # calculation goes here end end //jarkko> > class Node < ActiveRecord::Base > end > > > On Thu, 17 Feb 2005 18:20:58 -0500, Bob Aman <vacindak-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> > wrote: >> Noob alert. I know barely any Ruby, and I''m just getting started >> with Rails. >> >> I effectively have a graph data structure in my database, and I''m >> trying to figure out how it should get modelled properly into Rails. >> >> Let''s say there''s a "nodes" table and an "edges" table. The "edges" >> table has fields "from_id" and "to_id" as well as several other fields >> to describe the edge. >> >> How do I link things so that I can do stuff like: >> >> <% for edge in @node.edges %> >> From: <%= edge.from.name %><br /> >> To: <%= edge.to.name %><br /> >> Length: <%= edge.length %><br /> >> <hr /> >> <% end %> >> >> -- >> Bob Aman >> _______________________________________________ >> Rails mailing list >> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >> http://lists.rubyonrails.org/mailman/listinfo/rails >> > > > -- > Cheers > > Koz > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >-- Jarkko Laine http://jlaine.net http://odesign.fi _______________________________________________ Rails mailing list Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org http://lists.rubyonrails.org/mailman/listinfo/rails
> In this case the foreign key fields would be in the nodes table. > Shouldn''t they be in the edges table (at least the original poster > seems to want that)? Anyway, you probably need to name the foreign keys > explicitly because the two associations point to the same class: > > class Edge < ActiveRecord::Base > belongs_to :from, :class_name=>"Node", :foreign_key => "from_id" > belongs_to :to, :class_name => "Node", :foreign_key => "to_id" > def length > # calculation goes here > end > endYes, I believe that''s what I was looking for. I''m going to go see if that works. Thanks! -- Bob Aman
> Yes, I believe that''s what I was looking for. I''m going to go see if > that works. Thanks!I had to put has_many :edges, :class_name => "Edge", :foreign_key => "from_id" into the Node model, but otherwise it worked perfectly, thanks! I am a little confused about the difference between has_one and belongs_to; it looks like this is a fairly common confusion since there''s even a FAQ entry on it. Honestly, I still don''t understand, even after reading the FAQ. Perhaps a more complete example showing the difference between the two might help? (By which I mean, show the SQL dump for creating the related tables in the example as well.) -- Bob Aman
Hello Bob, Maybe this [ http://curry.elitists.net/%7Escott/ARAssociations.png ] helps clear the confusion. Cheers /B On Fri, 18 Feb 2005 08:33:41 -0500, Bob Aman <vacindak-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> > Yes, I believe that''s what I was looking for. I''m going to go see if > > that works. Thanks! > > I had to put > > has_many :edges, :class_name => "Edge", :foreign_key => "from_id" > > into the Node model, but otherwise it worked perfectly, thanks! > > I am a little confused about the difference between has_one and > belongs_to; it looks like this is a fairly common confusion since > there''s even a FAQ entry on it. Honestly, I still don''t understand, > even after reading the FAQ. Perhaps a more complete example showing > the difference between the two might help? (By which I mean, show the > SQL dump for creating the related tables in the example as well.) > > -- > Bob Aman > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >-- Bruno Mattarollo <bruno.mattarollo-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> Currently in: Sydney, Australia
On 19/02/2005, at 12:18 AM, Bob Aman wrote:> Yes, I believe that''s what I was looking for. I''m going to go see if > that works. Thanks!This might probably be a good candidate for an AR::Act. Might not belong in the AR core, but definately as a gem or download on the community wiki. - tim lucas
Hi Bob, You might try playing with the has_and_belongs_to_many relationship to create a many-to-many link between nodes via edges. Something like this: has_and_belongs_to_many :edges, :class_name => "Node", :join_table => "edges", :foreign_key => "from_id", :association_foreign_key => "to_id" Depending on how you are storing the edge, you might also define the relationship in the other direction: has_and_belongs_to_many :linked_from, :class_name => "Node", :join_table => "edges", :foreign_key => "to_id", :association_foreign_key => "from_id" The two relationships will create two collections of edges for each node. Vince Nibler Bob Aman wrote:>Noob alert. I know barely any Ruby, and I''m just getting started with Rails. > >I effectively have a graph data structure in my database, and I''m >trying to figure out how it should get modelled properly into Rails. > >Let''s say there''s a "nodes" table and an "edges" table. The "edges" >table has fields "from_id" and "to_id" as well as several other fields >to describe the edge. > >How do I link things so that I can do stuff like: > ><% for edge in @node.edges %> >From: <%= edge.from.name %><br /> >To: <%= edge.to.name %><br /> >Length: <%= edge.length %><br /> ><hr /> ><% end %> > > >
> The two relationships will create two collections of edges for each node. >I take that back, you''ll have collections of nodes, not edges. This might not work if the nodes in the collections are not extended with state from the edges. Vince Nibler
On Fri, 18 Feb 2005 11:34:58 -0800, Vince Nibler <vincen-VPOBLbH4ca3QT0dZR+AlfA@public.gmane.org> wrote:> > The two relationships will create two collections of edges for each node. > > > I take that back, you''ll have collections of nodes, not edges. This > might not work if the nodes in the collections are not extended with > state from the edges.Yeah, and this wasn''t what I wanted. I implemented it as someone suggested with a has_many :edges and belongs_to :node kinda of setup. The problem was that there are fields on the edges I need to get access to. But I''m all set at this point. Everything''s working like a charm. -- Bob Aman