[jayburn00]

macosxnerd101, on 18 July 2012 - 12:44 PM, said:

Do you know how to create a Linked List? It's the same general principle, except each Node has n children Nodes instead of one next Node.

I know the general idea of a linked list and how it works. I don't really know how to code one. Here is what I know how to do with reliability: for loop, if-else statements(all if type statements actually), case decisions, simple class objects with their attributes and methods, output and input, file reading and writing, and some other stuff. I understand most of the concepts for data structures(stacks, linked list, tree, queue, vectors, but I struggle in implimentation. I don't know the syntax to use or how to use them in the code.

[Skydiver]

Well it sounds like the instructions are pretty clear... there is an expectation that the data be stored in a binary search tree (unless BST means something else):

jayburn00, on 18 July 2012 - 12:42 PM, said:

Requirements: modify and complete the BST we have partially finished in the class accordingly and use it for the following program:

*snip*

2. Your program should the provide the user with the following options
a. Print the tree in level-order from root to leaves (hint: a stack can help)
b. Add new entry – the given entry will be in the same format as the file
c. Confirm

*snip*

The “confirm” option, worth 50 points, will take in a relation and answer true or false. The following relations must be implemented: ancestor(X,Y), decedent(X,Y), wife(X,Y), and husband(X,Y).

This post has been edited by Skydiver: 18 July 2012 - 01:48 PM

[jayburn00]

Skydiver, on 18 July 2012 - 01:46 PM, said:

Well it sounds like the instructions are pretty clear... there is an expectation that the data be stored in a binary search tree (unless BST means something else):

jayburn00, on 18 July 2012 - 12:42 PM, said:

Requirements: modify and complete the BST we have partially finished in the class accordingly and use it for the following program:

*snip*

2. Your program should the provide the user with the following options
a. Print the tree in level-order from root to leaves (hint: a stack can help)
b. Add new entry – the given entry will be in the same format as the file
c. Confirm

*snip*

The “confirm” option, worth 50 points, will take in a relation and answer true or false. The following relations must be implemented: ancestor(X,Y), decedent(X,Y), wife(X,Y), and husband(X,Y).

My teacher sent an email to clear that up. He said that it means take the code of the partial bst that we made in class and modify it to work in this case. He meant modify it in that it may no longer be a bst. My teacher's english is horrible, one of the reasons I struggle with the class, and as a result things that seem gramattically correct may not actually be what he meant to say.

[Skydiver]

2.a. Still makes no sense. Given:

Parent(Abel, Adam)
Parent(Abel, Eve)

as input. Is Adam or Eve the root with respect to the 2.a. requirement?

[jayburn00]

Skydiver, on 18 July 2012 - 02:50 PM, said:

2.a. Still makes no sense. Given:

Parent(Abel, Adam)
Parent(Abel, Eve)

as input. Is Adam or Eve the root with respect to the 2.a. requirement?

I don't know. One of the examples the teacher showed us was one where the children were the roots. The other example he showed us was where there was a 'dummy' parent, which was the main root node. Any parent from outside the family automatically was a child of the dummy parent, and the first parents were also the child of the dummy parent.

[jayburn00]

Skydiver, on 18 July 2012 - 02:50 PM, said:

2.a. Still makes no sense. Given:

Parent(Abel, Adam)
Parent(Abel, Eve)

as input. Is Adam or Eve the root with respect to the 2.a. requirement?

I don't know. One of the examples the teacher showed us was one where the children were the roots. The other example he showed us was where there was a 'dummy' parent, which was the main root node. Any parent from outside the family automatically was a child of the dummy parent, and the first parents were also the child of the dummy parent.

[jayburn00]

woops did not mean to double post. I found a program from an old text book I have from a previous class, its a geneology program, doesn't display as family tree, but uses a tree. A lot different from my assignment's program, but there is some useful stuff in it. By the way, anyone know how to create a tree that takes in input? The program I found in my older book has the family already in the code, and I find it a bit hard to follow. I will have the code type from my book later, I tried to split the files, but it did not like it and when I copy pasted, it only pasted part of it and I lost the other part so I am having to retype the book code. So irrelevant for now. Any other advice, suggestions, or reccomendations pertaining to the family tree program will be appreciated. Particularly anything relating to a tree taking in input the way described in my program specs.

[jon.kiparsky]

A tree doesn't take input, any more than an Array or a Linked List does. Your program might take input and modify the tree, but the tree is just a representation.


I think what you need to think about is, what are you trying to represent? What are the facts that matter here? One way to put that is, "what questions will this object answer?" And, naturally, "what sort of answers can I expect to get?"

The more I think about it, the less a "tree" makes sense for this, unless you're specifically interested in considering the "tree" as "the descendants of one anscestor". Suppose you want to go back a few generations to Hiram Q. Bullfinch, and map out his progeny, unto the seventh generation.

