How do I implement a directed graph in C++ without using an adjacency list, given that the path of traversal...












1















[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?










share|improve this question























  • 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


















1















[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?










share|improve this question























  • 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
















1












1








1








[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?










share|improve this question














[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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










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





















  • 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














1 Answer
1






active

oldest

votes


















2














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)?






share|improve this answer

























    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    2














    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)?






    share|improve this answer






























      2














      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)?






      share|improve this answer




























        2












        2








        2







        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)?






        share|improve this answer















        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)?







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Nov 29 '18 at 19:24

























        answered Nov 21 '18 at 0:51









        johnathanjohnathan

        2,158819




        2,158819






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

            SQL update select statement

            'app-layout' is not a known element: how to share Component with different Modules