• Hallo liebe Userinnen und User,

    nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.

    Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance.
    Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.

    Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.


    Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.

Listen aus Graph generieren

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
Irgendwie stehe ich auf dem Schlauch gerade.

Ich baue mir aus Listen nach gewissen einfachen Regeln Pfade bzw. einen Graphen. Also keinen Graphen im visuellen Sinne, aber man könnte es als Graphen (DAG) darstellen, wenn man wollte. So sehen die Listen aus, die ich als Input habe:
[src=yaml]
name: A1
name_specs:
- B1
- C1
kind:
- D:
- E
- F
- G:
- H


property1:
- x
- y
property2:
- z
[/src]
Ich baue mir daraus einen Haufen materialized paths. Dabei ist 'name' die erste Ebene, 'name_specs' die zweite, 'kind' die dritte und vierte. Das sieht dann so aus:
[src=ruby]
/A1/B1/D/E/
/A1/B1/D/F/
[...]
[/src]
Diese haben dann m:n Verbindungen zu den properties.
Die Listen sind so zu lesen, dass ich alle Pfadvarianten auspräge, welche die Liste ermöglicht. Man könnte das vllt so schreiben:
[src=ruby]
/A1/{B1,C1}/D/{E,F}
/A1/{B1,C1}/G/H
[/src]
D.h. aus der Liste ganz oben würden jetzt 4+2 = 6 Pfade entstehen. Jeder dieser Pfade bekommt dann die zugehörigen Verbindungen zu den aufgeführten properties. Natürlich gibt es noch mehr Listen mit meistens anderen Pfaden und auch anderen Kombinationen an properties und natürlich mehr 'names' etc. Die realen Einträge sind natürlich auch länger und es gibt mehr als 3 Properties.

Ziel Aus den generierten Pfaden wieder die Listen generieren.
Erste Frage die sich mir stellt: Unten oder oben anfangen? Ich habe jetzt Erstmal 'oben' an der Wurzel angefangen.

Mein Ansatz war jeweils pro Ebene zu gruppieren:
[src=ruby]
Names.all.group_by{name_specs}
[/src]
Daraus kriege ich dann Dictionaries/Hashtables mit jeweils einer Menge an name_specs als Schlüssel und den passenden name als Werten. also sowas wie das hier:
[src=ruby]]
{
{B1,C1} => {A1}
{B1, C2} => {A2}
}
[/src]
A2, B2, C2 sind hypothetische Einträge aus anderen Listen.


Das wollte ich jetzt ebene für Ebene runter gehen immer gruppieren und dann am Ende die Liste bauen.
* Was haltet ihr davon? Geht das so überhaupt?
* Geht es anders vielleicht besser? Ich finde diese "/A/{B,C}/D/{E,F}" Darstellung höchst ansprechend, aber mir will einfach nicht kommen, wie ich die generiere.
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Ziel Aus den generierten Pfaden wieder die Listen generieren.
[...]
Ich finde diese "/A/{B,C}/D/{E,F}" Darstellung höchst ansprechend, aber mir will einfach nicht kommen, wie ich die generiere.
Das verwirrt mich ein bisschen. Willst du die Pfade oder die Listen generieren? Oder steh gerade ich auf dem Schlauch?

Seh ich das richtig, dass du erstmal aus den Listen einen Baum ausfaltest und ein Graph erst unten bei den Properties entsteht?
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
  • Thread Starter Thread Starter
  • #3
Das verwirrt mich ein bisschen. Willst du die Pfade oder die Listen generieren? Oder steh gerade ich auf dem Schlauch?
Ich habe zuerst diese Listen vorliegen. Daraus baue ich dann die Pfade. Dann will ich wieder die Listen daraus genieren und eben dieser Schritt ist das Problem ;-).
Es reicht leider nicht einfach die Listen zu speichern da a) es vorkommen kann, dass sich drei Listen zu einer zusammenführen lassen und b) auch Einträge beliebig geändert und entfernt werden können.

Seh ich das richtig, dass du erstmal aus den Listen einen Baum ausfaltest und ein Graph erst unten bei den Properties entsteht?

Die Darstellung als Liste täuscht ein wenig.
Es sind durchaus solche Pfade möglich (bzw. Listen die solche Pfade generieren):

/A1/B1/K/V
/A2/B2/K/V
Wobei ich hier jeweils von gerichteten Kanten ausgehe (A1/B1 = Es gibt eine Kante von A1 nach B1).
Was nicht vorkommen kann ist das z.B. K in Ebene 3 und auch Ebene 2 auftaucht. Jeder Knoten ist auf eine einzelne Ebene beschränkt. Dadurch wird das ganze zu einem DAG.


