Topic: How to build a tree structure

Ok I have a XML file that basically has a dependency tree of the form

<Dep1 name="aaa" version="1.2.3">
  <Dep2 name="bbb" version="4.5.6">
    <Dep3 name="ccc" version="7.8.9">
      <Dep4 name="ddd" version="1.1.1">
      </Dep4>
    </Dep3>
  </Dep2>
</Dep1>

My problem is that before hand I have no way of knowing anything about the structure each element can have any number of children or none at all and there is no way to know how many levels a particular branch will go down (up to a max of say 10 or 15).

I was wanting to know how I could structure this using what I do know so that I could pass this huge thing to a view in rails where is could be displayed as nested <ul>'s
quasi-code example:

<ul>
<for-each "Tree/Dep1">
  <li><value-of "@name"/> : <value-of "@version"/></li>
  <ul>
    <for-each "Dep2">
    <li><value-of "@name"/> : <value-of "@version"/></li>
    <ul>
      <for-each "Dep3">
      ...
      10x
    </ul>
  </ul>
</ul>

Any ideas on how I could structure this? Many thanks.
-Jack

Re: How to build a tree structure

How about using recursion with a partial? Similar to this post

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

Thanks Ryan. The part about using a partial for recursion will really help me keep this DRY. However, I should have explained some things better. You see these dependencies are also not unique so 'a' might depend on 'c' but 'b' could also depend on 'c'. So is it possible to have multiple 'patent_id's? Is there something else I could try?

By the way thanks for all your help and Railscast etc.

Re: How to build a tree structure

JackVandaL wrote:

You see these dependencies are also not unique so 'a' might depend on 'c' but 'b' could also depend on 'c'.

That shouldn't be a problem. "c" can be the parent of both "a" and "b".

JackVandaL wrote:

So is it possible to have multiple 'patent_id's?

I don't see how that would solve anything. Do you really need multiple parents? A given parent can have multiple children so I think that's all you need here.

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

Sorry again, I'm still not being clear the dependency works the other way

dependency level 1 (Dep1) depends on dependency level 2 (Dep2)

So you see I have widget 'Q' that requires parts 'a' through 'f' such that:

     A
  __|__
  |        |
  a      b__
  |        |     |
  c      d    e
  |        |     
  e      f

Sorry for the poor graphic but you can see that 'e' is not a unique child (granted all 'e's [read: parts] will have the same children but can occur anywhere.) In the end 'Q' only needs a, b, c, d, e, and f, but I need to have a page that can show the full tree.

Pretty nasty tree huh?

Re: How to build a tree structure

Hmm, you might need a self-referencing many-to-many association. Something like this:

class Part < ActiveRecord::Base
  has_many :dependencies
  has_many :dependent_parts, :through => :dependencies, :class_name => 'Part'
end

class Dependency < ActiveRecord::Base
  belongs_to :part
  belongs_to :dependent_part, :foreign_key => 'dependent_part_id', :class_name => 'Part'
end


Then you would have two tables: parts and dependencies. The dependencies table would have two foreign keys: part_id and dependent_part_id. Now a given part can have many parents in a sense.

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

Wow that's incredible. I don't want to be a pain but I'm not as proficient with RoR as you are. Do you think you could expound on this idea some more or point to some other source(s). I'm pretty sure I don't quite grasp it fully. (Hey maybe you could make it a Railscast)

Thanks

Re: How to build a tree structure

I'm planning to release a Rialscasts episode on Wednesday that will cover many-to-many associations. It won't go into detail regarding self-referencing many-to-many like I'm showing here, but it may answer some of your questions.

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

I just watched it. VERY helpful. I have a new look on how to do my DB but I'd still like to get this tree information in there somehow as well. I left a comment on the railscast page but in case you see this first I was wondering if we could discuss self-referencing associations. If not maybe a pointer in the the right direction?

EDIT: maybe we should move this discussion to the Database Design section...

EDIT2: until then I'll be looking at your old post here. I may not need anything after I've looked over it awhile.

EDIT3: ok I think I've got a plan now. I'm really starting to understand this stuff better. I'll post what I come up with so someone can look over it. *grins big*

Last edited by JackVandaL (2007-06-20 14:04:23)

Re: How to build a tree structure

JackVandaL wrote:

maybe we should move this discussion to the Database Design section...

There we go. smile

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

Hello again and thanks for the move.

Ok here's my design model and my ideas for how to "make it so"

