[MySQL+PHP] Hoe een graaf afbeelden? *

[douweh]

Dit is eigenlijk niet specifieks iets voor mysql en php, maar hier in moet het wel gebeueren, dus vandaar deze titel.

Zie het volgende schema:



Je moet als gebruiker een stappenplan kunnen doorlopen, en in dit geval zijn, wit de vragen, roze de opties, en groen de eindstations..

Ik wil dit schema uit een database kunnen trekken en zo printen..
Wat is dan de moeilijkheid? Een item kan meerdere parents hebben om het zo maar even te noemen..

Normaal gesproken zou ik gewoon recursief vanaf boven kunnen beginnen en steeds alle childs afdrukken behorend bij een item.

Nu is het alleen zo, dat bijvoorbeeld vraag "3 Prima verder?" zowel onder optie "1Appels3" valt als onder optie "3Groene3".

Weet er iemand een methode om dit goed aan te pakken?

[pistole]

douweh schreef op vrijdag 26 november 2004 @ 18:52:Nu is het alleen zo, dat bijvoorbeeld vraag "3 Prima verder?" zowel onder optie "1Appels3" valt als onder optie "3Groene3".

Dat zou je kunnen oplossen door in je datamodel geen gebruik te maken van "parents" maar van "childs"

3Groene3 leidt tot 3Prima
1Appels3 leidt tot 3Prima

Dat lijkt me niet to problematisch?
Vervolgens zou ik rekening houden met "element type": is het een vraag, een aktie, etc

[douweh]

Ja, in dit model houd ik al wel rekening met element type,
de roze elementen en de witte+groene zouden in gescheiden tabellen komen..

in dit geval zijn de rozen als volgt van naam voor zien:

"eigenid naam idvervolgvraag".

Het is alleen meet hoe print je zoiets met php, want je kan niet gewoon alle keuzes bij een vraag printen, en daaronder simpelweg weer de vragen die bij die keuzes horen, want dan kom je er op een gegeven moment achter, dat een antwoord op een vraag doorverwijst, naar een vraag die je al geprint hebt

[Infinitive]

Dat je een graaf hebt in plaats van een boom maakt zaken een stuk gecompliceerder. Je kunt nu situaties tegenkomen waarin er altijd een kruisende lijn is. Ik weet niet wat een goede voorwaarde is voor een "mooi" schema, maar ik denk dat dat min of meer betekent dat je het aantal kruisende lijnen en de totale lengte van de lijnen minimaliseert.

Misschien een idee: neem voor het gemak aan dat een vakje een vaste grootte heeft en dat je een bepaald raster is waar je cellen kunt opvullen. Zo'n tekstvakje neemt bijvoorbeeld 8x4 cells in. Om een lijn te trekken kan je alleen over kanten in je raster lopen waarvan de omliggende cellen leeg zijn (of ook een lijn in zit).

Vervolgens kun je wel een zeer inefficiente beginoplossing maken die bestaat uit twee lege cellen tussen de vakjes en waarbij je de lijnen gewoon op een zo kort mogelijke manier (zonder door andere cellen te gaan) naar de andere vakjes trekt. Je kruist op deze manier vast een aantal andere lijnen.

Vervolgens ken je een score toe aan deze "oplossing". De score bestaat uit het aantal overlappende lijnen en iets als de totale afstand van de lijnen. Deze score ga je (min of meer) minimaliseren, bijvoorbeeld door random restart hillclimbing (mix even je beginoplossing door wat random permutaties van vakjes door elkaar en doe daarna een aantal stappen waarin je een vakje omwisseld of verplaatst net zolang er een mogelijkheid overblijft op je oplossing te verbeteren. Of iets als simulated annealing. Aan genetische algoritmen zou ik niet beginnen tenzij je een goede mutatie/crossover operator weet.

Vervolgens moet je het resultaat nog converteren naar html, maar dat lijkt me niet al te moeilijk (je raster lijkt tenslotte al op een tabel).

Nu lijkt me dit een vrij lastig probleem. Waarschijnlijk dat er eenvoudigere of efficientere technieken zijn, tenslotte komt dit in aardig wat applicaties voor. Je zou ook op zoek kunnen gaan naar een bibliotheek die zoiets doet.

[douweh]

Mm,

Ja dit was inderdaad het verschil tussen boom en graaf, misschien kan een moderator de titel veranderen?

Ik zal eens googlen ook op combinaties van graven en php!
bedankt iig