Verknüpfungen feststellen

Konzeptionelles, Technisches, Termine, Fragen zum Hersteller usw.

Moderator: Moderatoren

Antworten
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Verknüpfungen feststellen

Beitrag von Jan »

Moin,

ich habe eine konzeptionelle Frage. An der mich meine mangelnden tiefergehenden Mathe-Kenntnisse und die fehlende IT-Ausbildung einholen.

Problem: Wie manche von Euch wissen schreibe ich eine Software für Familienforscher. In der man strukturiert alle seine Vorfahren etc. erfassen kann. Und da ich kein Fan davon bin einfach nur der Sammelleidenschaft zu fröhnen und ein Datengrab zu fabrizieren gibt es auch relativ viele Ausgabemöglichkeiten. Mehr als die meisten anderen Programme in dem Bereich anbieten, und in jedem Fall massiv mehr als alle Online-Anbieter - die diese Thematik erheblich vernachlässigen, auch die ganz großen, die man inzwischen aus der Werbung kennt.

Ich habe nun vor, eine neue Auswertung zu schreiben. Man wählt zwei Personen aus, und das Programm gibt die Verwandschaftsbeziehung(en) aus. Und da stolpere ich gerade drüber.

Es gibt als Verknüpfungspunkte die Verbindung zum (Ehe-)Partner, und zu den Eltern (damit umgekehrt natürlich auch zu den Kindern). Wenn ich jetzt feststellen möchte, wie zwei Personen miteinander verbunden sind, muß ich theoretisch von einer Person ausgehend alle Verbindungen dieser Person überprüfen. Dann alle Verbindungen der mit ihr verbundenen Personen. Dann alle Verbindungen der Verbindungen dieser Person. Und so weiter. Bis ich irgendwann bei der zweiten Person angekommen bin.

Das halte ich für etwas sinnbefreit. Kostet enorm viel Rechenzeit, und vermutlich wird auch recht viel Zeit dabei ins Land streichen. Im einfachsten Fall haben ja beide den gleichen Vorfahren oder den gleichen Nachfahren - was aber auch schon aufwändig auszuwerten ist. Im komplizierteren Fall ist die zweite Person aber der Neffe des der angeheiratete Enkels der zweiten Ehefrau meines Opas.

Gibt es für solch ein Problem eine mathematische oder organisatorische Lösung? Ich bin da offen für fast alle Vorschläge.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
nightcrawler
1000 working lines a day
1000 working lines a day
Beiträge: 650
Registriert: Di, 24. Apr 2012 16:33
Wohnort: 72184 Weitingen
Hat sich bedankt: 3 Mal
Danksagung erhalten: 96 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von nightcrawler »

schau mal hier: https://de.wikipedia.org/wiki/Pathfinding
edit: und davon ausgehend "kürzester Pfad" und https://de.wikipedia.org/wiki/A*-Algorithmus
--
Joachim
Joachim Dürr Softwareengineering
https://www.jd-engineering.de
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Hallo Joachim,

Danke für die Links. Das sind schon mal Ansatzpunkte für mich. Wobei das aber letztendlich anscheinend nichts daran ändert, das ich alles durchprobieren muß. Es kommt nur darauf an wie zielgerichtet und effizient ich das mache.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
Tom
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 9345
Registriert: Do, 22. Sep 2005 23:11
Wohnort: Berlin
Hat sich bedankt: 100 Mal
Danksagung erhalten: 359 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Tom »

Brute-Force-Algorithmen (ich suche einfach alles ab, bis ich etwas finde oder alles abgesucht habe) leiden extrem unter dem exponentiellen Wachstum der benötigten Rechenzeit (also der exponentiellen Regression ihrer Performance). Es ist zwar ein schönes Beispiel für etwa einen recht simplen rekursiven Algorithmus, so vorzugehen (ich bin mit Dir verwandt, wenn einer meiner Nachbarn mit Dir verwandt ist, also untersuche ich ihn - er ist mit Dir verwandt, wenn einer seiner Nachbarn mit Dir verwandt ist, undsoweiter, bis ich entweder alle untersucht oder eine Verbindung gefunden habe), aber den dürfte man schon mit einer Stammbaumtiefe von drei, vier Generationen in die Knie zwingen. Du wirst Dich mit Dijkstra auseinandersetzen müssen. Andererseits sind heuristikbasierte Wege-Finde-Algorithmen darin schwach, definitiv den optimalen Weg, in Deinem Fall also die direkteste Verwandtschaft zu finden. Man kann ja, was weiß ich, Urururcousin sein, und zugleich Schwiegerurenkel oder so. Schwierig. Jim? :wink:
Herzlich,
Tom
Benutzeravatar
Tom
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 9345
Registriert: Do, 22. Sep 2005 23:11
Wohnort: Berlin
Hat sich bedankt: 100 Mal
Danksagung erhalten: 359 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Tom »

Dijkstra ist hier - mit Pseudo-Code - recht gut erklärt: http://www.gm.fh-koeln.de/~hk/lehre/ala ... iebelt.pdf
Herzlich,
Tom
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Hallo Tom,