Okay, this view of the matter helps: now you can ignore half of the parents in the model, and you can treat the thing like a tree. You're interested in descendants of Hiram, and their descendants, and the associated spice* with whom they produced those descendants don't need to be nodes of the tree at all. From there, if we eliminate incestuous relationships, at least ones which produce offspring, then it's not difficult at all. A node of the tree has simply a list of child Nodes and possibly a pointer to its (singular!) parent. If you want to make notes about who the partners were, when the kids were whelped, whatever and whatnot, then you may do that, but none of that is structural.

If you want to be a little more realistic and represent the fact that someone's spouse also has a role in producing the offspring, you complicate the matter and as was suggested you start looking at something more like a directed graph, and more importantly you complicate the relation between one generation and the next. Do you represent a child node as coming off of both parents independently, or do you make a join node, or what do you do?
I confess, that looks to me like an ugly little problem. Since you're already having trouble with the notions of trees and graphs, I'd suggest you go with the Hiram Q. Bullfinch model.


*mouse:mice::spouse: ???

[jayburn00]

What about that idea with the dummy parent? Will that work? I did not really understand the Hiram Bullfinch thing. I thought you were talking about a tree being within a node which though I guess is possible, doesn't make much sense in this regard. Here is something I drew, messy and lines intersect, but it is how I understand the dummy parent idea. I know it doesn't look much like a tree, but bear with me. Also, I now know that spousal relationships are not direct connections, and doesn't even need to be the only spouse the person had. eg: all children need 2 parents, but only one parent has to be the same as the parent from the other child. Here is the tree with dummy parent:

[Skydiver]

My problem with the Dummy Parent idea is how do you deal with requirement 4.d without writing special case code. Specifically:
sibling(Joan, George) == true?
ancestor(Pete, Adam) == true?
descendant(Jack, Adam) == true?

And how do you deal with 2.b without writing special case code: child(Adam, Pete) --> error?

Or even better, assume that you start with an empty tree... How do you deal with: child(Cain, Adam)? Do you create parent named Adam who is different from the dummy parent, and make Cain the child of Adam?

[jayburn00]

Skydiver, on 19 July 2012 - 11:46 PM, said:

My problem with the Dummy Parent idea is how do you deal with requirement 4.d without writing special case code. Specifically:
sibling(Joan, George) == true?
ancestor(Pete, Adam) == true?
descendant(Jack, Adam) == true?

And how do you deal with 2.b without writing special case code: child(Adam, Pete) --> error?

Or even better, assume that you start with an empty tree... How do you deal with: child(Cain, Adam)? Do you create parent named Adam who is different from the dummy parent, and make Cain the child of Adam?

Actually in this case Adam was just a place holder. We can name it anything we like. In the teachers example, he got a little mixed up on what animals we are descended from and put Baboon as the dummy parent. Also, I think creating lines of code where if the parent is dummy parent then its children are not siblings would solve that problem. As for tree not working for this stuff, I can't take that as an answer. The teacher suggested a bitree by the way, not clear on what that is though.

[Skydiver]

Yes, I know that you were using "Adam" as a place holder. My point, though, is if the user knows the placeholder's name, the weird stuff can happen unless you start writing special case code to deal with it.

I think your teacher was talking about B-trees. It works if you know ahead what the maximum number of children will be. So for the assignment, I think it would be perfect since he specified 2 children maximum. Setting up the spouse relationships will still be tough, though.

Actually, the more I think about it, the spouse relationship need not be hard as long as the spouse relationship is viewed an attribute of the data, and not an attribute of the graph. By "attribute of the data", I mean the same way the male(X)/female(X) listed in the requirements in an attribute of the person and makes no difference on how the graph is structured. So likewise, nodes can have have one (or more?) spouse (spice? ) pointer(s) to indicate the spouse relationships, but these pointers are never used for navigation through the graph.

This post has been edited by Skydiver: 20 July 2012 - 03:07 PM

[jayburn00]

Skydiver, on 20 July 2012 - 03:01 PM, said:

Yes, I know that you were using "Adam" as a place holder. My point, though, is if the user knows the placeholder's name, the weird stuff can happen unless you start writing special case code to deal with it.

I think your teacher was talking about B-trees. It works if you know ahead what the maximum number of children will be. So for the assignment, I think it would be perfect since he specified 2 children maximum. Setting up the spouse relationships will still be tough, though.

Actually, the more I think about it, the spouse relationship need not be hard as long as the spouse relationship is viewed an attribute of the data, and not an attribute of the graph. By "attribute of the data", I mean the same way the male(X)/female(X) listed in the requirements in an attribute of the person and makes no difference on how the graph is structured. So likewise, nodes can have have one (or more?) spouse (spice? ) pointer(s) to indicate the spouse relationships, but these pointers are never used for navigation through the graph.

Ok, your thing kind of makes more sense now. Also I was thinking, if a person has a child, since every child has 2 parents, couldn't they then use the fact that the child is going to have a connection to two nodes to simply use the child to find a spouse?

[Skydiver]