PS.:
Ich glaube es spielt für theoretische Überlegungen keine Rolle, aber es sind auch alle 'Teilpfade' gespeichert, also
/A1
/A1/B1
etc.
Aber nur immer von der Wurzel bzw. Ebene 0 ausgehend, sowas wie /K/V gibt es nicht extra abgespeichert.

--- [2020-04-23 20:35 CEST] Automatisch zusammengeführter Beitrag ---

-----------
Aktuelle Idee:

Je Ebene schaue ich mir die Transitive Hülle an aka die Menge aller "Kinder" (bis in die unterste Ebene) an. Angefangen bei der ersten Ebene. Also schaue mir an, Ob /A1/* und /A2/* identisch sind und wenn ja, dann pack ich die in die selbe Liste. Wenn jetzt ein /A3/* gibt das anders ist habe ich eine zweite Liste. Sagen wir ich habe dann {/A1/*, /A2/*}, {/A3/*}. Es kann aber sein, dass bei /A3 noch multiple Unterschiede existieren. Also schaue ich mir jetzt /A3/B1/*, /A3/B2/*, ... also alle direkten Kindern von /A3 an und gruppiere wieder nach gleichen Sub-Graphen. Dann habe ich {/A3/B5/*, /A3/B8/*}, {/A3/B2/*, /A3/B7/*, ...}, ... und so weiter.
Und das dann so weiter bis in Ebene 4.
Könnte das funktionieren? Bin mir mit dem genauen Algo aber grad noch nicht ganz klar.
 
Zuletzt bearbeitet:

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Dein Ansatz aus dem Startpost klingt nach einem simplen breadth-first traversal über den Graphen, wobei jede Traversal-Ebene einer Listenebene entspricht. Das passt sehr fein zu deinem ersten Listenbeispiel.

Deine »aktuelle Idee« mit der transitiven Hüllen ist dagegen ein depth-first-Ansatz, bei dem du anhand der Knoten auf der obersten Ebene Teilgraphen bildest. Das klingt so, als hättest du mehrere Listen vom gleichen Typ (z.B. mehere Instanzen von »name«), die alle in denselben Graphen gemergt werden. Ist das so? Dann mergt du ja mehrere Input-Datenstrukturen in eine einzelne Output-Datenstruktur. Wie sind dann die Regeln für die Graphbildung? Evtl. hast du Informationen verloren und kannst den Weg vom Graph zurück zu den Listen gar nicht mehr gehen.

Wenn die Teilgraphen unabhängig sind, klappts. Dann kannst du über die transitive Hülle auf oberster Ebene den Satz an Input-Datenstrukturen wiederherstellen. Und die weiteren Listenebenen kriegst du pro Teilgraph per breadth-first. … OK, das ist ein Stück weit Spekulation. Vermutlich hab ich irgendwo noch etwas nicht verstanden.

--- [2020-04-24 21:04 CEST] Automatisch zusammengeführter Beitrag ---

Mit einer »Inputdatenstruktur« meine ich einen Satz Listen wie ganz oben im ersten Beispiel. Sollte ich vermutlich dazu sagen. ;)
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
  • Thread Starter Thread Starter
  • #5
Dein Ansatz aus dem Startpost klingt nach einem simplen breadth-first traversal über den Graphen, wobei jede Traversal-Ebene einer Listenebene entspricht. Das passt sehr fein zu deinem ersten Listenbeispiel.

Deine »aktuelle Idee« mit der transitiven Hüllen ist dagegen ein depth-first-Ansatz, bei dem du anhand der Knoten auf der obersten Ebene Teilgraphen bildest. Das klingt so, als hättest du mehrere Listen vom gleichen Typ (z.B. mehere Instanzen von »name«), die alle in denselben Graphen gemergt werden. Ist das so? Dann mergt du ja mehrere Input-Datenstrukturen in eine einzelne Output-Datenstruktur. Wie sind dann die Regeln für die Graphbildung? Evtl. hast du Informationen verloren und kannst den Weg vom Graph zurück zu den Listen gar nicht mehr gehen.
Danke für den Input und die Insights was Graphenalgos angeht.
Die Regel für den Output lautet: So wenige Listen wie möglich (= so kleine Graphen wie möglich, denke ich).

Wenn die Teilgraphen unabhängig sind, klappts. Dann kannst du über die transitive Hülle auf oberster Ebene den Satz an Input-Datenstrukturen wiederherstellen. Und die weiteren Listenebenen kriegst du pro Teilgraph per breadth-first. … OK, das ist ein Stück weit Spekulation. Vermutlich hab ich irgendwo noch etwas nicht verstanden.
Das hab ich grad noch nicht verstanden, ist aber auch spät, werde ich drüber nachdenken.
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
[src=ruby]/A1/{B1,C1}/D/{E,F}
/A1/{B1,C1}/G/H[/src]

[src=ruby]
A1
/ \
B1 C1
/ \
D G
/ \ |
E F H
[/src]

Passt doch ins Schema? Also sollte Breadth-first (Fancy name stuff) doch einfach implementierbar sein. Oder übersehe ich etwas?

Du mußt auch jedes Element nur einmal erfassen dabei. Einmal die Wurzel/das Elternelement, X Kinder (B1, C1, D1) und deren Kinder.

Wenn jetzt C1 mehre "Partner" hätte würde der Graph einfach noch in einer zweiten Ebene zwischen B1 und C1 aufgesplittet bzw. als Partner referenziert werden:

[src=ruby]
A1
/ \
B1 C1 --- C+P1 --- C+P2
/ \ / \ \
D G I J K
/ \ |
E F H
[/src]

Wichtig ist nur zu vermerken, das jedes "Elternelement" dann "keine, ein oder mehrere Partner hat" also die Referenzen von C1 auf +P1 und +P2 (C+P1 und C+P2 gehören nicht zusammen sonder jeweil zu C.

Das ist glaube ich der geringste Overhead.
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Das hab ich grad noch nicht verstanden, ist aber auch spät, werde ich drüber nachdenken.
Hast recht, ist spät. Deswegen nur ein schnelles Bild:

Das ist ein Graph bestehend aus zwei unabhängigen Teilgraphen, die aus zwei verschiedenen Sätzen von Inputlisten entstanden sind. Der linke Teilgraph hat zwei Köpfe (A1, A2), der rechte nur einen (A3). Unabhängig sind sie, weil es keine Kanten zwischen ihnen gibt.

Solange du dieses Bild hast, ist alles bestens. Du kriegst deine zwei Sätze Inputs einwandfrei wieder zurück. Wenn du zwischen den Teilgraphen auch nur eine Kante einziehst, kannst du nicht mehr eindeutig entscheiden, welche Knoten aus welchem Satz Inputs kamen. Wenn du z.B. C2->G ziehst, woher stammen dann G und H? Das ist nicht mehr entscheidbar, zumindest nicht ohne zusätzliche Informationen zu speichern. Und an dem Punkt sind wir bei dem, was theSplit sagt.
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
  • Thread Starter Thread Starter
  • #8
Ah ok, verstehe.
Wenn es noch eine Kante C2->G gäbe, dann ergäbe das in meinem Sinne drei Teilgraphen. Ich würde dann /A3/C2/G/H und /A3/C2/G2/H2 bauen.
Deswegen funktioniert der breadth-first Ansatz auch nicht (und ich glaube das von dir, thesplit auch nicht) und ich muss das über die Transitive Hüllen (= alle direkten und indirekten Kinder anschauen) machen, jedenfalls so mein gedanklicher aktueller Stand.
Ein Punkt scheint auch nicht klar gewesen zu sein: Einzelne Knoten können in verschiedenen Listen gewesen sein, bzw. zu verschiedenen Listen gehören. Es muss auch nicht Original die selben Listen hergestellt werden, bzw. das geht nicht, weil der Graph zwischendurch geändert wurde. Es müssen nur hinterher so wenige Listen wie möglich sein.

@theSplit:
[src="ruby"]
/A1/{B1,C1}/D/{E,F}
/A1/{B1,C1}/G/H
[/src]
Das ergibt insgesamt 6 Pfade:
[src="ruby"]
/A1/B1/D/E
/A1/B1/D/F
/A1/C1/D/E
/A1/C1/D/F
/A1/C1/G/H
/A1/B1/G/H
[/src]
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
@BurnerR: Und wenn du es so zusammenfasst:
/A1 / B1+C1 /D/E
/A1 / B1+C1 /D/F
/A1 / B1+C1 /G/H

3 Pfade, wobei B1 und C1 zusammengefasst werden da sie alle mit "A1" zusammenhängen und in gleicher Kombination zusammenkommen.
Also wäre es vielleicht ein Trick sich auf die "zweite" Stufe der Pfade ausgehend, zu konzentrieren und diese auf gleiche Paarungen hin zu untersuchen? Also wo kann man zusammenfassen und wo geht das nicht. Als immer dann, wenn B1 und C1 auf ein Kindelement verweisen.
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
BurnerR schrieb:
Einzelne Knoten können in verschiedenen Listen gewesen sein, bzw. zu verschiedenen Listen gehören.
Guter Hinweis Das ändert das Teilgraphen bauen ein Stückchen. Macht aber nix kaputt, soweit ich das sehe.

BurnerR schrieb:
Wenn es noch eine Kante C2->G gäbe, dann ergäbe das in meinem Sinne drei Teilgraphen. Ich würde dann /A3/C2/G/H und /A3/C2/G2/H2 bauen.
[...]
Es müssen nur hinterher so wenige Listen wie möglich sein.
Da hast du imo einen Widerspruch. Pro Teilgraph erzeugst du ja einen Listensatz. Die beiden /A3/… kannst du aber in einem Listensatz abbilden. Ich überleg’s mir immer so: Wenn ich die finalen Listen habe und aus denen wieder den gleichen Graphen ausmultiplizieren kann, hab ich noch nicht zuviel zusammengefasst.

Ich denke immer noch, dass transitive Hülle + breath-first funktioniert. Nehmen wir mein Bild von oben plus eine C2->G-Kante als Beipsiel.

Schritt 1: Die Teilgraphen kriegst du, wie du’s schon beschrieben hast über die transitive Hülle. Die von A1 und A2 aus erreichbaren Knoten sind exakt dieselben => ein Teilgraph. Von A3 aus ist eine andere Menge an Knoten erreichbar => zweiter Teilgraph. Und zwar beinhaltet der A3, C2, G, H, G2, H2. Dass sich beide Teilgraphen bei G und H überschneiden, macht nix, weil Dopplungen in den Inputlisten erlaubt sind.

Schritt 2: Für den ersten Teilgraph erstellst du einen Listensatz, indem du im Graph Ebenen bildest, so wie sie sich bei einem breadth-first traversal ergeben würden. Dein Gruppierungsansatz von ganz oben müsste aufs gleiche Ergebnis rauslaufen. Mir fällt es nur leichter, in Traversal-Algorithmen zu denken. ;) Die breadth-first-Ebenen entsprechen den Listenebenen.

Schritt 3: Rinse and repeat für alle übrigen Teilgraphen.
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
  • Thread Starter Thread Starter
  • #11
Schritt 1: Die Teilgraphen kriegst du, wie du’s schon beschrieben hast über die transitive Hülle. Die von A1 und A2 aus erreichbaren Knoten sind exakt dieselben => ein Teilgraph. Von A3 aus ist eine andere Menge an Knoten erreichbar => zweiter Teilgraph. Und zwar beinhaltet der A3, C2, G, H, G2, H2. Dass sich beide Teilgraphen bei G und H überschneiden, macht nix, weil Dopplungen in den Inputlisten erlaubt sind.

Schritt 2: Für den ersten Teilgraph erstellst du einen Listensatz, indem du im Graph Ebenen bildest, so wie sie sich bei einem breadth-first traversal ergeben würden. Dein Gruppierungsansatz von ganz oben müsste aufs gleiche Ergebnis rauslaufen. Mir fällt es nur leichter, in Traversal-Algorithmen zu denken. ;) Die breadth-first-Ebenen entsprechen den Listenebenen.

Schritt 3: Rinse and repeat für alle übrigen Teilgraphen.
Ich baue den Algo morgen mal und werde natürlich berichten :-).





@BurnerR: Und wenn du es so zusammenfasst:
/A1 / B1+C1 /D/E
/A1 / B1+C1 /D/F
/A1 / B1+C1 /G/H

3 Pfade, wobei B1 und C1 zusammengefasst werden da sie alle mit "A1" zusammenhängen und in gleicher Kombination zusammenkommen.
Also wäre es vielleicht ein Trick sich auf die "zweite" Stufe der Pfade ausgehend, zu konzentrieren und diese auf gleiche Paarungen hin zu untersuchen? Also wo kann man zusammenfassen und wo geht das nicht. Als immer dann, wenn B1 und C1 auf ein Kindelement verweisen.
Das Ergebnis wäre halt in meinem Sinne falsch weil nicht genug zusammen gefasst. Es treten auch nicht unbedingt Paare auf, sondern beliebige Gruppen.
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
  • Thread Starter Thread Starter
  • #12
So, ich hatte kurz nach dem Beitrag einen Algo gebaut und hatte jetzt endlich Gelegenheit den auf Realdaten loszulassen.
Nach erster Inspektion sieht es sehr cool aus! Ich hatte aber glaube ich noch ein zwei Details vercheckt gehabt in der Beschreibung des Problems. Ich hoffe ich werde noch Muße zu einem kleinen "Post mortem" haben. Jedenfalls hat mir der Dialog hier extrem weiter geholfen!
Geschwindigkeit ist 'schnell genug' mit 1-2 Minuten bei 1.000 Begriffen und 6.500 Pfaden.
 
Oben