Thread: Linked Lists for Research Trees?

  1. #1
    Registered User
    Join Date
    Apr 2004
    Location
    Ohio
    Posts
    147

    Question Linked Lists for Research Trees?

    I want to implement a reasearch tree into a program that I'm writting right now. However, what would be the best way to do such a thing?

    Maybe a modified version of a linked list?


    VISUAL EXAMPLE:

    Code:
    RESEARCH1 --
    	     \
    	      } -- RESEARCHX --
                 /                  \
    RESEARCH2 --                     \
                                      } -- RESEARCH Z
    RESEARCH3 --                     /
    	     \                  /
    RESEARCH4 --  } -- RESEARCHY --
                 /
    RESEARCH5 --
    RESEARCHX needs only two previous types of research completed before it can be researched whereas RESEARCHY needs 3. The idea is to make the tree flexible enough that I can have any number of 'modules' complete before the next ones can be complete.

    I hope that this is clear...

    Leeor...
    Last edited by leeor_net; 09-03-2004 at 10:11 AM. Reason: redoing the visual example

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    what is the max height of your tree? If it is just 2 (from your picture) then it doesn't really matter what data structure you use to represent it.

    If you don't know the max size, then I would probably use a modified version of a B-tree.

    Are there any other rules for this structure?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    I'd consider using the composite design pattern.

    The research base class would have a list (or a vector, deque, map, etc) of pointers to research base class objects. You would create functions to add a child, enumerate the children (if necessary), clear the children and delete the memory, and perform the meaningful operations common to all research types.

    You could then define a derived class for each type of research if they each must be implemented differently. If not, then you could just leave the base class and use member variables to distinguish between research types.

    When you create each actual research type you create an instance of the derived class and add a pointer to it to the appropriate parent. Once you have built your tree, it makes it very easy to process all the nodes in a generic way, you can use depth first or breadth first traversal to do what you need to do.

    Anyway, that's just one idea that might be useful depending on your needs. I did something like this recently and it made things very easy to extend and implement once the original code was set up.

  4. #4
    Registered User
    Join Date
    Apr 2004
    Location
    Ohio
    Posts
    147

    E.G. - Technologies

    Well, the basic idea behind the research tree is for a series of different paths. The one represented above would be maybe one path that leads to an ultimate goal.

    However, there could be numerous paths.

    For example:

    Code:
    > ===== Agricultural Studies ==
    |        |
    |        |----> Hydroponic Growing Media
    |        |
    |        |-----> Expanded Hydroponics
    |                 |
    |                 |-----> Large Scale Condenser Circuit
    |                 |
    |                 |-----> Genetic Food Engineering
    |                          |
    |                          |-----> Advanced Genetics
    |                          |
    |                          |-----> Artificial Flavoring
    |                          |
    |                          |-----> Food Synthesis
    |                                   |
    |                                   |-----> Synthetic Protein
    |                                   |
    |                                   |-----> Synthetic Fiber
    |
    |
    > ===== Geographical Studies ==
    |     |
    |     |-----> General Geology
    |              |
    |              |-----> Seismology
    |              |        |
    |              |        |-----> Structural Shock-Resistant Housing
    |              |
    |              |-----> Vulcanology
    |                       |
    |                       |-----> Lava Diversion Walls
    |                       |
    |                       |-----> Volcanic Activity Pre-Warning
    |                       |
    |                       |-----> Lava-Based Mineral Deposits
    |                                |
    |                                |-----> Lava Mineral Extraction
    These are not the entries I intend to use but serve as just a sample.

    The idea that I have is to start with the root of RESEARCH. After that there would be the general catagory such as AGRICULTURE, GEOLOGY, COSMOLOGY (does that even exist?), MYTHOLOGY, etc. Within each of those catagories would be the rest of them.

    Now, the thought that I have right now is to create a modified version of a binary tree. Well, in essence it's not a binary tree at all. But anyway, here goes:

    Each 'node' can have up to let's say 6 entries. Each entry, naturally, can have 6 leaves plus the name of the research, what type of research (basic or advanced), how long it takes to complete and whether or not it has been completed. The tree would be pre-built or maybe could be built at run-time (would I use a text file or should I just hard code it?).

    Is the concept here sound or am I going about it all the wrong way?

    Thanks for your time, all!

    Leeor...

  5. #5
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    Here is an example of one way to do it. There are no derived classes because all of the data and behavior of the types are the same. You would probably want to create the objects based on input from a file, but I didn't feel like taking the time to figure that out right now. You would have to add all other behavior - like how to set the research to complete - or anything else you need.
    Code:
    #include <iostream>
    #include <string>
    #include <list>
    
    // RESEARCH CLASS
    class ResearchBase
    {
    public:
        ResearchBase(const std::string& researchName,
                     bool thisResearchCompleted,
                     unsigned int daysToCompleteThis);
        virtual ~ResearchBase();
    
        bool ResearchCompleted() const;
        int DaysToComplete() const;
        void Output(std::ostream& out, unsigned int indent = 0) const;
    
        void AddChild(ResearchBase* researchBase);
    
    protected:
        ResearchBase* GetFirstChild() const;
        ResearchBase* GetNextChild() const;
    
    private:
        void ClearChildren();
    
        std::string researchName_;
        bool thisResearchCompleted_;
        unsigned int daysToCompleteThis_;
    
        typedef std::list<ResearchBase*> ChildPointerList;
        ChildPointerList m_listChildren;
        // declare after the list for proper initialization
        mutable ChildPointerList::const_iterator m_iterChild;
    };
    
    ResearchBase::ResearchBase(const std::string& researchName,
                               bool thisResearchCompleted,
                               unsigned int daysToCompleteThis)
     : researchName_(researchName),
       thisResearchCompleted_(thisResearchCompleted),
       daysToCompleteThis_(daysToCompleteThis),
       m_iterChild(m_listChildren.end())
    {
    }
    
    ResearchBase::~ResearchBase()
    {
        ClearChildren();
    }
    
    bool ResearchBase::ResearchCompleted() const
    {
        ResearchBase* childResearch = GetFirstChild();
        while (childResearch)
        {
            if (!childResearch->ResearchCompleted())
                return false;
    
            childResearch = GetNextChild();
        }
    
        return thisResearchCompleted_;
    }
    
    int ResearchBase::DaysToComplete() const
    {
        unsigned int days = daysToCompleteThis_;
    
        ResearchBase* childResearch = GetFirstChild();
        while (childResearch)
        {
            days += childResearch->DaysToComplete();
            childResearch = GetNextChild();
        }
    
        return days;
    }
    
    void ResearchBase::Output(std::ostream& out, unsigned int indent/* = 0*/) const
    {
        if (indent != 0)
            out << std::string(indent, ' ');
    
        out << researchName_ << ": Days To Complete: " << DaysToComplete() << " -- ";
        if (ResearchCompleted())
            out << "COMPLETED";
        else
            out << "INCOMPLETE";
    
        out << std::endl;
    
        ResearchBase* childResearch = GetFirstChild();
        while (childResearch)
        {
            childResearch->Output(out, indent + 2);
            childResearch = GetNextChild();
        }
    }
    
    void ResearchBase::AddChild(ResearchBase* researchBase)
    {
        m_listChildren.push_back(researchBase);
    }
    
    ResearchBase* ResearchBase::GetFirstChild() const
    {
        m_iterChild = m_listChildren.begin();
        if (m_iterChild != m_listChildren.end())
            return *m_iterChild;
        return 0;
    }
    
    ResearchBase* ResearchBase::GetNextChild() const
    {
        if (m_iterChild == m_listChildren.end())
            return 0;
        if ((++m_iterChild) != m_listChildren.end())
            return *m_iterChild;
        return 0;
    }
    
    void ResearchBase::ClearChildren()
    {
        m_iterChild = m_listChildren.begin();
        ChildPointerList::const_iterator iterEnd = m_listChildren.end();
        for (; m_iterChild != iterEnd; ++m_iterChild)
            delete (*m_iterChild);
        m_listChildren.clear();
        m_iterChild = m_listChildren.end();
    }
    
    // CREATION
    int main()
    {
      std::auto_ptr<ResearchBase> rootResearch(new ResearchBase("RESEARCH", true, 0));
        ResearchBase* researchAgStudies = 
          new ResearchBase("Agricultural Studies", true, 0);
        rootResearch->AddChild(researchAgStudies);
          ResearchBase* researchHydropGrMedia =
            new ResearchBase("Hydroponic Growing Media", false, 30);
          researchAgStudies->AddChild(researchHydropGrMedia);
          ResearchBase* researchExpHydrop =
            new ResearchBase("Expanded Hydroponics", false, 2);
          researchAgStudies->AddChild(researchExpHydrop);
            ResearchBase* researchLScCndsCircuit =
              new ResearchBase("Large Scale Condenser Circuit", true, 2);
            researchExpHydrop->AddChild(researchLScCndsCircuit);
            ResearchBase* researchGenFoodEng =
              new ResearchBase("Genetic Food Engineering", true, 0);
            researchExpHydrop->AddChild(researchGenFoodEng);
              ResearchBase* researchAdvGenetics =
                new ResearchBase("Advanced Genetics", true, 3);
              researchGenFoodEng->AddChild(researchAdvGenetics);
              ResearchBase* researchArtFlavoring =
                new ResearchBase("Artificial Flavoring", true, 5);
              researchGenFoodEng->AddChild(researchArtFlavoring);
              ResearchBase* researchFoodSynth =
                new ResearchBase("Food Synthesis", true, 0);
              researchGenFoodEng->AddChild(researchFoodSynth);
        ResearchBase* researchGeoStudies =
          new ResearchBase("Geographical Studies", true, 0);
        rootResearch->AddChild(researchGeoStudies);
          ResearchBase* researchGenGeology =
            new ResearchBase("General Geology", true, 0);
          researchGeoStudies->AddChild(researchGenGeology);
            ResearchBase* researchSeismology =
              new ResearchBase("Seismology", true, 10);
            researchGenGeology->AddChild(researchSeismology);
              ResearchBase* researchStrShockResHousing =
                new ResearchBase("Structural Shock-Resistant Housing", true, 8);
              researchSeismology->AddChild(researchStrShockResHousing);
            ResearchBase* researchVulcanology =
              new ResearchBase("Vulcanology", true, 3);
            researchGenGeology->AddChild(researchVulcanology);
              ResearchBase* researchLavaDivWalls =
                new ResearchBase("Lava Diversion Walls", false, 5);
              researchVulcanology->AddChild(researchLavaDivWalls);
              ResearchBase* researchVolcActPreWarning =
                new ResearchBase("Volcanic Activity Pre-Warning", false, 5);
              researchVulcanology->AddChild(researchVolcActPreWarning);
              ResearchBase* researchLavaMinDeposits =
                new ResearchBase("Lava-Based Mineral Deposits", true, 1);
              researchVulcanology->AddChild(researchLavaMinDeposits);
    
        rootResearch->Output(std::cout);
    }
    Last edited by jlou; 09-03-2004 at 01:53 PM. Reason: forgot to delete the root!

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Is the concept here sound or am I going about it all the wrong way?
    No, that looks about what I would do if I lacked an appropriate library. What you are thinking of is a tree structure similar to a B-tree, but lacking the balancing hell. Each node would have a list of links (possible a linked list, but probably an array of some form). Each link has its own list of links and so on until you run out of research paths.

    An interesting brain teaser would be to devise a way for separate paths to open up new branching options earlier in the tree as they are followed.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Apr 2004
    Location
    Ohio
    Posts
    147
    Cool. I'm glad I have at least a general way to go... ^_^

    Anyway, the brain teaser is probably something I'm going to add to it in the future (for later games or something0.

    Hehe... B-Tree balancing certainly is hell. That's why BSP Trees are so horrible! (Ugh... I'm still trying to figure them out!)

    Thanks for the tip!

    BTW:
    I typically don't like looking at code unless there's really no other way to describe something. Looking at code doesn't help me much (I end up writting my own in the end).

    Thanks all!

  8. #8
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    By the way, I still think a form of the composite design pattern would help you a lot here.

    I would hope you would write your own code in the end - code examples are meant to be understood, not copied. But I promise not to use code to describe stuff for you in the future... if I remember who you are.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. Linked lists and Binary trees
    By Scotty in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 07-04-2002, 06:59 PM
  5. arrays, linear linked lists and binary trees
    By jasingle in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2001, 11:12 AM