Algorithm for creating a directed graph using flat data input [closed]

Question

Given flat data like this:

01001, Butter, salted
01002, Butter, whipped, with salt
01145, Butter, without salt
04601, Butter, light, stick, with salt
04602, Butter, light, stick, without salt

What's the best approach to convert into this:

Butter (01001, 01002, 01145, 04601, 04602) -> salted (01001)
                     -> whipped (01002) -> with salt (01002)
                     -> without salt (01145) 
                     -> light (04601, 04602) -> stick  (04601, 04602) -> with salt (04601)
                                                                      -> without salt (04602)

I was thinking of recursive sorting first, but I realized there may be a lot of string comparisons to be efficient.

Answer 1

It looks like you're making a tree based on elements after the first. Some quick pseudocode for this might look like:

 1. Start with a tree containing only the root.
 2. Set the current node to the root.
 3. Read a line of input = (ID, tail)
 4. For each object in tail, do
 5.     if the current node has a child equal to the current object, then
 6.         move to that child node
 7.         add the current ID to the list of IDs associated with that node
 8.     else,
 9.         add a new child node corresponding to the current object
10.         start a list of associated IDs using the current ID as the first entry
11. Repeat from step 2. until there is no more input

Showing this on your example:

Initial:
Root

Pass 1: (ID, tail) = (01001, (Butter, salted))
Root
- Butter (01001)
  - salted (01001)

Pass 2: (ID, tail) = (01002, (Butter, whipped, with salt))
Root
- Butter (01001, 01002)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)

Pass 3: (ID, tail) = (01145, (Butter, without salt))
Root
- Butter (01001, 01002, 01145)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)
  - without salt (01145)

...

Basically, you're constructing a tree, one branch at a time.