Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Gerichteter azyklsicher Graph speichern
Alphawolf1988
myCSharp.de - Member



Dabei seit:
Beiträge: 68

Themenstarter:

Gerichteter azyklsicher Graph speichern

beantworten | zitieren | melden

Hallo liebe Community!

Ich stehe mal wieder vor einem Problem. Hat Jemmand eine Idee wie ich einen gerichteten azyklischen Graphen abspeichern kann als Datei mit so wenig Platzverbrauch wie möglich.

Vllt irgendwelche Strategien oder Ideen?

Ein Beispielgraph wäre:

siehe Anhang

Danke im vorraus,

Wolf
Attachments
Wer zuerst kommt malt zuerst, wer danach kommt malt drüber!
private Nachricht | Beiträge des Benutzers
VizOne
myCSharp.de - Member

Avatar #avatar-1563.gif


Dabei seit:
Beiträge: 1551

beantworten | zitieren | melden

Musst du per Node Daten speichern oder reichen dir die Edges?

Schau dir mal das dot Format von Graphviz an. Das ist zwar ein Textformat, aber als Anschauungsmaterial sicherlich nicht schlecht.

Hier einige Möglichkeiten, deinen Graph zu repräsentieren (angelehnt an dot):
1) Jede Edge einzeln: A->B;B->C;B->D;B->E;C->E;D->E;G->D;E->F
2) Jeden Ausgangsknoten einzeln: A->B;B->(C,D,E);C->E;D->E;G->D;E->F
3) Pfade: A->B->C->E->F;B->D;B->E;G->D->E
4) 2) und 3) kombiniert: A->B->C->E->F;B->(D,E);G->D->E

Am einfachsten zu speichern ist sicherlich Version 1, weil jede Edge als ein Paar Node IDs repräsentiert wird. Als Binärformat reicht es dann aus, zunächst die Anzahl Paare und danach je Paar die zwei IDs zu speichern. Die Auswahl des Datentyps für jeden Wert hängt vom Anwendungsfall ab (Größe des Graphs): für kleine Graphen z.B. bytes, oder allgemein z.B. 7-bit komprimierte Integer (siehe http://msdn.microsoft.com/en-us/library/system.io.binarywriter.write7bitencodedint.aspx)

Grüße,
Andre
private Nachricht | Beiträge des Benutzers
Alphawolf1988
myCSharp.de - Member



Dabei seit:
Beiträge: 68

Themenstarter:

beantworten | zitieren | melden

Ich muss sowohl die Knotenübergänge speichern, als auch die Inhalte der Blätter am Ende (1 Byte groß pro Blatt).
Danke für die Ansätze erstmal!

MFG Wolf
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Alphawolf1988 am .
Wer zuerst kommt malt zuerst, wer danach kommt malt drüber!
private Nachricht | Beiträge des Benutzers
Schlopp
myCSharp.de - Member

Avatar #avatar-3124.jpg


Dabei seit:
Beiträge: 299
Herkunft: Stuttgart, München, Schweiz

beantworten | zitieren | melden

Ich meine mich daran erinnern zu können, das man Graphen recht gut mit verketteten Listen im Speicher darstellen kann, also sollte es ja auch beim Speichern in einer Datei funktionieren: Dazu zunächst einfach mal alle Knoten miteinander verknüpfen: A - B - C - D - E - F - G anschließend zu jedem Knoten speichern, welcher andere Knoten von diesem erreicht werden kann: A - B | B - C - D - E | C - E | D - E | E - F | F | G - D Kann man auch recht einfach mit XML oder soetwas umsetzen.
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Schlopp am .
There are 10 kind of people, those who understand binary and those who don't.
private Nachricht | Beiträge des Benutzers