Вычислить родство по генеалогическим данным

Сначала вам нужно вычислитьнаименьшего общего предка обоихA иB . Назовем этот низший общий предок C .

Затем вычислите расстояние в шагах от C до A (CA) и C до B (CB). Эти значения должны быть проиндексированы в другую таблицу, которая определяет отношение, основанное на этих двух значениях. Например:

CA      CB      Relation
1       2       uncle
2       1       nephew
2       2       cousin
0       1       father
0       2       grandfather

Вы можете сохранить основные соотношения в этой таблице и добавить "отлично -" для дополнительные расстояния на некоторых отношениях, таких как дедушка, например.: (0, 3) = прадедушка.

Надеюсь, это укажет вам правильное направление. Желаю удачи!

обновление: (я не могу комментировать ниже вашего кода, так как у меня еще нет репутации.)

Ваша функция aggrandize_relationships немного не в себе, Я думаю. Вы можете упростить его, добавив префикс "grand", если смещение равно 1 или больше, а затем префикс" great - " (смещение - 1) раз. Ваша версия может быть включите приставку "пра-пра - пра-пра" для очень дальних родственников.(Не уверен, что у меня есть правильный параметр в этом объяснении, но надеюсь, вы поймете суть. Кроме того, не знаю, идет ли ваше семейное древо так далеко назад, но точка зрения остается в силе.)

ОБНОВЛЕНИЕ ТОЖЕ: К сожалению, вышеизложенное неверно. Я неправильно истолковал случай по умолчанию и подумал, что он рекурсивно вызвал функцию снова. В свою защиту скажу, что я не был знаком с обозначением "2-й прадед"., и всегда пользовался "прапрадедушкой" сам. Код вперед!!

Это может помочь вычислителю древовидных отношений-объекту, который принимает XML-представление дерева и вычисляет отношения любых двух членов внутри него. В этой статье описывается, как вычисляются отношения и что означают такие термины, как троюродный брат или двоюродный брат после удаления. Этот код включает в себя объект для вычисления отношений, написанный на JavaScript, а также веб-интерфейс для визуализации и взаимодействия с деревом. Пример проекта настроен как классический страница ASP.

Http://www.codeproject.com/Articles/30315/Tree-Relationship-Calculator

Я решил эту проблему, используя концепцию списка смежности в java. Можно иметь узел для каждого человека и иметь его дочерние отношения, связанные с ним на самом узле. Ниже приведен код, чтобы найти только братьев и сестер. Однако, вы можете увеличить его согласно вашему требованию. Я написал этот код только для демонстрации.

public class Person {
    String name;
    String gender;
    int age;
    int salary;
    String fatherName;
    String motherName;

    public Person(String name, String gender, int age, int salary, String fatherName,
            String motherName) {
        super();
        this.name = name;
        this.gender = gender;
        this.age = age;
        this.salary = salary;
        this.fatherName = fatherName;
        this.motherName = motherName;
    }

}

Ниже приведен основной код для добавления семейных людей и поиска отношений между собой.

import java.util.LinkedList;

public class PeopleAndRelationAdjacencyList {
    private static String MALE = "male";
    private static String FEMALE = "female";

public static void main(String[] args) {
    int size = 25;
    LinkedList<Person> adjListArray[] = new LinkedList[size];
    for (int i = 0; i < size; i++) {
        adjListArray[i] = new LinkedList<>();
    }

    addPerson( adjListArray, "GGM1", MALE, null, null );
    addPerson( adjListArray, "GGF1", FEMALE, null, null );

    addPerson( adjListArray, "GM1", MALE, "GGM1", "GGF1" );
    addPerson( adjListArray, "GM2", MALE, "GGM1", "GGF1" );

    addPerson( adjListArray, "GM1W", FEMALE, null, null );
    addPerson( adjListArray, "GM2W", FEMALE, null, null );

    addPerson( adjListArray, "PM1", MALE, "GM1", "GM1W" );
    addPerson( adjListArray, "PM2", MALE, "GM1", "GM1W" );
    addPerson( adjListArray, "PM3", MALE, "GM2", "GM2W" );

    addPerson( adjListArray, "PM1W", FEMALE, null, null );
    addPerson( adjListArray, "PM2W", FEMALE, null, null );
    addPerson( adjListArray, "PM3W", FEMALE, null, null );

    addPerson( adjListArray, "S1", MALE, "PM1", "PM1W" );
    addPerson( adjListArray, "S2", MALE, "PM2", "PM2W" );
    addPerson( adjListArray, "S3", MALE, "PM3", "PM3W" );
    addPerson( adjListArray, "S4", MALE, "PM3", "PM3W" );

    printGraph(adjListArray);
    System.out.println("Done !");


    getRelationBetweenPeopleForGivenNames(adjListArray, "S3", "S4");
    getRelationBetweenPeopleForGivenNames(adjListArray, "S1", "S2");

}


private static void getRelationBetweenPeopleForGivenNames(LinkedList<Person>[] adjListArray, String name1, String name2) {

    if ( adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1)].peekFirst().fatherName
            .equalsIgnoreCase(
                    adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2)].peekFirst().fatherName) ) {
        System.out.println("SIBLIGS");
        return;
    }

    String name1FatherName = adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1)].peekFirst().fatherName;
    String name2FatherName = adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2)].peekFirst().fatherName;

    if ( adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1FatherName)].peekFirst().fatherName
            .equalsIgnoreCase(
                    adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2FatherName)].peekFirst().fatherName) ) {
        System.out.println("COUSINS");
    }
}



