c# - 在 x 轴的 2D 点中定位基因图的非递归方法。后代如下

Question

我目前的任务是为一个由 sibling 、 parent 、阿姨和叔叔以及祖 parent 和曾祖 parent 组成的家庭制作基因图，仅供血缘亲属使用。我当前的算法正在使用递归。但我想知道如何以非递归方式进行操作以提高效率。它是用 c# 编程的，使用图形在位图上绘制。

当前算法计算x位置，y位置是通过获取世代号。

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;
    }
}

Answer 1

For converting recursive algorithms to iterative ones Pavel Shved建议我这个链接。