Kleine Geschichtsstunde.
1967 startete der Psychologe/Soziologe Stanley Milgram (übrigends der selbe welcher das “Milgram Experiment” durchführte) das “Small World” Experiment. Milgram erstellte eine Art Informationspaket, das 60 zufällig ausgewählte Teilnehmer an jeweils eine vorher festgelegte Person in Boston zu senden hatten. Als Startpunkte wählte er Personen aus den sozial und geografisch weit von der Zielstadt entfernten Städten Omaha und Wichita. Die Aufgabe der Teilnehmer bestand darin, das Paket nicht direkt an die Zielperson zu senden, sofern sie diese nicht persönlich kannten (bei ihrem Vornamen ansprachen), sondern an eine Person, die sie persönlich kannten und bei der die Wahrscheinlichkeit höher war, dass sie die Zielperson kannte. Gleichzeitig waren die Teilnehmer angehalten, grundlegende Daten über sich selbst in einer Tabelle zu vermerken und eine Postkarte an die Wissenschaftler zu senden, um die Kette nachvollziehbar zu machen.
Insgesamt erreichten drei Pakete die Zielpersonen mit einer durchschnittlichen Pfadlänge von 5,5 oder aufgerundet sechs. Die Wissenschaftler schlossen daraus, dass jede Person der US-amerikanischen Bevölkerung von jeder anderen Person der USA durchschnittlich durch sechs Personen getrennt ist oder, andersherum formuliert, durch durchschnittlich sechs Personen erreicht werden kann.
In einem zwei Jahre später durchgeführten Experiment mit 296 möglichen Ketten wurden 217 Pakete gestartet und 64 erreichten ihr Ziel.[1] Im Jahre 1970 folgte ein weiterer Versuch, der, neben der Entfernung der Menschen untereinander, auch mögliche Grenzen zwischen ethnisch unterschiedlichen Gruppen untersuchen sollte. Von 270 mit afroamerikanischen Personen als Ziel gestarteten Paketen erreichten 13 % diese Person, während 33 % von wiederum 270 an „weiße“ Personen adressierte Pakete ihr Ziel erreichten.[2]
Möchte man jetzt die Verbindung von Person A zu Person B darstellen, läuft man schnell in das “shortest path problem“. Um dies zu lösen eignet sich der sogenannte “Dijkstra-Algorithmus“.
Wie sieht jetzt die Impementierung in PHP aus ?
Wir nehmen an wir haben eine Tabelle mit unseren Usern, und eine Zweite die Verbindungen von den Usern untereinander darstellt (fromid => toid).
CREATE TABLE IF NOT EXISTS `users` (
`id` int(11) NOT NULL auto_increment,
`firstnames` varchar(200) NOT NULL,
`lastname` varchar(200) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=22 ;
CREATE TABLE IF NOT EXISTS `links` (
`link_id` int(11) NOT NULL auto_increment,
`fromid` int(11) NOT NULL,
`toid` int(11) NOT NULL,
PRIMARY KEY (`link_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=11 ;
Als erstes brauchen wir den theoretisch längsten Pfad: Dies wäre die Anzahl der User +1.
Nächster Schritt das Basis array, welches die schritte von person x zu person y festlegt, da wir dies aber noch nicht wissen inintialisieren wir das array mit -1 (unbekannter pfad). Einen Pfad kennen wir jedoch nämlich den Pfad von $fromid zu $fromid. Dieser hat die Distanz 0.
private function _fetchUser(){
$m_user = new UserModel();
$this->_users = $m_user->fetchAll();
$this->_longestPath = $this->_users->count()+1;
}
private function _buildSkel($fromid){
if(!$this->_users){
$this->_fetchUser();
}
foreach($this->_users as $user){
$this->_nodes[]=$user->id;
$this->_dist[$user->id]=$this->_longestPath;
$this->_previous[$user->id]=-1;
}
if($fromid>0)
$this->_dist[$fromid]=0;
}
Jetzt beginnt der Spass, suchen des kürzesten Pfads von User A zu User B:
private function _findPath($toid){
$Q = $this->_nodes;
while(count($Q)>0){
$qsize=count($Q);
$unode = $this->_findMin($Q);
if($unode == $toid){
break; // We have found ToId
}
$u = array_search($unode, $Q);
$Q[$u]=false;
$Q = array_filter($Q);
if($qsize == count($Q)){
throw new Exception("Qsize doesnt shrink!");
}
$m_link = new LinksModel();
$invitees = $m_link->fetchAll("fromid='$unode'");
$inviters = $m_link->fetchAll("toid='$unode'");
if($invitees->count()>0)
$this->_relaxNeighbors($unode,$invitees,'toid');
if($inviters->count()>0)
$this->_relaxNeighbors($unode,$inviters,'fromid');
}
}
private function _relaxNeighbors($unode,$neighbors,$col){
foreach($neighbors as $neighbor){
$this->_relax($unode,$neighbor->$col);
}
}
private function _relax($u,$v){
if($this->_dist[$v] > $this->_dist[$u]+1){
$this->_dist[$v]=$this->_dist[$u]+1;
$this->_previous[$v] = $u;
}
}
private function _findMin($nodes){
$keys = array_keys($nodes);
$minid = $nodes[$keys[0]];
$mindist = $this->_dist[$minid];
foreach ($keys as $key){
$tnode = $nodes[$key];
if($this->_dist[$tnode] < $mindist){
$mindist = $this->_dist[$tnode];
$minid=$tnode;
}
}
return $minid;
}
Wir laufen also unsere Knoten durch und berechnen die Kantenlängen für jeden knoten. Dabei wird ein bereits bekannter kürzester Weg benutzt und um eine Kante (zu dem jeweils nächsten) Nachfolgeknoten ergänzt. Dadurch entsteht letztendlich eine Baumstruktur, welche die kürzesten Wege von einem Startknoten repräsentiert.
Die gesamte Klasse findet sich auf http://www.cwd.at/shortestpath.phps
Raum für Optimierung gibt es genug. Zb. das errechnen der Kantenlängen jedes Users zueinander und speichern in einer Tabelle. Oder aber auch den gesamten Algorithmus in die Datenbank auszulagern.
