Graphen-Analyse

Bidirektional ist wohl doch nicht ganz richtig - es sind Kanten die gar 
keine Richtung haben (oder die Richtung einfach nicht relevant ist - nur 
der Bezug zwischen den Knoten)

bei der Zyklus-Erkennung verhaltet sich diese neutral was den 
Richtungswechsel angeht

cppbert schrieb:

> Bidirektional ist wohl doch nicht ganz richtig - es sind
> Kanten die gar keine Richtung haben (oder die Richtung
> einfach nicht relevant ist - nur der Bezug zwischen den
> Knoten)

Die heißen m.W. einfach "ungerichtete Kanten".


> bei der Zyklus-Erkennung verhaltet sich diese neutral
> was den Richtungswechsel angeht

Ungerichtete Kanten lassen sich m.W. äquivalent durch
"antiparallele" Paare von gerichteten Kanten ersetzen.

cppbert schrieb:

> Könnt ihr mir Algorithmen nennen die für die obigen
> Anforderungen gut passen würden oder ist eine
> Adjazenzmatrix in meinem Fall nicht wirklich sinnvoll?

Ich verstehe zu wenig von Graphentheorie, um Dir gezielt
helfen zu können, aber:

1. Für die mathematischen Grundlagen ist sicher ein gutes
Lehrbuch am hilfreichsten; die online verfügbaren Tutorien
finde ich ziemlich lückenhaft und nicht unbedingt gut
verständlich.
Unter Umständen findest Du heraus, dass Dein Graph spezielle
Eigenschaften hat, die sich vorteilhaft ausnutzen lassen --
dann ist weniger brutale Gewalt notwendig.

2. Da man die Knoten nummerieren und i.d.R. auch sortieren
kann, lassen sich für manche Zwecke n*log(n)-Algorithmen
konstruieren. Für Deine relativ kleinen Graphen genügt das
unter Umständen schon.

3. Wenn im Mittel jeder Knoten deutlich weniger Kanten
hat, als Dein Graph insgesamt Knoten besitzt (-- anders
gesagt: wenn Dein Graph "sehr weit" vom vollständigen
Graphen "entfernt" ist), dann wird die Adjazenzmatrix
schwach besetzt und damit wenig nützlich sein (vermute
ich).

Die Antwort auf beide Fragen lautet: Tiefensuche und Färbung

color = 1
foreach node:
  if node is uncolored:
    depth-first-search(node, color) //recursively traverses graph, 
colors nodes and detect cycles
  color++

Softwareentwickler schrieb:
> Die Antwort auf beide Fragen lautet: Tiefensuche und Färbung
>
> color = 1
> foreach node:
>   if node is uncolored:
>     depth-first-search(node, color) //recursively traverses graph,
> colors nodes and detect cycles
>   color++

Zur Erklärung, du startest von einem Knoten aus eine Tiefensuche und 
markierst alle Knoten mit derselben Farbe die du währenddessen besuchst 
(triffst du auf einen schon gefärbten knoten mit derselben farbe, hast 
du einen Zyklus entdeckt), triffst du auf einen schon anders gefärbten 
Knoten überschreibst du die Farbe einfach. Am Ende schaust du wie viele 
verschiedene Farben in deinem Graphen vorherrschen. Das würde bei 
folgendem Graphen 2 ergeben:

O->O<-O

Wenn das Ergebnis 1 lauten soll, musst du jede Kante als ungerichtet 
betrachten bei der Färbung und nur für die Zyklendetektierung gerichtete 
Kanten berücksichtigen.

Danke für die Tips, ich hab jetzt meinen Graphen von meinen Objekten 
total entkoppelt und mit dem einfärben gearbeitet - viel kleiner und 
übersichtlicher