树形关系计算器

• 下载源代码 - 9.47 KB

引言

家谱关系计算器是一个对象，它接受 XML 格式的家谱表示，并计算其中任意两个成员之间的关系。本文描述了关系是如何计算的，以及“表堂兄弟”或“表叔”（first cousin once removed）等术语的含义。该代码包含一个用于计算关系的 JavaScript 对象，以及一个用于渲染和交互家谱的 Web UI。以 示例项目 设置为一个经典的 ASP 页面。

家谱作为数据结构

家谱（树）是一种非线性数据结构，在计算机科学中有许多应用。非线性结构表示组件之间复杂的链接。具体来说，家谱是一种图，其中每个节点最多有一个父节点和零个或多个子节点。

家谱的最高节点称为根节点，家谱中的每个节点都是一个子家谱的根节点。父节点是直接链接在当前节点上方的节点。描述家谱时使用的术语很多都来自我们用来描述家庭关系的名称。例如，两个具有相同父节点的节点称为兄弟姐妹。我们还使用祖先、后代和子代等术语来描述节点之间的相对位置。供您参考，我包含了一些解释部分概念和术语的链接：家谱、数据结构、递归。

节点的深度是我们将用于计算关系的另一个重要概念。如果您从一个给定节点开始向上移动到其父节点，我们称之为一步。向上移动到父节点的父节点将是两步。如果您继续向上移动到根节点，计算步数，您将获得节点的深度，即从节点到根节点的距离。

衡量关系

虽然祖先和后代等术语对家谱中两个节点之间的相对位置提供了模糊的参考，但家谱学家使用更精确的术语来描述关系，这使他们能够解释两个成员之间的确切相对位置。“三表叔”（third cousin once removed）就是其中一个例子，而这正是我们的程序将要计算的关系类型。

有两种组成部分可以衡量家庭树中两个人之间的关系类型，它们衡量的是每个人在垂直和水平方向上的距离。第一个组成部分描述了两个家庭成员之间的水平距离，其衡量方式是他们最近的共同亲戚有多远。例如，您的表兄弟（first cousin）共享一个祖父母，该祖父母在上面两层。您的表堂兄弟（second cousin）是指您最近的共同祖父母是您的曾祖父母，在上面三层。

要计算表亲的级别，您需要从最近的共同祖父母所在的代数减去一。共同的曾祖父母（3）意味着您是（3-1=2）二代表亲，共同的祖父母意味着您是一代表亲。共同的父节点意味着您是零代表亲，我们称之为兄弟姐妹。下图显示，Cyclops 和 Hemera 是表兄妹，因为他们共享一个共同的祖父母。

第二个组成部分衡量家谱中的垂直距离，它描述了您们之间相差的代数。“表叔”（once removed）是“表堂兄弟一次移除”（first cousin once removed）这个短语的“once removed”部分。例如，您的母亲比您大一代，所以她是“一次移除”。您的祖母比您大两代，所以她是“两次移除”。您是您祖母和母亲的直系后代，不使用“移除”术语；但是，对于更远的亲戚，原则是相同的。您的二表叔两次移除（second cousin twice removed）将与您的祖母在同一代。

下图显示 Hemera 和 Leto 共享 Chaos 作为他们最近的共同祖先。Chaos 距离 Hemera 两代，距离 Leto 四代。我们使用两者中较小的距离来确定表亲的因子，并使用两者之间的差值来计算移除的因子。这告诉我们 Hemera 和 Leto 是二代表亲两次移除（first cousins twice removed）。

• 距离最近共同祖先的距离：Hemera:2, Leto:4
• Hemera(2) – 1 = 1^st 表亲
• Leto(4) – Hemera(2) = 2 次移除

命名关系

使用这两个组成部分，您可以计算出您在家谱中任何成员的关系。我们的大部分直系亲属都有他们关系的特殊名称，但遵循与更远的二代表亲、三代表亲和四代表亲相同的规则。例如，您的一代表亲一次移除（zero cousin once removed）将是您的父母。您的一代表亲零次移除（zero cousin zero times removed）是您的兄弟姐妹。下表显示了命名关系如何对应表亲/移除的约定。

