Forum: PC-Programmierung Graphen-Analyse


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich hab eine Art Graphenwolke

Die besteht größtenteils aus unidirektionalen
und ganz wenigen bidirektionalen Kanten und ein paar Knoten
nichts wildes so 100-300 Knoten/Kanten (relativ klein)

nicht alle Knoten können über alle Kanten erreicht werden d.h.
diese Kanten/Knoten bilden n gerichtete Graphen ohne Mehrfachkanten

Was ich von der Graphenwolke wissen möchte:
-welche Graphen (zusammenhängende Knoten über die uni und 
bi-directionalen Kanten gibt es)
-gibt es Zyklen (über die uni und bi-directionalen Kanten)

mein Algorithmus steht und funktioniert auch - bisschen 
Rekursion/Durchlaufene Knoten/Kanten merken usw.

Vor ein paar Tagen bin ich jetzt auf Adjazenzmatrix gestossen
https://en.wikipedia.org/wiki/Adjacency_matrix
und wollte wissen ob ich damit die beiden oberen Anforderungen mit 
bekannteren Standard-Algorithmen lösen kann (um z.B. Boost Graph zu 
verwenden oder auch einfach weniger dokumentieren zu müssen, oder auch 
weniger Rekursionen zu haben)

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?

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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).

von Softwareentwickler (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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++

von Softwareentwickler (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.