We start with our USERS who have [first_names, last_names, emails(which are also logins), and passwords]. USERS can have many PROJECTS which have [names and descriptions]. Next, PROJECTS have many REQUIREMENTS which may have been [approved and requested]. REQUIREMENTS are actually PRODUCTS which have a long list of attributes like [names, versions, product_numbers, etc.]. PRODUCTS have DEPENDENCIES which are just other PRODUCTS. In the dependency tree children may have more than one parent (ie they are not unique or more than one product may 'depend' on another product). Also USERS can have PREFERENCES which are simply PROJECTS that they care about currently (Use Case: They may not want to see all of the PROJECTS that belong to them OR they may want to keep an eye on other USERS' PROJECTS)

So now for my models: (notice the '*', '**', and '***' notes)
regular text = fields
{} = in the model

(id)
first_name
last_name
login/email
password
created_at
updated_at
{
has_many :projects
has_many :products
has_many :preferences
}

(id)
name
description
user_id
created_at
updated_at
{
belongs_to :user
belongs_to :preferences
has_many :requirements
has_many :products, :through => :requirements
has_many :dependencies ***
}

(id)
name
version
approver
product_number
user_id
approval **
{
has_many :requirements
has_many :projects, :through => :requirements
has_many :dependencies
has_many :parts, :through => :dependencies
}

(no id)
project_id
product_id
approved **
requested **
{
belongs_to :project
belongs_to :product
}

(no id)
product_id
part_id
product_version *
part_version *
project_id ***
{
belongs_to :product
belongs_to :part, :class_name => 'Product', :foreign_key => 'part_id'
belongs_to :project ***
}

(no id)
user_id
project_id
{
belongs_to :user
has_one :project
}

NOTES:
* - different version #s are needed because a PROJECT only 'requires' in the latest version of each unique PRODUCT name specified in the dependency tree. However, the tree itself may have (read: will have) many different versioned PRODUCTS listed. So when recreating the Tree we need those versions not the ones that actually get pulled in.

** - The type for 'approval', 'approved', and 'requested' will be DATE so we now when these actions happened and 'nil' will mean false. 'approval' will mean all 'requirements':'approved' will be marked as "approved" with the DATE. Otherwise the PRODUCT owner can choose who is 'approved' on a case-by-case basis.

*** - Originally I didn't have this but I know see this as needed. Here is why. When a PROJECT is updated it may have different 'dependencies' (and therefore also different 'requirements' since they are related). Most likely, some 'dependencies' will be new and others will no longer exist we need to delete the ones that no longer exist or we'll have incorrect data in our DB. This alone is not a full problem. The rest of the issue comes from '*'. In short, PROJECTS need to know when to delete 'dependencies' or rather which ones they can delete.

RULES:
-Only a user who owns a project can 'request' approval for products that owner
-Only a user who owns a product can mark 'approval' or individual 'approved's
-Only a user who owns a project can update the projects 'requirements' and 'dependencies'

OBSERVATIONS:
REQUIREMENTS - is join table that creates a many-to-many association of PROJECTs and PRODUCTs using has_many-through
DEPENDENCIES - is join table that creates a self-referencing many-to-many association of PRODUCTs and PRODUCTs using has_many-through
PREFERENCES - is a join table that connects USERs and PROJECTs in a manner other than ownership, allowing users to "watch" certain PROJECTs not matter who they belong to.

-------------------------------

Sorry for that long message, but does all of the look correct? Is that the best way to do PREFERENCES? Any improvements anyone sees?

Re: How to build a tree structure

Ok so I know all of this looks very LARGE and I've been reading that it is usually better to start small and add to it after each part is operational. Is this a good idea? If so I was thinking I would start with just "projects" and "products" linked with just "requirements" (but that is still pretty big). Then go back and add "users", then "preferences", and finally "dependencies".

Any feed back on this? Also the former question of 'do my relationships look correct?' still stands if anyone cares to look at it all.

Thanks again to everyone

Re: How to build a tree structure

It looks like you're on the right track. Unfortunately I don't have time to inspect your schema in much detail.

JackVandaL wrote:

Ok so I know all of this looks very LARGE and I've been reading that it is usually better to start small and add to it after each part is operational. Is this a good idea?

Yeah, it's generally best to start small. Just try to keep it flexible so you can easily add on the features you need.

The best approach is to start at the interface and build your models from that. Do you need a page to list all of the projects for a given user? If so, make the models and controller for doing that.

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

Thanks Ryan (and no problem I know you are a busy guy)

I guess my main concern is PREFERENCES table because I haven't seen to many examples of has_one. So if someone could just advise me on that.

PREFERENCES is a join table (I'm pretty sure it won't have its own model, just a table) and it connects users and projects through another relation (ie 'interested in') besides 'ownership'.

So does this sound right?
- a USER has_many PREFERENCES
- a PREFERENCE belongs_to a USER  &  has_one PROJECT
- a PROJECT belongs_to a PREFERENCE

Is there maybe a better way or is this correct?

Last edited by JackVandaL (2007-06-22 11:28:51)

Re: How to build a tree structure

If you want to set up an association with preferences then you need to make it a model. Also, you might want to put both foreign keys in there so it can belong_to both a user and a project.

class Preference < AR:B
  belongs_to :user
  belongs_to :project
end

I'm not exactly sure if this fits your requirements, but it's more normal.

Railscasts - Free Ruby on Rails Screencasts

Re: How to build a tree structure

ryanb wrote:

class Preference < AR:B
  belongs_to :user
  belongs_to :project
end

So then using this and
[code=Preference Table]no table id
user_id
project_id[/code]
Would I then have

class User < AR:B
  has_many :preferences
  ...

class Project < AR:B
  has_one :preference
  ...
end

Re: How to build a tree structure

If a project can only have one preference, then yes.

However, you'll want an "id" column in the "preferences" table. It's just like any other table/model.

Railscasts - Free Ruby on Rails Screencasts