genau das war mein Problem: Alles durchtesten steigert den Aufwand exponentiell. Genau das wollte ich nach Möglichkeit vermeiden.

Danke für das Papier, seh ich mal durch.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
Marcus Herz
1000 working lines a day
1000 working lines a day
Beiträge: 851
Registriert: Mo, 16. Jan 2006 8:13
Wohnort: Allgäu
Hat sich bedankt: 39 Mal
Danksagung erhalten: 192 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Marcus Herz »

Hallo Jan
Ich hab auch über dein Problem nachgedacht. Vielleicht ist es einfacher:
- du musst ja nicht den Weg finden, sondern nur feststellen, ob es einen gibt.
Ich vermute, du hast eine eindeutige ID einer Person.
- du musst jetzt für jede der 2 Personen alle IDs aller Vorfahren x Generationen zurück sammeln,
hoffentlich hast du SQL, dann kannst du das mit einem union:
// hier mal pseudo Code
select Id from .. where .... // eltern
union all
select Id from .. where kind in (select Id from .. where ....).... // eltern der eltern
union all
select Id from .. where kind in (select Id from .. where kind in (select Id from .. where .....)). // eltern der eltern der eltern
usw.


Für die andere Person machst du das gleiche. Dann musst du nur schauen, ob IDs in beiden Menge identisch sind. Dann hast du die IDs der Gemeinsamkeit, die kannst du ja dann wieder zuordnen

- Sorry, ganz so einfach doch nicht, man muss ja noch die Cousins usw. mit ins union einbeziehen. Aber es wäre ein Lösungsansatz
Gruß Marcus

Erkenne, was du findest, dann weißt du, wonach du gesucht hast
Benutzeravatar
AUGE_OHR
Marvin
Marvin
Beiträge: 12903
Registriert: Do, 16. Mär 2006 7:55
Wohnort: Hamburg
Hat sich bedankt: 19 Mal
Danksagung erhalten: 44 Mal

Re: Verknüpfungen feststellen

Beitrag von AUGE_OHR »

hi,

ist es nicht ein "TREE" Problem :idea:

die Person ist der "Node" und von da kannst du durch den "TREE" gehen um die "Verwandtschaft" festzustellen, oder :?:
gruss by OHR
Jimmy
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Marcus,

nein, kein SQL. FOXCDX.

Und Dein Vorschlag läuft ja letztendlich wieder auf das hinaus was ich vermeiden möchte, oder was Tom so nett Brute Force nennt. Alles zusammenstellenw as jede der beiden Personen hat, und dann abgleichen.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Jimmy,

dafür müsste ich die aber auch erst einmal in den Tree überführen. Damit wäre nach meinem Verständnis nichts gwonnen. Auch dann trage ich ja alles zusammen, was es zu dieser Person gibt. Abgesehen davon wäre in Tree auch zu unflexibel.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
AUGE_OHR
Marvin
Marvin
Beiträge: 12903
Registriert: Do, 16. Mär 2006 7:55
Wohnort: Hamburg
Hat sich bedankt: 19 Mal
Danksagung erhalten: 44 Mal

Re: Verknüpfungen feststellen

Beitrag von AUGE_OHR »

Jan hat geschrieben: Sa, 13. Mär 2021 21:18 dafür müsste ich die aber auch erst einmal in den Tree überführen.
na dann solltest du mal dein Konzept überdenken wie man einen "Familien-BAUM" strukturiert.
gruss by OHR
Jimmy
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Jimmy,

fühl Dich eingeladen Vorschläge zu machen. Ich bin durchaus offen dafür.

Aber wie gesagt, ein Tree scheint mir so oder so nicht die richtige Lösung zu sein, da das nur in eine Richtung geht. Familien aber in zwei gehen (Vorfahren, Nachfahren), und auch waagerecht laufen können durch Partner und deren Angehörigen. Aber auch da lasse ich mich gerne eines Besseren belehren.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
Marcus Herz
1000 working lines a day
1000 working lines a day
Beiträge: 851
Registriert: Mo, 16. Jan 2006 8:13
Wohnort: Allgäu
Hat sich bedankt: 39 Mal
Danksagung erhalten: 192 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Marcus Herz »

Ein Tree wäre ja nur die Kinder zu einer Person. Nur die Referenz. Tabelle mit der Struktur: Parent_ID, Child_ID
DIe kann dann rekursiv beliebig oft aufgerufen werden. Klar werden das viele Verknüpfungen. Aber wozu hätte man sonst ein DBMS?
Gruß Marcus

Erkenne, was du findest, dann weißt du, wonach du gesucht hast
Benutzeravatar
AUGE_OHR
Marvin
Marvin
Beiträge: 12903
Registriert: Do, 16. Mär 2006 7:55
Wohnort: Hamburg
Hat sich bedankt: 19 Mal
Danksagung erhalten: 44 Mal

Re: Verknüpfungen feststellen

Beitrag von AUGE_OHR »

