Multiple Tree

[sadsdw]

Hi everyone,

I'm trying develop a code to read a file containing records of INDIVIDUAL ID, FATHER ID and MOTHER ID, and re-code the file using multiple trees. At this point I'm not concerning to re-code the IDs and I would like to build the multiple tree.
The idea is:

A) Read each line from the genealogy file and connect the individuals by theirs fathers or mothers.
B) If the individual doesn't have father or mother, I will set father and mother as NULL. Tree disconnected from the others.
C) If the individual has father or mother (Or if the individual is father or mother), I need to connect him to respective node.

Below, I typed a simple example and my first code. I don't know how to manipulate the pointers to build the multiple tree. I was planning to retrieve information from the vectors and build the tree. Could anyone help me?

Thanks a lot!

File:

1 0 0
2 0 0
3 14 20
14 999 6
20 10 1000
30 999 7

Multiple Tree:

1) NULL(F) NULL(M)
1(I)

2) NULL(F) NULL(M)
2(I)

3) [999(F) 6(M)] [10(F) 1000(M)]
[14(I)(F)] [20(I)(M)] // 14 is son of 999 and 6 and father of 3
3(I)

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <ctype.h>

using namespace std;

struct TreeGen *get_AniGeneal(void);    /* Prototype for input function */
char set_ancestry(struct TreeGen *pmember1, struct TreeGen *pmember2);
char related (struct Family *pmember1, struct Family *pmember2);
void getGeneal(ifstream &myfileGenealOriginal,ofstream &myfileLog, ofstream &myfileOut,vector<int> &vetorGenealOrigIndiv,vector<int> &vetorGenealOrigFather,vector<int> &vetorGenealOrigMother);
void printIntV(ofstream &myfileLog,vector<int>& a);
void buildTree(M &top, int indiv, int father, int mother);

typedef struct STreeGen                      /* Family structure declaration   */
{
  int indiv;
  int father;
  int mother;

  struct STreeGen *pFather;         /* Pointer to father structure   */
  struct STreeGen *pMother;         /* Pointer to mother structure   */
} Tree;

typedef Tree *M;

int main ()
{

	vector<int> vetorGenealOrigIndiv;
	vector<int> vetorGenealOrigFather;
	vector<int> vetorGenealOrigMother;

	ifstream myfileGenealOriginal;
	ofstream myfileOut; 	// OUTPUT END FILE
	ofstream myfileLog;

	myfileGenealOriginal.open("ped.txt");
	myfileLog.open("log.txt");
	myfileOut.open("out.txt");

	getGeneal(myfileGenealOriginal,myfileLog, myfileOut,vetorGenealOrigIndiv,vetorGenealOrigFather,vetorGenealOrigMother);



   return 0;
}

void getGeneal(ifstream &myfileGenealOriginal,ofstream &myfileLog, ofstream &myfileOut,vector<int> &vetorGenealOrigIndiv,vector<int> &vetorGenealOrigFather,vector<int> &vetorGenealOrigMother)
{
	string lineGenealOrig = "";
	int indivV = 0;
	int fatherV =0;
	int motherV = 0;

	if ( myfileGenealOriginal.is_open() )
	{
	       	 while(myfileGenealOriginal >> lineGenealOrig)
	         {
					  istringstream (lineGenealOrig) >> indivV;
	        	      vetorGenealOrigIndiv.push_back(indivV);

	        	      myfileGenealOriginal >> lineGenealOrig;
	        	      istringstream (lineGenealOrig) >> fatherV;
	        	      vetorGenealOrigFather.push_back(fatherV);

	        	      myfileGenealOriginal >> lineGenealOrig;
	        	      istringstream (lineGenealOrig) >> motherV;
	        	      vetorGenealOrigMother.push_back(motherV);
	         }
	}
	else
	{
	  cout << "Unable to open file Original File" << endl;
	}

		myfileLog << "\nPrinting  ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigIndiv);
		myfileLog << "\nPrinting Father ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigFather);
		myfileLog << "\nPrinting Mother ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigMother);
}

void printIntV(ofstream &myfileLog,vector<int>& a)
{
	for(int i=0; i<a.size(); ++i)
		myfileLog << a[i] << "\n";
}

void buildTree(M &top, int indiv, int father, int mother)
{
	M NOaux;

	NOaux = top; // PRESERVAR "TOPO" INTACTO
	if(NOaux == NULL)
	{
		NOaux = new(Tree);
		NOaux->indiv = indiv;
		NOaux->father = father;
		NOaux->mother = mother;
		top = NOaux;
	}
	else
	{

	}

}

[mike_2000_17]

I think you are going about this the wrong way. You should first think logically about what your program will have to do. Here is what I would say your program needs to do (at high level):

1) Read the IDs of the individual, and parents.
2) Create a record for the individual.
3) Find the records of the parents and link them to the individual's record.

Now, you have the reading part done correctly, although, this might be simpler:

while(myfileGenealOriginal >> indivV) {
    myfileGenealOriginal >> fatherV >> motherV;
  
    //do step 2 and 3 here.
  };

Then, you did step 2 correctly, in some sense, but now you are stuck at step 3 because you didn't do step 2 in a way that would facilitate step 3. In C++, you have many choices of containers, including associative containers which allow you to associate a key-value to each record. In this case, the most appropriate container for your individual records would probably be std::map. This container will allow you to be able to look-up individuals based on their ID directly and efficiently. Furthermore, if you look-up an ID that doesn't exist, then it will be created. This is perfect because it allows you to do step 2 and 3 at the same time. For example:

map<int, STreeGen> IndivMap;
  while(myfileGenealOriginal >> indivV) {
    STreeGen& current_indiv = IndivMap[indivV];
    current_indiv.indiv = indivV; //assign ID to the new record at ID indivV.

    myfileGenealOriginal >> fatherV >> motherV;

    // current_indiv.father = fatherV; //this is useless.
    // current_indiv.mother = motherV; //this is useless.
    current_indiv.pFather = ( fatherV ? &IndivMap[fatherV] : NULL );
    current_indiv.pMother = ( motherV ? &IndivMap[motherV] : NULL );
  };

And that is it. Now, the entries "father" and "mother" as integer IDs in the individual records are useless, you could get rid of them. Notice also, that, in the above, if you have not yet "loaded" a mother or father, it won't matter, their nodes will be created by accessing them in the std::map.

[sadsdw]

Hi,

I'm posting a new version of my code but I still need help ... :(

Thanks!

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <ctype.h>

using namespace std;


void getGeneal(ifstream &myfileGenealOriginal,ofstream &myfileLog, ofstream &myfileOut,vector<int> &vetorGenealOrigIndiv,vector<int> &vetorGenealOrigFather,vector<int> &vetorGenealOrigMother);
void printIntV(ofstream &myfileLog,vector<int>& a);
void buildTree(int &indiv, int &father, int &mother);

struct STreeGen                      /* Family structure declaration   */
{
  int indiv;
  int father;
  int mother;

  struct STreeGen *pFather;         /* Pointer to father structure   */
  struct STreeGen *pMother;         /* Pointer to mother structure   */
} ;



int main ()
{
	STreeGen *t;

	vector<int> vetorGenealOrigIndiv;
	vector<int> vetorGenealOrigFather;
	vector<int> vetorGenealOrigMother;

	int auxIndividual = 0;
	int auxFather = 0;
	int auxMother = 0;

	ifstream myfileGenealOriginal;
	ofstream myfileOut; 	// OUTPUT END FILE
	ofstream myfileLog;

	myfileGenealOriginal.open("ped.txt");
	myfileLog.open("log.txt");
	myfileOut.open("out.txt");

	getGeneal(myfileGenealOriginal,myfileLog, myfileOut,vetorGenealOrigIndiv,vetorGenealOrigFather,vetorGenealOrigMother);

	for(int i=0; i< vetorGenealOrigIndiv.size();i++)
	{
		auxIndividual = vetorGenealOrigIndiv[i];
		auxFather = vetorGenealOrigFather[i];
		auxMother = vetorGenealOrigMother[i];
		buildTree(auxIndividual,auxFather,auxMother);
	}


   return 0;
}

