I currently was tasked to make a genogram for a family consisting of siblings, parents with aunts and uncles with grandparents and greatgrandparents for only blood relatives. My current algorithm is using recursion. but I am wondering how to do it in non recursive way to make it more efficient. it is programmed in c# using graphics to draw on a bitmap.
Current algorithm for calculating x position,
the y position is by getting
the generation number.
public void StartCalculatePosition()
{
// Search
the start node (The only node with targetFlg set to true)
Person start = null;
foreach (Person p in PersonDic.Values)
{
if (start == null) start = p;
if (p.Targetflg)
{
start = p;
break;
}
}
CalcPositionRecurse(start);
// Normalize
the position (shift all values to positive value)
// Get
the minimum value (must be negative)
// Then offset
the position of all marriage and
person with that to make it start from zero
float minPosition = float.MaxValue;
foreach (Person p in PersonDic.Values)
{
if (minPosition > p.Position)
{
minPosition = p.Position;
}
}
if (minPosition < 0)
{
foreach (Person p in PersonDic.Values)
{
p.Position -= minPosition;
}
foreach (Marriage m in MarriageList)
{
m.ParentsPosition -= minPosition;
m.ChildrenPosition -= minPosition;
}
}
}
/// <summary>
/// Calculate position of genogram using recursion
/// </summary>
/// <param name="psn"></param>
private void CalcPositionRecurse(Person psn)
{
// End
the recursion
if (psn.BirthMarriage == null || psn.BirthMarriage.Parents.Count == 0)
{
psn.Position = 0.0f;
if (psn.BirthMarriage != null)
{
psn.BirthMarriage.ParentsPosition = 0.0f;
psn.BirthMarriage.ChildrenPosition = 0.0f;
}
CalculateSiblingPosition(psn);
return;
}
// Left recurse
if (psn.Father != null)
{
CalcPositionRecurse(psn.Father);
}
// Right recurse
if (psn.Mother != null)
{
CalcPositionRecurse(psn.Mother);
}
// Merge Position
if (psn.Father != null && psn.Mother != null)
{
AdjustConflict(psn.Father, psn.Mother);
// Position
person in center of parent
psn.Position = (psn.Father.Position + psn.Mother.Position) / 2;
psn.BirthMarriage.ParentsPosition = psn.Position;
psn.BirthMarriage.ChildrenPosition = psn.Position;
}
else
{
// Single mom or single dad
if (psn.Father != null)
{
psn.Position = psn.Father.Position;
psn.BirthMarriage.ParentsPosition = psn.Position;
psn.BirthMarriage.ChildrenPosition = psn.Position;
}
else if (psn.Mother != null)
{
psn.Position = psn.Mother.Position;
psn.BirthMarriage.ParentsPosition = psn.Position;
psn.BirthMarriage.ChildrenPosition = psn.Position;
}
else
{
// Should not happen, checking in start of function
}
}
// Arrange
the siblings base on my position (left younger, right older)
CalculateSiblingPosition(psn);
}
private float GetRightBoundaryAncestor(Person psn)
{
float rPos = psn.Position;
// Get
the rightmost position among siblings
foreach (Person sibling in psn.Siblings)
{
if (sibling.Position > rPos)
{
rPos = sibling.Position;
}
}
if (psn.Father != null)
{
float rFatherPos = GetRightBoundaryAncestor(psn.Father);
if (rFatherPos > rPos)
{
rPos = rFatherPos;
}
}
if (psn.Mother != null) {
float rMotherPos = GetRightBoundaryAncestor(psn.Mother);
if (rMotherPos > rPos)
{
rPos = rMotherPos;
}
}
return rPos;
}
private float GetLeftBoundaryAncestor(Person psn)
{
float rPos = psn.Position;
// Get
the rightmost position among siblings
foreach (Person sibling in psn.Siblings)
{
if (sibling.Position < rPos)
{
rPos = sibling.Position;
}
}
if (psn.Father != null)
{
float rFatherPos = GetLeftBoundaryAncestor(psn.Father);
if (rFatherPos < rPos)
{
rPos = rFatherPos;
}
}
if (psn.Mother != null)
{
float rMotherPos = GetLeftBoundaryAncestor(psn.Mother);
if (rMotherPos < rPos)
{
rPos = rMotherPos;
}
}
return rPos;
}
/// <summary>
/// Check if two parent group has conflict and compensate on
the conflict
/// </summary>
/// <param name="leftGroup"></param>
/// <param name="rightGroup"></param>
public void AdjustConflict(Person leftGroup,
Person rightGroup)
{
float leftMax = GetRightBoundaryAncestor(leftGroup);
leftMax += 0.5f;
float rightMin = GetLeftBoundaryAncestor(rightGroup);
rightMin -= 0.5f;
float diff = leftMax - rightMin;
if (diff > 0.0f)
{
float moveHalf = Math.Abs(diff) / 2;
RecurseMoveAncestor(leftGroup, 0 - moveHalf);
RecurseMoveAncestor(rightGroup, moveHalf);
}
}
/// <summary>
/// Recursively move a
person and all his/her ancestor
/// </summary>
/// <param name="psn"></param>
/// <param name="moveUnit"></param>
public void RecurseMoveAncestor(Person psn, float moveUnit)
{
psn.Position += moveUnit;
foreach (Person siblings in psn.Siblings)
{
if (siblings.Id != psn.Id)
{
siblings.Position += moveUnit;
}
}
if (psn.BirthMarriage != null)
{
psn.BirthMarriage.ChildrenPosition += moveUnit;
psn.BirthMarriage.ParentsPosition += moveUnit;
}
if (psn.Father != null)
{
RecurseMoveAncestor(psn.Father, moveUnit);
}
if (psn.Mother != null)
{
RecurseMoveAncestor(psn.Mother, moveUnit);
}
}
/// <summary>
/// Calculate
the position of
the siblings
/// </summary>
/// <param name="psn"></param>
/// <param name="anchor"></param>
public void CalculateSiblingPosition(Person psn)
{
if (psn.Siblings.Count == 0)
{
return;
}
List<Person> sibling = psn.Siblings;
int argidx;
for (argidx = 0; argidx < sibling.Count; argidx++)
{
if (sibling[argidx].Id == psn.Id)
{
break;
}
}
// Compute position for each brother that is younger that
person
int idx;
for (idx = argidx - 1; idx >= 0; idx--)
{
sibling[idx].Position = sibling[idx + 1].Position - 1;
}
for (idx = argidx + 1; idx < sibling.Count; idx++)
{
sibling[idx].Position = sibling[idx - 1].Position + 1;
}
}
