kostenloser Webspace werbefrei: lima-city

Schlauer Algorithmus zur Abhängigkeitsauflösung gesucht

lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess

1. Autor dieses Themas

   fchriis

   fchriis hat kostenlosen Webspace.

   19:12, 23.2.2010

   Hallo,
   
   ich suche einen Algorithmus. Vielleicht habt ihr ein paar schlaue Ideen.
   Um einen fertigen Code gehts mir garnicht, Ideen oder schon erste PseudoCode-Schnippsel reichen mir völlig ;)
   
   Zum Problem:
   Ich will Abhängigkeiten auflösen.
   Beispiel:
   firephplib benötigt core
   benchmark benötigt core und firephplib
   acp benötigt core
   userverwaltung benötigt core und acp
   autouserhinzufügen benötigt core, userverwaltung (und damit auch acp) und firephplib
   
   Jetzt erstell ich aus diesen einzelnen Abhängigkeiten eine große Liste:
   

   Abhängigkeiten = [
     [firephplib, core],
     [acp, core],
     [benchmark, core],
     [benchmark, firephplib],
     [userverwaltung, core],
     [userverwaltung, acp],
     [autouserhinzufügen, core],
     [autouserhinzufügen, userverwaltung],
     [autouserhinzufügen, firephplib],
   ]

   
   
   Aus diesen ganzen Abhängigkeiten soll nun ein Baum mit Verästelungen werden.
   Jeder Ast entspricht damit einer Stufe.
   Auf Stufe 0 (also der Stamm) ist nur das Core-Plugin.
   Jedes Plugin ist eine Stufe höher als das Plugin mit der höchsten Stufe, das es benötigt.
   
   Damit sollte der Baum am ende so aussehen:
   

   Stufen/Äste = [
     [core], // stufe 0
     [firephplib, acp], // stufe 1
     [benchmark, userverwaltung], // stufe 2
     [autouserhinzufügen] // stufe 3
   ]

   
   
   Nun die große Frage: Wie erstell ich so einen Baum?
   
   Vielen Dank,
   Chris
   
   Beitrag zuletzt geändert: 23.2.2010 19:16:02 von fchriis

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. x*****k

   20:15, 23.2.2010

   Hallo.
   
   Nur eine kurze Frage die mich hier ein bisschen ins Irre führt.
   Müsste Autouserhinzufügen nicht auch eine Dependency zu Benchmark bilden?
   Ansonsten hätte ich schon einige Ideen parat.
   
   mfg x-bLacK
4. Autor dieses Themas

   fchriis

   fchriis hat kostenlosen Webspace.

   20:28, 23.2.2010

   x-black schrieb:
   Hallo.
   
   Nur eine kurze Frage die mich hier ein bisschen ins Irre führt.
   Müsste Autouserhinzufügen nicht auch eine Dependency zu Benchmark bilden?
   Ansonsten hätte ich schon einige Ideen parat.
   
   mfg x-bLacK
   

   
   
   nein, muss es nich, da Benchmark die FirePHPLib benötigt, das Autouserhinzufügen aber nur die FirePHPLib und Benchmark ja ein Ast höher ist.
   
   cool, wie wärn denn deine Ideen? ;)
   
   Edit:
   
   Ich hab mir jetz so kleine Zettelchen mit den einzelnen Plugins gemacht und probier etwas rum..
   Folgendes schwirrt mir grad im Kopf rum:
   Man geht die Pluginliste durch bis alles gefunden wurde. Für jedes Plugin prüft man ob in irgendeinem Ast ein Plugin ist, was es braucht. Wenn ja die Nummer notieren. Weiter alle Plugins durchsuchen und wenn die Nummer größer ist diese notieren statt der anderen. Wurden alle abhängigen Pakete zu diesem Paket gefunden, ist die gemerkte Nummer die Nummer des Astes mit höchster Abhängigkeit. Das Paket muss einen Ast drüber, also Nummer eins höher und in den Baum einhängen. Wurde alles gefunden das Paket aus der zuSuchenliste rauswerden. Wurde nicht alles gefunden, verbleibt das Paket in der Liste.
   
   so in etwa:
   

   $astNummern = array();
   $zuSuchenListe = $plugins;
   $zuSuchenListeKopie = array();
   
   // wenn zuSuchenListe == zuSuchenListeKopie, dann wird nichts mehr gefunden
   // verhindert eine endlosschleife, wenn was nich passen sollte :)
   while (count($zuSuchenListe) and $zuSuchenListe != $zuSuchenListeKopie) {
   	foreach ($zuSuchenListe as $zuSuchendesPlugin) {
   		$zuSuchendesPluginAstnummer = null;
   		$zuSuchendesPluginAbhaengigkeiten = $zuSuchendesPlugin['abhaengigkeiten'];
   		
   		$zuSuchendesPluginAbhaengigkeitenNochZuSuchen = count(..);
   		foreach ($zuSuchendesPluginAbhaengigkeiten as $zuSuchendesPluginAbhaengigkeit) {
   			$zuSuchendesPluginAbheangigkeitGefunden = false;
   			
   			// schauen ob Ast am Baum
   			foreach ($aesteAmAbhaengigkeitsbaum as $astNummer => $ast) {
   				if (in_array($zuSuchendesPluginAbheangigkeit, $ast)) {
   					$zuSuchendesPluginAbhaengigkeitGefunden = true;
   					
   					// größte nummer rausfinden
   					if ($astNummer > $zuSuchendesPluginAstnummer) {
   						$zuSuchendesPluginAstnummer = $astNummer;
   					}
   					
   					break;
   				}
   			}
   			
   			// Plugin gefunden -> 1 weniger zu suchen
   			if ($zuSuchendesPluginAbheangigkeitGefunden) {
   				$zuSuchendesPluginAbheangigkeitenNochZuSuchen--;
   			}
   		}
   		
   		// nix mehr zu suchen -> alles da -> plugin ok
   		if ($zuSuchendesPluginAbhaengigkeitenNochZuSuchen == 0) {
   			// alle Abhängigkeiten des Plugins gefunden
   			
   			$astNummern[$zuSuchendesPlugin] = ($zuSuchendesPluginAstnummer + 1);
   			kicke_aus_array($zuSuchenListe, $zuSuchendesPlugin);
   		}
   	}
   	
   	// kopie um später zu prüfen, ob noch plugins gefunden werden
   	$zuSuchenListenKopie = $zuSuchenListe;
   }

   
   
   dann hab ich alle astnummern. und dann muss ich nur aus den astnummern ein baum basteln :)
   was ja nich so schwer is :)
   
   is nur die frage, passt der algorithmus so oder muss man da noch was anpassen? ich hab ihn noch nich auf alle eventualitäten getestet..
   
   Beitrag zuletzt geändert: 23.2.2010 21:37:52 von fchriis

5. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?