[alg]het weergeven van grafen

[brokenp]

Ik heb nu een delphi-programma dat werkt met tree's
dit delphi prog genereert deze tree's en beeld ze netjes af op het canvas

Nu is het mijn taak om een uitbreiding hierop te maken,
Ik moet het programma aanpassen zodat het ook grafen genereert en accepteerd

Het genereren van de ze grafen gaat goed.
Ik sla ze op als node's met verwijzingen naar node's ( dus niet met een matrix ofzo)
Ik moet nu nog het afbeelden van deze grafen naar het canvas.
Ik heb na zitten denken over de weergave, als ik het op basis van het algoritme doe dat reeds bestaat
dan houd ik zo'n plaatje over.

Ik gebruik maak dus gewoon een streep tussen de nieuwste knoop, en reeds bestaande(rode streep)
Ik vind het lelijk dat die lijn door andere knopen/lijnen heen loopt

Terwijl dit plaatje veel duidelijker dezelfde situatie weergeeft.


Ik zoek dus een algoritme die dit probleem redelijk oplost, dus dat er zo min mogelijk lijnen kruisen enzo.
Ik heb google/search gebruikt maar heb niets echt bruikbaars kunnen vinden.
Zijn er voor dit probleem standaard algoritmen, of moet ik hier zelf maar iets voor gaan bedenken.

[edit] ff links gefixt
ga nu ff zoeken op planaire grafen

[ Voor 8% gewijzigd door brokenp op 25-03-2003 19:38 ]

[Varienaja]

Je plaatjes doen het niet.

Je kunt alleen een graaf tekenen zonder kruisende lijnen als die graaf planair is. Ik weet niet zo exact meer hoe dat allemaal zat (en m'n grafentheorie diktaat ligt op een ander adres), maar ik geloof dat er wel een algoritme moet zijn om een planaire graaf netjes te tekenen. :-/ [sorry, je hebt eigenlijk niks aan deze post :+]

[Soultaker]

Misschien kun je eens kijk hoe Graphviz dat precies doet, of gewoon van deze library gebruik maken. Zoals Varienaja al zegt, is het onvermijdelijk dat je in sommige gevallen kruisende lijnen krijgt (tenzij je kunt garanderen dat je graaf planair blijft).

Uiteindelijk blijft het een kwestie van heuristiek en voorkeuren; er is geen "beste" manier om dit probleem op te lossen, denk ik, tenzij je graaf een specifieke vorm heeft, die beter weer te geven is dan met een generiek algoritme. (Ik denk daarbij bijvoorbeeld aan niet-cyclische graven, die meestal wat mooier weergegeven kunnen worden).

Ach, kijk nu eens wat ik zomaar op de Graphviz website vind:

A Technique for Drawing Directed Graphs:

We describe a four-pass algorithm for drawing directed graphs. The first pass finds an optimal rank assignment using a network simplex algorithm. The second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm makes good drawings and runs fast.

Erg interessant document, moet ik zeggen, maar wel enigzins ingewikkelde theorie.

[ Voor 52% gewijzigd door Soultaker op 25-03-2003 19:58 ]

[MSalters]

De C++ boost::graph library is misschien erg nuttig, en die kan GraphViz files lezen en schrijven.

[Sjnirk]

http://www.cs.kun.nl/~henk/fd.pdf Dit is het een deel van het dictaat wat ik moest leren over grafen, hier in staat ook precies uitgelegd wanneer ie planair is enzo

[xoror]

een plenaire graaf is een graaf die je kan inbedden op bijv een platte vlak.
Als je de inbedding maakt mogen de lijnen niet kruisen. jij zoekt minimaal kruisende lijnen (dus ook niet plenaire grafen).

er zijn een paar formules om snel te bepalen of een graaf plenair is of niet.

stel
n = aantal punten van een graaf
m = aantal lijnen van een graaf
f = aantal mazen van een graaf
(een maas is zeg maar een vlak gescheiden door lijnen van de graaf. er is ook altijd een buiten maas)

voor plenaire grafen gelden de volgende formules:
n - m + f = 2 (formule van euler)
m < 3n - 6

je kan met die formules dus snel nagaan of een graaf plenair is of niet
maar dan ben je er dus nog niet. (maw, je weet alleen of je hem kan tekenen
zonder kruisende lijnen of niet. Niet hoe je hem moet tekenen met minimaal aantal kruisende lijnen)

[ Voor 11% gewijzigd door xoror op 26-03-2003 16:42 ]

[Soultaker]

xoror schreef op 26 March 2003 @ 16:38:
f = aantal mazen van een graaf
(een maas is zeg maar een vlak gescheiden door lijnen van de graaf. er is ook altijd een buiten maas)

Dit getal bepalen is nog niet zo eenvoudig. Er is wel een algoritme voor, maar dat is verre van triviaal. Controleren of de graaf planair is, is dus ook niet simpelweg een kwestie van getalletjes optellen.

Los daarvan betwijfel ik de relevantie binnen dit topic, aangezien een graaf in het algemeen niet planair is (en niets van de informatie van de TS wijst erop dat deze graaf het zou zijn). Daarbij levert een bewijs van planairiteit nog geen methode voor de constructie van een tekening.

offtopic:
Planair != plenair!

[xoror]

Het is planair idd

maar ik zeg toch je kan alleen aantonen dat de graaf planair is. niet hoe je hem kan tekeken. Het is verder voor dit topic relevant dat je een test heb of een graaf al dan niet planair is. Wellicht heb je 2 algo's voor het tekenen. een voor planaire grafen en een voor niet planaire grafen. Omdat TS op onderzoek wilde gaan naar planariteit heb ik de betreffende info maar gegeven. (en dus ook laatste alinea dat hij er vrijwel niets aan heeft voor constructie van de tekening)

Daarnaast heb je met de 2e ongelijkheid geen mazen nodig.

[ Voor 21% gewijzigd door xoror op 26-03-2003 18:06 ]

[Anoniem: 91735]

Ik weet ik haal een oud topic uit de doos maar heb een vraag.
Enige tijd geleden ben ik hier ook mee bezig geweest en wild eik voor ene toepassing een plaatje tekenen met relaties met zo min mogelijk kruisende lijnen. Dat bleek wel mogelijk te zijn door gewoon alle combinaties te proberen. Echter bleek dat er heel erg veel (te veel) combinaties doorgerekend moesten gaan worden om uit eindelijk te bepalen wat de meest mooie opossing was.

Recent opzoek gegaan naar een activex-component voor het tekenen van een flowchart. Waarom zelf bouwen als ze er kant en klaar zijn dacht ik :-). Heb naar verschillende gekeken. Maar kom er niet 1 tegen waarbij je gewoon de entiteiten kan opgeven en vervolgens de relaties en die dan een plaatje tekent met zo weinig mogelijk kruisende lijnen. Dus die automatisch de entiteiten zelf herschikt.

Weet iemand of er een dergelijk activex-component is??? hoeft niet gratis te zijn.
Ik heb o.a. gekeken naar flowchartX van mindfusion. Deze biedt heel erg veel behalve dus dat ene probleem.

[Janoz]

Zo'n oud topic omhoogkicken voor een scriptrequest? (daar valt een component request inderdaad ook onder )

Liever niet...