Graphenverarbeitung

[3_of_8]

Morgen,

ich habe gerade ein Problem, einen Algorithmus zu finden. Ich habe einen zusammenhängenden, ungerichteten Graphen. Ich würde jetzt gerne alle Zyklen in diesem Graphen finden und die dazugehörigen Knoten irgendwie markieren. Wenn ich die markierten Knoten jetzt entferne, habe ich entweder gar nichts mehr oder einen oder mehrere nichtzyklische Graphen.

Ich nehme mir jetzt einen beliebigen solchen Graphen. Dann ist dieser Graph praktisch eine (möglicherweise verzweigte) Kette. Aus diesem Graphen würde ich jetzt gerne die längste Kette auswählen.

Wie kann ich das halbwegs effizient realisieren? Beim ersten Teilproblem habe ich mir überlegt, einfach einen Knoten auszuwählen und per Tiefensuche durchzugehen, wobei ich jeden besuchten Knoten markiere, und wenn ich bei der Suche auf einen schon markierten Knoten stoße, dann habe ich einen Zyklus gefunden. Wenn ich außerdem noch eine aufsteigende Nummerierung verwende, müsste ich auch in der Lage sein, zu bestimmen, wie viele Knoten der Zyklus lang ist.

Beim zweiten Problem aber fällt mir außer Bruteforcing kein Ansatz ein, der alle Fälle abdeckt.

[3_of_8]

Nach einem Monat werde ich wohl mal pushen dürfen.

[Nikolas]

Das Problem, zu entscheiden, ob ein Graph einen Zyklus hat, der eine bestimmte Länge überschreitet ist NP-Vollständig. Dein Problem, den längsten Zyklus zu finden, ist darauf zurückzuführen, so dass es wohl für dein Problem keine effiziente Lösung (also ein Algorithmus in P) geben wird, ein Brute Force Ansatz ausnahmsweise doch ganz gut.

[3_of_8]

Das mit der NP-Vollständigkeit habe ich schon befürchtet.

Ich suche nicht den längsten Zyklus sondern alle Zyklen und dann nehme ich mir alle (bzw. es reicht ja die Betrachtung von einem) nichtzyklischen Teilkomponenten und suche da nach der längsten Kette.

Wenn es hilft: Was ich da eigentlich machen will ist ein organisches Molekül zu analysieren und zu benennen.

[jfheins]

Also die Zyklen kann man ja mit Tiefensucher erschlagen.

Dann kannst du ungefähr so vorgehen, dass du dir einen beliebigen Knoten nimmst. Du weist, er ist Teil eines zusammenhängenden nicht-zyklischen Graphen.

Jetzt führst du für diesen Knoten wieder eine Tiefensuche durch, sodass du für jedes Kindelement eine Zahl bekommst, "wie tief es geht" also wie weit man gehen kann. Nimm die beiden maximalen Werte und du hast die länge der längsten Kette für diesen (Teil-)Graphen.

Idealerweise strechst du alle Knoten aus einer Liste heraus, die du auf diesem Weg besucht hast. (Du besuchst ja alle Knoten dieses Teilgraphen)
Jetzt kannst du das gleiche nochmal für den nächsten Knoten in der Liste machen (der noch nicht herausgestrichen ist)

Das sollte die Längste Kette liefern ;)

(Alternativ zur Liste geht natürlich auch ein Boolean-Flag oder sowas in der Art...)

Aber ich würde das nicht Brute-Force nennen, das klingt so Zeitaufwändig :mrgreen:

[3_of_8]

Mein Problem bei diesem Ansatz war eigentlich immer, was ich mache, wenn ich einen Knoten erwische, der nicht Teil der längsten Kette ist. Aber es stimmt schon, mit deinem Ansatz kann man die beiden Endknoten herausfinden. Dann muss ich eigentlich nur noch eine iterative Tiefensuche von Knoten 1 zu Knoten 2 durchführen, die terminiert, wenn Knoten 2 gefunden wurde. Das kann ich ja dann für die Seitenketten wiederholen.

Naja, das wäre schonmal ein Ansatz. Ein Problem bei den Zyklen ist, was ist, wenn ich kondensierte und/oder verbrückte Zyklen, Spiroverbindungen oder noch kompliziertere Verbindungen habe.

[Nikolas]

Wie groß sind denn deine Moleküle? Wäre Brute Force wirklich ein Zeitproblem?

[3_of_8]

Joa, wie groß sind die denn... ehrlich gesagt, keine Ahnung, so groß wie möglich, würde ich mal sagen. Und da bietet es sich dann halt an, einen möglichst effizienten Algorithmus zu finden.

[Nikolas]

so was solltet du klären, bevor du dich an den Algorithmus setzt. Wenn es wichtige Moleküle sind, kannst du auch mal ne Nacht dran rechnen. Hast du eine grafische Darstellung der Moleküle? Vielleicht wäre auch ein halbautomatisierter Vorgang interessant, in dem du Atome im Zyklus per Hand vorgibst.

[3_of_8]

Naja, es geht ja hierbei nicht um eine Lösung für Moleküle bestimmter Größe. Es geht um Moleküle, die der Benutzer eingeben kann. (graphisch oder auch per SMILES oder sowas in der Art) Ich will mich mal an einem kleinen Chemie-Zeichenprogramm mit ein paar Zusatzfunktionen versuchen, so wie ISIS/Draw (im kleineren Stil natürlich) oder wie diese ganzen kommerziellen Programme heißen.

Ich vermute mal, allzu groß können die Moleküle konzeptbedingt nicht werden, also ein komplettes Protein wird da wohl keiner eingeben, aber ein paar hundert Atome können das im Extremfall schon werden (wobei dann eine längere Wartezeit natürlich auch angemessen ist)

Daher suche ich eine asymptotisch ideale Lösung. (Kommerzielle Programme brauchen bei mittelgroßen Molekülen auch durchaus 5-10 Sekunden, was dafür spricht, dass die Lösung doch recht aufwändig ist)