void getGeneal(ifstream &myfileGenealOriginal,ofstream &myfileLog, ofstream &myfileOut,vector<int> &vetorGenealOrigIndiv,vector<int> &vetorGenealOrigFather,vector<int> &vetorGenealOrigMother)
{
	string lineGenealOrig = "";
	int indivV = 0;
	int fatherV =0;
	int motherV = 0;

	if ( myfileGenealOriginal.is_open() )
	{
	       	 while(myfileGenealOriginal >> lineGenealOrig)
	         {
					  istringstream (lineGenealOrig) >> indivV;
	        	      vetorGenealOrigIndiv.push_back(indivV);

	        	      myfileGenealOriginal >> lineGenealOrig;
	        	      istringstream (lineGenealOrig) >> fatherV;
	        	      vetorGenealOrigFather.push_back(fatherV);

	        	      myfileGenealOriginal >> lineGenealOrig;
	        	      istringstream (lineGenealOrig) >> motherV;
	        	      vetorGenealOrigMother.push_back(motherV);
	         }
	}
	else
	{
	  cout << "Unable to open file Original File" << endl;
	}

		myfileLog << "\nPrinting  ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigIndiv);
		myfileLog << "\nPrinting Father ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigFather);
		myfileLog << "\nPrinting Mother ID: " << endl;
		printIntV(myfileLog,vetorGenealOrigMother);
}

void printIntV(ofstream &myfileLog,vector<int>& a)
{
	for(int i=0; i<a.size(); ++i)
		myfileLog << a[i] << "\n";
}

void buildTree(int &indiv, int &father, int &mother)
{
	STreeGen *t;

	if(father == 0 and mother == 0)
	{
		t = new STreeGen;
		t->indiv = indiv;
		t->father = NULL;
		t->mother = NULL;
	}
	else if(father != 0 and mother == 0)
	{
		t = new STreeGen;
		t->indiv = indiv;
		t->father = father;
		t->mother = NULL;

	}
	else if(father == 0 and mother != 0 )
	{
		t = new STreeGen;
		t->indiv = indiv;
		t->father = NULL;
		t->mother = mother;
	}

}

[sadsdw]

Hi Mike,

I'm new in C++ ... I will read with attention your comments and I'm going to try adapt it in my code.

Thank you very much!

[sadsdw]

Hi Mike,

This is the final version of my code after your suggestions. Can you check where I made mistake please?

Thanks a lot

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <ctype.h>
#include <map>

using namespace std;


struct STreeGen                      /* Family structure declaration   */
{
  int indiv;
  int father;
  int mother;

  struct STreeGen *pFather;         /* Pointer to father structure   */
  struct STreeGen *pMother;         /* Pointer to mother structure   */
} ;



int main ()
{

	vector<int> vetorGenealOrigIndiv;
	vector<int> vetorGenealOrigFather;
	vector<int> vetorGenealOrigMother;

	string lineGenealOrig = "";
	int indivV = 0;
	int fatherV =0;
	int motherV = 0;

	ifstream myfileGenealOriginal;
	ofstream myfileOut; 	// OUTPUT END FILE
	ofstream myfileLog;

	myfileGenealOriginal.open("ped.txt");
	myfileLog.open("log.txt");
	myfileOut.open("out.txt");

	// ----------------------------
		map<int, STreeGen> IndivMap;
	// ----------------------------

	while(myfileGenealOriginal >> indivV)
	{

		STreeGen& current_indiv = IndivMap[indivV];
		current_indiv.indiv = indivV; //assign ID to the new record at ID indivV.

		myfileGenealOriginal >> fatherV >> motherV;

		current_indiv.pFather = ( fatherV ? &IndivMap[fatherV] : NULL );
		current_indiv.pMother = ( motherV ? &IndivMap[motherV] : NULL );
	};

	cout << "PRINTING:" << endl;

	map<int, STreeGen> :: const_iterator iter;
	for (iter = IndivMap.begin(); iter != IndivMap.end(); ++iter)
	{

		cout << iter->first << '\t' << iter->second.pFather << " " << iter-> second.pMother << '\n';

	}

   return 0;
}

