C#/Linq/SQLite Recursive query to build a family tree

rip55jcp
rip55jcp used Ask the Experts™
on
I have a table of animals.  The important fields are:

animal_id
mother_animal_id
father_animal_id

mother_animal_id and father_animal_id both relate back to animal.animal_id.

I need to build a result set of an animal and it's ancestors.  Each set of immediate ancestors will have a higher level number.  I would stop at a maximum of 6 levels above the base animal.

For example, this is what a small dataset might look like:

animal_id, mother_animal_id, father_animal_id, level
104, 98, 97, 0
98, 101, 102, 1
97, 4, 10, 1
101, 60, 44, 2
102, 11, 6, 2
4, 57, 22, 2
10, 66, 21, 2

I'm using SQLite, so I don't have the ability to use a stored procedure.  Can I do this with LINQ?  If so, how?

TIA
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
View Solution Only
Gary DavisDir Internet Svcs

Commented:
This solution uses recursion and Linq. I developed with LinqPad which has that Dump() function so replace that with your own output. Also, you can sort the output by Level if needed.

Gary Davis

const int MaxLevel = 6;	// Maximum depth
List<Animal> animals = new List<Animal>();		// Return
List<Animal> animalData = new List<Animal> {	// Database
		new Animal (1, 98, 97, 0),
		new Animal (2, 98, 97, 0),
		new Animal (3, 98, 97, 0),
		new Animal (104, 98, 97, 0),
		new Animal (98, 101, 102, 1),
		new Animal (97, 4, 10, 1),
		new Animal (101, 60, 44, 2),
		new Animal (102, 11, 6, 2),
		new Animal (4, 57, 22, 2),
		new Animal (10, 66, 21, 2)};

void Main()
{
	GetAnimal(104);	
	animals.Dump();
}

// Add one animal record to the list of ancestors. Recursively called.
void GetAnimal(int id)
{
	var animal = animalData.SingleOrDefault(s => s.AnimalId == id);
	if (animal == null) return;	// Stop recursion (not found)
	animals.Add(animal);
	if (animal.Level == MaxLevel) return;	// Stop recursion (max level)
	GetAnimal(animal.MotherAnimalId);
	GetAnimal(animal.FatherAnimalId);	
}

public class Animal
{
	public Animal(int animalId, int motherAnimalId, int fatherAnimalId, int level) // Constructor
	{
		AnimalId = animalId;
		MotherAnimalId = motherAnimalId;
		FatherAnimalId = fatherAnimalId;
		Level = level;
	}
	
	public int AnimalId {get;set;}
	public int MotherAnimalId {get;set;}
	public int FatherAnimalId {get;set;}
	public int Level {get;set;}
}

Open in new window

AnimalsResult.png
rip55jcp

Author

Commented:
I'm accepting the comment made by EugeneZ as the correct answer since the links led me to an acceptable solution.  Gardavis, yours was close, but the level value is not part of the original table.  It has to be incremented for each level of ancestors found.  

Thanks!!!

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial