Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

pedigree graph

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.

share|improve this question

1 Answer 1

Finding $y$ coordinates is very easy. First tag all sinks (nodes with no children) as depth $0$. Then tag all their ancestors as depth $1$. And so on. This can be implemented as a recursive procedure or using a stack.

Finding $x$ coordinates is more tricky (probably NP-complete under a suitable definition). In particular, edges are going to cross. I suggest using some iterative approach. First, find the largest level, and assign it some $x$ values. Then assign $x$ values for the rest in the same range. Now figure out some scoring function that takes into account edge length and crossings. Use local search or simulated annealing to find a god local optimum with respect to this scoring function.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.