I'm trying to process pedigree data into a graphical representation. My issue is with positioning each node. I need (I think) to figure out the maximum number of generations for the dataset to determine the number of y-axis divisions. And then I need to assign each node to the proper division. Determining the x-axis arrangement is something I can't wrap my head around yet.
My data is in an adjacency list that looks something like this:
cross fishgroup dam damcount sire sirecount crossdate 1 23 42 57 2009-07-16 2 26 25 10 25 10 2010-01-06 3 27 43 9 43 9 2010-01-07 4 28 44 7 44 7 2010-01-08 5 30 25 10 25 10 2010-02-11 6 31 45 25 2010-02-23 7 32 45 45 2010-03-19 8 33 31 8 32 8 2010-07-14 9 34 28 10 59 10 2010-07-15 10 35 27 4 28 5 2010-07-22 11 36 28 6 28 8 2010-07-28 12 39 38 6 34 6 2011-02-08 13 41 27 2 24 5 2011-04-13
Each node is a group of fish. A dam is another group of fish, as is a sire. A fishgroup can have 1 dam and 1 sire, but the dam and sire may have the same id. This means there are 2 types of edges: dam edges and sire edges. The damcount and sirecount is the number of fish that participated in the cross. These counts may be considered edge weights and are optional.
This is the kind of graph the above data should produce:
What is the most efficient method of determining x,y co-ordinates for each node such that:
- nodes do not overlap
- ancestor nodes are above child nodes
- edge length is minimized
- edges preferably do not cross each other
If it's truly better, I can store my data as a nested set. But I still have the same difficulty figuring out the logic of positioning nodes.
Sorry if this is an obvious question. I'm not much of a math person.