Bekanntenverkettungen
afoeder am 7. Februar 2008 16:51
Aus reiner technologischer Neugier hat es mich dazu getrieben, ein wenig nach Umsetzungsalgorithmen für grafische Darstellungen von Personenbeziehnungen zu recherchieren. Diese Umsetzung ist wohl am populärsten bei XING und studiVZ anzutreffen.
Wer’s nicht kennt, eine kurze Erläuterung: Personen definieren, welche Personen sie kennen. Mittels der grafischen Darstellung soll es nun möglich sein, den “Weg” zwischen zwei Personen aufzuzeigen, also über wieviele “Ecken” sich die beiden Personen kennen. Zugrunde liegt die Theorie, dass jede Person mit jeder Person auf der Welt um maximal 6 (glaube ich) Ecken bekannt ist.
Dies soll zunächst nur als Linkliste zum Thema dienen, da mit schlichtweg die informatische und mathematische Grundkenntnis fehlt.
Zunächst bin ich ironischerweise auf einem direkten XING-Thread gelandet, der bereits sehr vielversprechend war. Dort wurden im wesentlichen genannt:
- http://de.wikipedia.org/wiki/Dijkstra-Algorithmus als theor. Erläuterung des Problems an sich
- http://www.boost.org/libs/graph/doc/index.html eine binäre Postgresql-Erweiterung (die sich vielleicht sogar für mySQL umschreiben ließe?
Diese Erweiterung stellt scheinbar direkt eine Dijkstra-Berechnung her:
Dijkstra - Shortest path algorithm computation on PostgreSQL
…
The shortest_path function has the following signature:
CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, target_id integer, > directed boolean, has_reverse_cost boolean)
RETURNS SETOF path_resultWhere path_result is:
CREATE TYPE path_result AS (vertex_id integer, edge_id integer, cost float8);
Außerdem verlinkt der XING-Thread auf http://forum.developers-guide.net/showthread.php?t=5071. Hier wiederum werden weitere Links bereitgestellt, die sich mit dem Thema auf sehr interessante Weise beschäftigen. Der interessanteste ist http://www.zdnet.de/builder/program/0,39023551,39124191,00.htm.
Kat: S/W-EntwicklungKeine Kommentare »