Mixing
How do I implement a directed graph in C++ without using an adjacency list, given that the path of traversal...
[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?
c++ directed-graph
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
add a comment |
[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?
c++ directed-graph
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40
add a comment |
[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?
c++ directed-graph
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
[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?
c++ directed-graph
c++ directed-graph
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
asked Nov 21 '18 at 0:32
Kat G FucciKat G Fucci
112
112
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40
add a comment |
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40
add a comment |
1 Answer
1
active
oldest
votes
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)?
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53403667%2fhow-do-i-implement-a-directed-graph-in-c-without-using-an-adjacency-list-give%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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)?
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
add a comment |
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)?
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
add a comment |
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)?
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
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)?
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
edited Nov 29 '18 at 19:24
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
answered Nov 21 '18 at 0:51
johnathanjohnathan
2,158819
2,158819
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53403667%2fhow-do-i-implement-a-directed-graph-in-c-without-using-an-adjacency-list-give%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
This is pretty broad. I'd recommend making an attempt, posting some code and your exact specifications to make this answerable and non-opinion-based. Beyond that, an adjacency matrix is probably not the way to go. Try node objects or a dictionary of arrays.
– ggorlen
Nov 21 '18 at 0:40