C = 最近共同祖先之间的较小距离

R = 较远亲戚的距离减去较近亲戚的距离

XML 结构

我们的关系计算程序将以一个表示家谱的 XML 文档作为输入，该文档将由一个根 <familytree> 节点表示，其中包含一个 <person> 节点，该节点又包含一个 <children> 节点，该节点可以包含零个或多个 <person> 节点。这是我从 Theoi Greek Mythology 网站 上的信息创建的希腊神话家谱的完整 XML 文件，该网站值得一看。

• 希腊神话家谱（tree.xml）- 15.91 KB

算法

这是我们为计算任意关系将遵循的算法

1. 找到两个成员在家谱中的位置
2. 使用位置找到每个人到其最近共同祖先的距离
3. 使用距离确定表亲（c）和移除（r）因子
4. 使用 c 和 r 变量生成关系的文本名称

递归搜索函数

递归和自相似是计算机科学中的另外两个重要概念，它们在处理家谱时特别有用。为了找到每个成员的位置，我们的程序将调用一个递归搜索函数来遍历家谱的每个节点，并在过程中记录其当前位置。找到匹配项时，将保存该位置。位置存储为一个数组，数组的每个元素代表一代。存储的整数表示该子节点的顺序，从零开始。例如，Hemera 的位置数组将是 {0, 2, 1}，跟踪每个子节点在家谱中的顺序：Chaos(0), Nyx(2), Hemera(1)。

这是我们程序的递归搜索函数。此函数接受一个 XML 节点，检查它是否与我们正在查找的任何 ID 匹配，然后对该节点的每个子节点调用自身。

function testNode(PerNode, depth,idFirst, idLast){
    if (PerNode.getAttribute("id") == null) 
        return false;
    var id = parseInt(PerNode.getAttribute("id"));
    depth++;

    // Look for a match for either person
    if (id==idFirst) this.arFirst = this.arPos.copy();
    if (id==idLast){ this.arLast = this.arPos.copy();}

    // If both people have been found, end recursion
    if (this.arFirst !=null && this.arLast!=null)return true;

    // If no children end recursion
    var ChildrenNodes = PerNode.getElementsByTagName("children");
    if (!ChildrenNodes) return false;
    
    // For each child of the given node, call this same function
    for (var c=0,k=0; c<ChildrenNode.childNodes.length; c++){
        k++;
        this.arPos.length = depth;
        this.arPos[depth] = k;
        var ret = this.TestNode(ChildrenNode.childNodes.item(c), 
        depth, idFirst, idLast)
        if (ret == true) return true;
    }
    return false;
}

步骤 1：开始搜索

getRelById() 函数是启动递归搜索的方法。搜索完成后，我们将有两个数组描述两个成员在家谱中的位置。然后调用 getRelByArray() 函数来根据位置数组计算关系。

function getRelById(idFirst, idLast)
{
    if (isNaN(idFirst) || isNaN(idLast)) 
        throw new Error("Id is not numeric");
    idFirst = parseInt(idFirst);
    idLast = parseInt(idLast);
    if (!this.xmlDoc) return false;

    // Start the search. If both matches are not found return false
    this.arPos[0]=0;
    var RootNode = this.xmlDoc.documentElement.firstChild;
    if (!this.TestNode(RootNode,0,idFirst, idLast)) return false;
    
    // Get the named relationship based on the position arrays
    return this.GetRelByArray(this.arFirst, this.arLast, this.g);
}

步骤 2：将位置转换为到最近祖先的距离

getRelByArray() 函数比较两个数组，并确定每个成员到最近共同祖先的距离。然后将这些数据发送给 getRelByDistance() 以进一步计算关系。

