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...

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?

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.

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...

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

>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. :)

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! :cool:

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