Boomstructuur kopieeren

[ZpAz]

Voor een klant ben ik momenteel bezig met een project en ik zit een beetje vast. Ik krijg data aangeleverd in de vorm van een boomstructuur alla:



Om het simpel te houden, elk item in de boom heeft een naam, id en mogelijk één of meerdere referenties naar een ander item. Nu wil ik de gehele boomstructuur en de data kopieren in een nieuwe boom. Maar elk item krijgt als je hem kopieert een nieuw ID. In de nieuwe boom moeten de referenties dus aangepast worden naar de juiste id's.

Nu kan ik wel recursief lopen door de boom om zo een lijstje te generen van alle items in de boom. Maar bijvoorbeeld doordat er een 'lus' in de boom zit (van project kan je bij koffiejuffrouw uitkomen welke weer naar project verwijst) zit ik vast.

Koffiejuffrouw kan pas een verwijzing bevatten naar project als project gemaakt is, maar deze kan pas gemaakt worden als koffiejuffrouw gemaakt is bijvoorbeeld.

Hoe los ik dit op. Ik hoop dat mijn vraagstelling een beetje duidelijk is.

[Nvidiot]

Dit artikel gaat specifiek over C++, maar het algoritme daarin is wellicht wel bruikbaar: http://www.parashift.com/...ialization.html#faq-36.11

[Armageddon_2k]

't is maar net hoe jij je ID's bepaalt. Als jij daar zelf zeggenschap over hebt, dan zou je een extra functie kunnen maken.
Dus een
Item_Copy()
Item_FlayCopy()

[ZpAz]

Op het moment dat een item wordt gemaakt wordt er een ID gegenereerd, hier heb ik dus geen zeggenschap over.

[Trolando]

Ik neem aan dat de oorspronkelijke boom ook ooit op een bepaalde manier opgebouwd is. Lijkt me het zo dat je een boom serialiseert naar een reeks instructies die nodig zijn om de boom op te bouwen, bijv:

1) maak knoop PROJECT
2) maak knoop ACHMEA als kind van 1
3) maak knoop KOFFIEJUFFROUW als kind van 2
4) maak een verbinding van 3 naar 1
enz.

En bij elke stap die een knoop maakt onthoudt je de ID.

En anders: vaak bestaat een graaf in de computer uit een verzameling knopen en een verzameling verbindingen, bijv:

Knopen: 1: project, 2:achmea, 3: koffiejuffrouw
Verbindingen: (1 -> 2), (2 -> 3), (3 -> 1)

Een graaf sla je dus op door simpelweg de lijst knopen te maken en de lijst verbindingen. Dat kan recursief, of wat dan ook, als je maar bijhoudt welke je al gehad hebt met een flag of met een hashtable.

Hoe laad je die graaf dan weer in? Je maakt eerst alle knopen. Vervolgens houd je intern bij welke ID elke knoop heeft gekregen, en dat gebruik je om alle verbindingen te leggen. Klaar!

Het ligt er een beetje aan met wat voor API je te maken hebt. Kun je zomaar knopen en verbindingen leggen, dan is dat de makkelijkste methode. Ben je afhankelijk van bepaalde commando's in een bepaalde volgorde om een graaf op te bouwen, doe het dan op die manier.

[ Voor 30% gewijzigd door Trolando op 25-06-2012 15:54 ]

[ZpAz]

Inderdaad Trolando, dat moet werken. Thanks.