[mike_2000_17]

What error do you get? This all seems fine to me.

I trimmed it down to bare essentials (as one should), and got this code:

#include <iostream>
#include <fstream>
#include <vector>
#include <map>

struct STreeGen                      /* Family structure declaration   */
{
  int ID;
  STreeGen *father;         /* Pointer to father structure   */
  STreeGen *mother;         /* Pointer to mother structure   */
} ;


int main()
{
	int indivV = 0;
	int fatherV =0;
	int motherV = 0;

	std::ifstream myfileGenealOriginal;

	myfileGenealOriginal.open("ped.txt");

	// ----------------------------
	std::map<int, STreeGen> IndivMap;
	// ----------------------------

	while(myfileGenealOriginal >> indivV)
	{
		STreeGen& current_indiv = IndivMap[indivV];
		current_indiv.ID = indivV; //assign ID to the new record at ID indivV.

		myfileGenealOriginal >> fatherV >> motherV;

		current_indiv.father = ( fatherV ? &IndivMap[fatherV] : NULL );
		current_indiv.mother = ( motherV ? &IndivMap[motherV] : NULL );
	};

	std::cout << "PRINTING:" << std::endl;

	std::map<int, STreeGen>::const_iterator it;
	for (it = IndivMap.begin(); it != IndivMap.end(); ++it)
		std::cout << it->first << '\t' 
                          << (it->second.father ? it->second.father->ID : 0) << " " 
                          << (it->second.mother ? it->second.mother->ID : 0) << std::endl;

   return 0;
}

I tested it with the input file:

5 0 0
3 6 7
6 0 0
2 4 5
7 0 0
1 2 3
8 0 0
4 0 8

And it printed out:

PRINTING:
1       2 3
2       4 5
3       6 7
4       0 8
5       0 0
6       0 0
7       0 0
8       0 0

As expected. I don't see any problems..

[sadsdw]

Mike,

Try this one as "ped.txt" please:

1 0 0
2 0 0
3 14 20
14 999 6
20 10 1000
30 999 7

[sadsdw]

And it printed out:

1 0 0
2 0 0
3 14 20
6 0 0
7 0 0
10 0 0
14 0 0
20 0 0
30 0 0
999 0 0
1000 0 0

[sadsdw]

Is the problem related to the numbers who were not consecutive? I don't have numbers that filled out a completed sequence. Because that I was planning use a tree. Is this possible with map?

[mike_2000_17]

Oh ok, you didn't mention that you expect some people to be mother or father and not be also an individual (not all your parents appears as individuals, so the ID for them never gets assigned). That's the problem. A simple fix is this:

while(myfileGenealOriginal >> indivV)
  {
    STreeGen& current_indiv = IndivMap[indivV];
    current_indiv.ID = indivV; //assign ID to the new record at ID indivV.

    myfileGenealOriginal >> fatherV >> motherV;

    if(fatherV) {
      current_indiv.father = &IndivMap[fatherV];
      current_indiv.father->ID = fatherV;
    } else
      current_indiv.father = NULL;

    if(motherV) {
      current_indiv.mother = &IndivMap[motherV];
      current_indiv.mother->ID = motherV;
    } else
      current_indiv.mother = NULL;
  };

I was assuming that all parents would eventually appear as an individual somewhere (like in the input file I used).

[sadsdw]

Perfect Mike!

I'm so sorry about the incompletely information.

Thanks a lot! You really help me!

I'm going mark this thread as solved but I will enjoy your skill one more time. Now I need to re-code all animals without spot between individuals and make sure that all individuals have code lower than their parents. Do you think that this is possible using map?

Thanks a lot for your attention and offered time