private static void addPerson(LinkedList<Person>[] adjListArray, String name, String gender, String fatherName, String motherName) {
    Person person = new Person(name, gender, 0, 0, fatherName, motherName);
    int indexToPutperson = getEmptyIndexInAdjListToInserterson(adjListArray);
    adjListArray[indexToPutperson].addLast(person);
    if( fatherName!=null ){
        int indexOffatherName = getIndexOfGivenNameInHeadPositionOfList( adjListArray, fatherName);
        adjListArray[indexOffatherName].addLast(person);
    }
    if( motherName!=null ){
        int indexOfMotherName = getIndexOfGivenNameInHeadPositionOfList( adjListArray, motherName);
        adjListArray[indexOfMotherName].addLast(person);
    }
}

private static int getIndexOfGivenNameInHeadPositionOfList( LinkedList<Person>[] adjListArray, String nameToBeSearched ) {
    for (int i = 0; i < adjListArray.length; i++) {
        if( adjListArray[i] != null ){
            if(adjListArray[i].peekFirst() != null){
                if(adjListArray[i].peekFirst().name.equalsIgnoreCase(nameToBeSearched)){
                    return i;
                }
            }
        }
    }
    // handle if father name is not found
    return 0;
}


private static void printGraph(LinkedList<Person>[] adjListArray) {
    for (int v = 0; v < 15; v++) {
        System.out.print("head");

        LinkedList<Person> innerLinkedList = adjListArray[v];
        for (int i = 0; i < innerLinkedList.size(); i++) {
            Person person = innerLinkedList.get(i);
            System.out.print(" -> " + person.name);
        }

        System.out.println("\n");
    }
}

private static int getEmptyIndexInAdjListToInserterson( LinkedList<Person>[] adjListArray) {
    for (int i = 0; i < adjListArray.length; i++) {
        if(adjListArray[i].isEmpty()){
            return i;
        }
    }
    throw new IndexOutOfBoundsException("List of relation is full.");
}

}

Это может помочь вам, это много теории и реализации SQL-запросов для создания и запроса древовидных структур

Http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

В частности, рассмотрим модельсписка смежности , в которой в качестве примера используется семейное дерево.

Как бы странно это ни звучало, пролог - это то, что вы ищете. Дана следующая специальная программа (http://www.pastey.net/117134 Лучшая окраска)

female(alice).
female(eve).
female(kate).

male(bob).
male(carlos).
male(dave).

% mother(_mother, _child).
mother(alice, bob).
mother(kate, alice).

% father(_father, _child)
father(carlos, bob).

child(C, P) :- father(P, C).
child(C, P) :- mother(P, C).

parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).

sister(alice, eve).
sister(eve, alice).
sister(alice, dave).

brother(dave, alice).

% brother(sibling, sibling)
sibling(X, Y) :- brother(X, Y).
sibling(X, Y) :- sister(X, Y).


uncle(U, C) :- sibling(U, PARENT),
    child(C, PARENT),
    male(U).


relationship(U, C, uncle) :- uncle(U, C).
relationship(P, C, parent) :- parent(P, C).
relationship(B, S, brother) :- brother(B, S).
relationship(G, C, grandparent) :- parent(P, C), parent(G, P).

Вы можете спросить переводчика пролога что-то вроде этого:

relationship(P1, P2, R).

С ответами:

P1 = dave, P2 = bob, R = uncle ;
P1 = alice, P2 = bob, R = parent ;
P1 = kate, P2 = alice, R = parent ;
P1 = carlos, P2 = bob, R = parent ;
P1 = dave, P2 = alice, R = brother ;
P1 = kate, P2 = bob, R = grandparent ;
false.

Это мощный инструмент, если вы знаете, как и когда им пользоваться. Это похоже на место для Пролога. Я знаю, что это не очень популярно, или легко встроить, но впечатляющая особенность wolphram Альфа, показанная в одном из комментариев, может быть закодирована только с помощью конструкций, использованных выше, и это пролог 101.