[php] 1/2 OT: Wegfindung mit PHP

[Dr. Volker M. Göbbels]

Ahoi Andreas ;)

>> Kruskal: http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
>
> Ups, richtig: Kuskal statt Chruschtschow. Hatte den Namen nur
> noch so halbwegs im Kopf ;-) Mea maxima Culpa...

Ego te absolvo ;o)

Nein im Ernst, bevor ich das Wikipedia gefunden hatte, hatte ich noch 
nie was von diesen Algorithmen gehört. Ich hab sowas immer quasi 
"empirisch bzw. heuristisch" gelöst. Viele der Algorithmen sind ja ah 
Heurismen. Bin halt Chemiker ;)

Aber natürlich ist mir eben aufgefallen, daß Ringschlüsse, bei denen 
ich wissen will, ob die Kante A-B in einem Ring liegt identisch sind 
mit dem Problem: Finde einen Pfad von A nach B ohne die direkte 
Verbindung zu nutzen.

Gebraucht wird das ganze bei einem PHP Script, welches sog. Mol-Files 
als Gif/Png plotten kann. Molfiles sind im Prinzip reine ASCII-Files 
mit den x/y/z Koordinaten aller in einem Molekül vorkommenden Atome und 
dahinter einer Liste aller Verbindungen, also Atom 1 an Atom 4 mit 
einer Doppelbindung usw.

Zum richtigen Anzeigen (so wie picky chemists das gern sehen würden) 
ist es nun wichtig, Doppelbindungen in Ringen anders zu malen als 
solche in offenen Ketten :-} Und dazu suche ich halt einen Algorithmus, 
der mir das liefert. Klingt eigentlich einfach - ist aber gar nicht so 
trivial. Ich muß mir wohl auch nochmal Gedanken über die Art der 
Datenstruktur machen, in der ich die Atombindungen ablege.
Dazu kommt, daß nahezu alle Algorithmen natürlich rekursiv sind - prima 
Sache, wenn der User drauf wartet, daß diese blöde Strukturformel 
endlich erscheint ;o) Notfalls mach ich halt C/C++ draus ;)

Viele Grüße,
Volker Göbbels
-- 
Dr. Volker Göbbels								vmg at arachnion.de
Arachnion GmbH & Co. KG						http://www.arachnion.de
Sandkaulbach 4								Tel. ++49 (0) 241 5591106
52062 Aachen									Fax ++49 (0) 241 5591107
Besuchen Sie uns auf dem Linux Tag 2004 in Karlsruhe!  
http://www.linuxtag.org