Actually, that maybe the only way to do it... Taking another look at the requirements list, there is no spouse(X, Y) input. There is only a spouse(X, Y) query. Since there is no spouse(X, Y) input, there is no need to have a spouse pointer.

[jayburn00]

Ok, I just ran into one snag with the btree idea. It won't work with the dummy parent, because you won't know how many children of the dummy parent there are later. Remember this program will be use any variant on the input spoken above, including user input. Also, I got all the bugs worked out of this example from an old book of mine. It looks very workable based on output, but I will have to change the 'main' function to use input to generate the 'Persons' instead of having them predefined in the program. Also, I don't know how I will implement 2 in the assignment. However, I have a lot of questions about the code itself, because I am a bit confused at times about what is going on. So here it is, with the lines/functions I am unclear on commented with a question:

#include <vector>
#include <string>
#include <iostream>
using namespace std;
enum Gender{male, female};


class Person
{
	string name;//this part I understand
	Gender gender;//this part I understand
	vector<Person *> parents;//I understand the vector part, but the rest of this line I go huh?
	vector<Person *> children;//Same as above
	void addParent(Person *p){parents.push_back(p);}//understand this is a function, but don't understnad much else about it.
public:
	Person(string name, Gender g)
	{
		this->name = name;//Since there are multiple instances of Person, it uses 'this' to specify unique name for this instance. Is that right?
		gender = g;
	}
	Person *addChild(string name, Gender g);
	Person *addChild(Person *p);//explain this part, why do these function have asterisks?
	friend ostream &operator << (ostream &out, Person p);//What exactly is this for?

	//member functions for getting info of Person

	string getName(){return name;};
	Gender getGender(){return gender;}
	int getNumChildren(){return children.size();}
	int getNumParents(){return parents.size();}
	Person *getChild(int k);
	Person *getParent(int k);
};


	
	//Create child and set one parent
Person *Person::addChild(string name, Gender g)//why the 'Person *Person?  Is it to indicate a pointer to a different person?
{
		Person *child = new Person(name, g);//Shouldn't there be a destructor also?
		child->addParent(this); //Parent of this child.  I don't understand the use of 'this' on this line.
		children.push_back(child);  //This is child of parent.
		return child;
}

	//add child of parent
Person *Person::addChild(Person* child)
{
		child->addParent(this); //parent of this child.  Don't understand use of 'this' here.
		children.push_back(child); //children of parent
		return child;
}

//return pointer to specified parent
Person *Person::getParent(int k)//
{
	if (k<0 || k>= parents.size())
	{
		cout<<"Error indexing."<<endl;
		exit(1);
	}
	return parents[k];
}

//return pointer to child
Person *Person::getChild(int k)
{
	if (k<0 || k>=children.size())
	{
		cout<<"error indexing child vector"<<endl;
		exit(1);
	}
	return children[k];
}

//Overloaded stream output operator
ostream & operator<<(ostream & out, Person p)//is this creating an 'out' operator?  please explain this function/operator overload
{
	out<<"<person name = " << p.name <<">"<<'\n';
	if (p.parents.size() > 0)
		out<<"  <parents>"<<' ';
	for (int k = 0; k<p.parents.size(); k++)
	{
		out<< " " <<p.parents[k]->name<<' ';
	}
	if (p.parents.size() > 0)
	{
		out<<"</parents>"<<"\n";
	}
	if (p.children.size()>0)
		out << "  <children>"<< ' ';
	for (int k=0; k < p.children.size(); k++)
	{
		out<<" "<<p.children[k]->name<< ' ';
	}
	if (p.children.size() > 0)
		out<<" </children>" << "\n";
	out<< "</person>" << "\n";
	return out;
}

//driver stub I think
int main(int argc, char** argv)
{
	Person adam("Adam", male);
	Person eve ("Eve", female);
	Person joan("Joan", female);

	//Adam and Eve are parents of Abel
	Person *pAbel = eve.addChild(new Person("Abel", male));
	adam.addChild(pAbel);

	//Abel and Joan are parents of missy
	Person *pMissy = joan.addChild("Missy", female);
	pAbel->addChild(pMissy);

	//output all people
	cout<< "Here are all the people:\n\n";
	cout<< adam << eve;
	cout<< *pAbel << joan;
	cout<< *pMissy << "\n";

	//Print parents for Missy
	cout<< "Missy's parents are:  "<<endl;
	for (unsigned int k=0; k < pMissy->getNumParents(); k++)
	{
		Person * p = pMissy ->getParent(k);
		switch(p->getGender())
		{
		case female : cout<<"\tMother:  "; break;
		case male : cout<<"\tFather:  "; break;
		}
		cout<<p->getName()<<endl;
	}
	return 0;
}

If someone could take the time to explain any line where a period is used, a back slash, any number of colons, asterisks, or ->, I would appreciate that as well. I am also trying to prepare for a final and I am trying very hard to comprehend this stuff. It has been an uphill struggle with this teacher, but I also think that I have forgotten a good amount of syntax, hence the desire explanations. Thanks in advance.