CODEWITHSUNDEEP
c++directed-graph
Kat G Fucci
Kat G Fucci

Reputation: 21

How do I implement a directed graph in C++ without using an adjacency list, given that the path of traversal will be the same every time?

[Disclaimer: I do not have any code yet, only concepts! Help with starting the code at all is why I'm here]

I want to code a "recipe book" type program (C++) for a game I'm playing, in which each ingredient will be a node, and will be assigned a tier based on the complexity of the ingredient. I want to use a directed graph, with an edge representing that one ingredient goes into making another; I'm trying for something like this. I will be traversing the graph by going through every node on the highest tier, then every node on the next tier down, and so on. So every time I traverse it, the path will be exactly the same.

I know that a graph can be implemented using an adjacency list, but that seems like overkill given that traversal is always the same and has a single overall direction to it. Is there another way; and if so, what is it?

Upvotes: 1

Views: 558

Answers (1)

johnathan
johnathan

Reputation: 2355

if you want recipe ingredients that has multiple parts

 std::map<unsigned int, std::vector<std::string>> myRecipeMap;

that would give you a complexity, ingredients pair where complexity could be the number of multiple parts to the ingredient, like some things are constructed from egg white and flour to make noodles.

if you need multiple complexities

 std::multimap<unsigned int, std::vector<std::string>>> myRecipeMap;

if you just need a complexity to ingredient name relationship

 std::map<unsigned int, std::string> RecipeBook;

and again multiple complexities

 std::multimap<unsigned int, std::string> RecipeBook;

that will give you complexity to recipe ingredient but not its sub components

I'm sure your aware that a std::map is a red black binary search tree, and while its NOT a graph I'm sorry for this answer if you choose this exercise specifically to learn how to write a graph. std::multimap is a sorted list.

This can all be accomplished in a simpler, and perhaps faster, albiet more clumsy manner with a vector of pairs of int and vector of strings for multiple parts of an ingrideant or a pair of int and string for just the ingrideant name. If you wanted to have the complexity and ingredient name along with its sub components 

 std::map<unsigned int, std::pair<std::string, std::vector<std::string>> Recipe;

The standard library components are entirely compose able to create some pretty complex data structures that can accommodate almost any problem.

Last why not forego this complxity and use a database like SQLite, MySql, MS SQL (developmemt server comes with the free visual studio)?

Upvotes: 2

Related Questions