function getRelByArray(arF, arL, g)
{
    // Set the gender flag
    g = (g==0||g==1)? g : 2;
    
    // Get length of the shorter array
    var len = (arF.length<arL.length)? arF.length : arL.length;
    
    // Compare the arrays to find out where they deviate.
    // i records how far down the arrays are the same
    for (var i=0; i<len; i++){if (arF[i] != arL[i]) break;}
    
    // Subtract i from the length of each array. This re-factors
    // the length in relation to the closest common relative
    var a = (arF.length - i);
    var b = (arL.length - i);
    
    // Use a,b (the distance of each to the closest common relative)
    // to generate the relationship label
    return(this.GetRelByDistance(a,b,g));
}

步骤 3：将祖先距离转换为 R 和 C 因子

getRelByDistance() 函数将接收两个成员到其最近共同祖先的距离，并计算关系的移除（r）和表亲（c）因子。然后将其发送到 getRelByRC()，后者生成关系的文本名称。

function getRelByDistance(a,b,g)
{
    a = parseInt(a);
    b = parseInt(b);
    g = (g==0||g==1)? g : 2;
    var c = ((b>=a)?  a: a - (a - b))
    var r = a - b;
    return(this.GetRelByRC(c,r,g));
}

步骤 4：使用 R 和 C 生成文本名称

最后，getRelByRC() 函数将创建关系的文本名称。对于大多数关系，我们只需从 c 因子中减去 1 即可获得类似 c3:r1 等于“二表叔一次移除”的结果。对于命名关系（零代表亲等），我们进行简单的查找以将 c 和 r 变量与预定义名称匹配。性别变量 g 会被传递，以便我们知道何时使用姑姑而不是叔叔，以及母亲而不是父亲。

function getRelByRC(c,r,g)
{
    var strName = "";
    var absR;
    var g = (g==0||g==1)? g : 2;
    var arYou = [["same person","same person","same person"],
        ["brother","sister","sibling"]];
    var arStatic = new Array();

    arStatic[0] = [["son","daughter","child"],
        ["father","mother","parent"]];
    arStatic[1] = [["nephew","neice","nephew/neice"],
        ["uncle","aunt","uncle/aunt"]];

    // c==0 are your direct descendants 
    if (c==0) { 
        absR = Math.abs(r); 
        if (absR==0) strName = arYou[c][g]; 
        if (absR>0) strName = (r<0)? arStatic[c][0][g] : arStatic[c][1][g]; 
        if (absR>1) strName = " grand " + strName; 
        if (absR>2) strName = " great " + strName; 
        if (absR>3) strName = rcFormatPrefix(absR-2) + strName; 
    } 

    // c==1 are zero cousins 
    else if(c==1) { 
        absR = Math.abs(r); 
        if (absR==0) strName = arYou[c][g]; 
        if (absR>0)  strName = (r<0)? arStatic[c][0][g] : arStatic[c][1][g]; 
        if (absR==2) strName = " great "; + strName; 
        else{ 
        if (absR>1) strName = "grand" + strName; 
        if (absR>2) strName = " great " + strName; 
        if (absR>3) strName = rcFormatPrefix(absR-1) + strName; 
        }
    } 

    // c>1 are all other 2nd, 3rd, etc... cousins 
    else{ 
        var cousin = rcFormatPrefix(c-1) + " cousin "; 
        var removed = (Math.abs(r)>0)? Math.abs(r) + " times removed." : ""; 
        strName = cousin + removed; 
    } 

    return strName; 
}

Using the Code

上述函数构成了我们的对象的各种方法。整个对象可以在文件 Rel.txt [4.98 KB] 中找到。要计算关系，我们只需实例化该对象，传入我们 XML 家谱的引用，然后调用 GetRelById() 函数。结果是关系的字符串表示。

var relObj = new RelCalculator(xmlDoc);
var strRel = relObj.GetRelById(100, 143);

我们的代码还包括一个 UI，它使用 XHTML 和 CSS 将 XML 渲染为可视化家谱。该 UI 允许我们可视化家谱并通过拖放界面调用关系计算器。我将不详细介绍此页面如何渲染，但如果您有兴趣，这里是相关文件。您还可以尝试 工作示例。

• 示例
• 项目文件（tree.zip）- 9.47 KB

历史

• 2008 年 10 月 21 日：初始帖子。