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

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.

• Copy your strings in a single array and replace each by its index. Can't you state your problem more formally? – babou Jun 24 '14 at 22:23
• I don't understand the specification of the problem. Giving one example isn't enough for me to tell what you want to happen in general. Also, what have you tried/considered? How do you plan to evaluate alternative proposals? What metrics or requirements do you plan to use to evaluate answers? – D.W. Jun 25 '14 at 0:07

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


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.