hi,

wie Marcus sagte gibt es die Parent / Child Struktur in einem TREE

mit :getChildItems() oder :getParentItem() kannst vor-/zurück in einer Generation navigieren und mit :setImage() kann man ein Image zuordnen.

---

so viel ich weiss gibt es in der v2.x jetzt "virtual Screen"
damit "müsste" man einen "horizontalen TREE" machen können ... mit Ownerdraw

p.s. DXE_TREE kann Ownerdraw aber ist mit Ot4xb geschrieben ...
gruss by OHR
Jimmy
Benutzeravatar
brandelh
Foren-Moderator
Foren-Moderator
Beiträge: 15688
Registriert: Mo, 23. Jan 2006 20:54
Wohnort: Germersheim
Hat sich bedankt: 65 Mal
Danksagung erhalten: 33 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von brandelh »

Jan hat geschrieben: Sa, 13. Mär 2021 21:18 Jimmy,

dafür müsste ich die aber auch erst einmal in den Tree überführen. Damit wäre nach meinem Verständnis nichts gwonnen. Auch dann trage ich ja alles zusammen, was es zu dieser Person gibt. Abgesehen davon wäre in Tree auch zu unflexibel.

Jan
du musst doch heute schon Infos haben über alle Eltern ... sagen wir 10 Generationen oder 20 zurück, das sollte überschaubar sein.
Jeder Vorgänger braucht eine eindeutige ID, bei jedem Schritt wird die ID bei jedem gemerkt.
Man könnte in jedem Schritt prüfen ob die neue ID bei den anderen vorhanden ist oder eben nicht oder am Ende ob es Übereinstimmungen gibt.

egal ob Tante, Enkel, oder weit entfernter Cousin, alle haben in überschaubarer Reihenfolge einen gemeinsamen Vorfahren oder eben nicht.
Ich habe die väterliche Linie bis etwa 1700 (um 1700 eingewandert aus Südtirol) ... pro Jahrhundert 4 oder 5.
Aber ohne Infos über Personen bzw. eine eindeutig ID wird es klar nicht gehen, ich dachte du hättest die Infos irgendwo auf der Platte ?
Gruß
Hubert
UliTs
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 2828
Registriert: Fr, 10. Feb 2006 9:51
Wohnort: Aachen
Hat sich bedankt: 259 Mal
Danksagung erhalten: 12 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von UliTs »

Ich bin gerade über diesen Faden gestolpert. Solche Algorithmen machen mir Spaß. :D
Hast Du eine Lösung gefunden, Jan?
-------
Mitglied XuG Cologne
Mitglied XuG Osnabrück
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von Jan »

Hallo Uli,

ich hatte mich damals in die Tipps rein vertieft, aber für mich keine Lösung gefunden.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
UliTs
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 2828
Registriert: Fr, 10. Feb 2006 9:51
Wohnort: Aachen
Hat sich bedankt: 259 Mal
Danksagung erhalten: 12 Mal
Kontaktdaten:

Re: Verknüpfungen feststellen

Beitrag von UliTs »

Danke für die Info. Meines Erachtens hast Du die Aufgabe sehr klar kommuniziert:
Ich habe nun vor, eine neue Auswertung zu schreiben. Man wählt zwei Personen aus, und das Programm gibt die Verwandschaftsbeziehung(en) aus. Und da stolpere ich gerade drüber.
Ich kenne mich in Verwandtschaftsbeziehungen nicht besonders gut aus. Aber ich meine, dass man derartige Beziehungen in verschiedene Grade (z.B. Geschwister = Beziehung 1.Grades (?) ) aufteilen kann. Ist das richtig?

Als Idee hätte ich den Lösungsansatz, dass man zunächst für die beiden Personen bestimmt, zu wem sie alles eine Verwandschaft 1.Grades haben. Tauchen die Personen in der jeweils anderen Menge auf, hat man schon einmal die Beziehung(en?) 1.Grades bestimmt.

Rekursiv könnte man anschließend genauso nach den Verwandtschaften 2.Grades suchen, etc.

Erscheint Dir diese Vorgehensweise halbwegs sinnvoll, Jan?
-------
Mitglied XuG Cologne
Mitglied XuG Osnabrück
Benutzeravatar
AUGE_OHR
Marvin
Marvin
Beiträge: 12903
Registriert: Do, 16. Mär 2006 7:55
Wohnort: Hamburg
Hat sich bedankt: 19 Mal
Danksagung erhalten: 44 Mal

Re: Verknüpfungen feststellen

Beitrag von AUGE_OHR »

hi Uli,

Marcus und ich haben Jan ein XbpTreeView() vorgeschlagen
ein XbpTreeView() hat die Method(en) o:getChildItems() und o:getParentItem() für genau "die Verknüpfungen"
aber Jan meint es gäbe ihm nicht genügend "Möglichkeiten".

man könnte z.b. die XbpTreeView() "Engine" als "Skipper" mit einem "Browse" verknüpfen ...
gruss by OHR
Jimmy
Antworten