I like to tell people I can explain the universe by explaining a sandwich. I then use this opportunity to trick them into learning about data structures. This sandwich based data structure is something I built about a year ago. I haven’t really updated it since I built it. However, I wanted to talk about it because I think it’s one of my favorite database structures I’ve had to implement. It’s somewhat complicated, but it’s easy to explain. The project was for a software engineering class. Originally we were gonna work with some company on an angular modules project, but then we decided we wanted to do our own thing. We wanted to implement something in the MEAN stack. For a lot of members in my team, this was their first web development experience. For me, this was my first experience using the MEAN stack. I gravitated towards the backend because I like to think about data structures.
The idea we came up with is a recipe search engine. We called it recipe stacker because you simply input ingredients and it finds recipes with those ingredients in them. The front end is pretty awesome, that was most of our team member's original goal, to learn angular. So a lot of time was spent focusing on the front end. I did a bit of work on the front end, but the backend is what interested me.
I had never worked with a non-relational database before. So the sandwich based schema I came up with turned out to be a nightmare. Also this was my first time working with NodeJS. Needless to say my code isn’t very pretty, and I’m not gonna show much of it. What I think is more interesting is the actual database structure, and what it allows us to do.
The idea is that there are three basic types of data structures that make up our recipes. There is a Composition, Abstract, and Primitive structure.
The rules are as follows:
- A Composition can be thought of as a recipe. This might be something like “A Sandwich”. A Composition has many children. The children can be other Compositions, Abstract, or primitive ingredients.
- An Abstract ingredient can be thought of as a category. This might be something like “Bread”. In which there are many different types of bread. Such as sourdough, wheat, rye, etc. An Abstract may have other Abstracts, compositions, or primitives as children.
- A Primitive ingredient is something that cannot be made any simpler. This is something like “Heirloom tomato”. You go to the store and buy a Heirloom tomato. It’s not ambiguous, you can’t create it, and it doesn’t get simpler than that. At the same time a brand name item might be a primitive ingredient. Such as “Heinz Ketchup”.
Here is a diagram that explains the structure:
Now that we have this structure. Let’s imagine how we would construct a sandwich. Let’s make a Roast Beef Sandwich. Here’s the tree structured diagram of what that might look like:
I also have a theorem in there because I’m some sort of nerd. Yellowish nodes are compositions, purple nodes are Abstracts, and green nodes are leaves.
Take special note. It’s not obvious in this diagram, but every leaf is a primitive ingredient. The diagram has unexplored purple nodes, but those aren’t leaves in the entire data structure. Those can be expanded. Think about what this means for a second, the diagram above is not fully explored. It’s not displaying all leaves. Think about what it means for the diagram to become fully explored.
The idea behind recipe stacker is to input ingredients that you have, and find recipes that fit that criteria. This data structure allows for that, but it’s not entirely efficient at that. I kind of forgot the agenda and started exploring my own agenda. My grand idea was to create a recipe website where you can dive as deep into the process as you’d like. What does it mean to make an apple pie? To quote Carl Sagan, “If you wish to make an apple pie from scratch, you must first invent the universe.”
On this website you can search for a roast beef sandwich recipe, and see a very simple recipe: Bread, Roast beef, Mayo, Tomato, Lettuce. These are all Abstract ingredients. However, what if I wanted to make my Roast Beef? Well, I would just click on Roast beef and be presented with the compositions that belong to this Abstract ingredient. I can do this with every component of the recipe. I can dig deeper and deeper, until I’m processing my own sugar and flour. This structure let’s you define what it means to “Make a sandwich”. Your sandwich can take you all month to make, if you’d like.
It’s all mostly functional. I had trouble creating a taxonomy of ingredients, and a lot of the attention was focused on the front end aspects. You can construct these recipes here: http://jayd.sauce.do/recipestacker
You can check out a very simple example of the structure with this recipe: http://220.127.116.11/#/details/$54610f449b4e07510abb2256
However, this recipe doesn’t really dive that deep and the UI doesn’t convey the structure very well.
Whenever I need to explain data structures to someone. This is how I do it. With a sandwich and three simple data structures. Then I ask the question: “What if I referenced my sandwich from within my sandwich?” Infinite sandwich! The next question. Is this limited to recipes? No, this data structure can explain everything!
You can check out the code here, but I’m warning you. It’s pretty ugly. You really shouldn’t use a nonrelational database on something like this. A lesson hard learned.https://github.com/erikmellum/RecipeStacker