[es] - Balansiranje stabla

DeYo
Dejan Vukmirovic
developer @ Mogul
Pozarevac/Bgd/Stockholm

Član broj: 36771
Poruke: 85
*.dynamic.sbb.co.yu.

Sajt: www.linkedin.com/in/dejan..

Profil

Balansiranje stabla

^{03.06.2007. u 11:57 - pre 205 meseci}

Iz baze dohvatam grupu entiteta i kreiram stablo koje prikazuje njihovu medjusobnu povezanost.
Primer rezultujuceg stabla bi trebalo da bude nesto ovako:

Medjutim, problem je sto ne mogu da dodjem do algoritma koji bi vrsio balansiranje stabla, vec ono sto sam trenutno uspeo da postignem je ovo (u odnosu na primer sa gornje slike):

Od podataka sa kojima raspolazem, tj. koje sam sracunao, imam:
- za svaki entitet tj. cvor vertikalni nivo (gde je vrednost najveceg, pri vrhu, jednaka 0), horizontalni index (redom kako su dohvatani iz baze, s leva na desno)
- veze izmedju cvorova, u formatu [startni, krajnji]
- krajnja gornja-leva koordinata [x,y] u odnosu na koju bi pocelo pozicioniranje svih cvorova

Dakle, treba mi algoritam pomocu kojeg bi sracunao koordinate za svaki od cvorova tako da stablo ima koliko-toliko izbalansiran izgled. Pretpostavljam da bi se mogle koristiti nekakve tezisne funkcije, ali racunam da je bolje da me neko prvo uputi pre nego sto krenem sam da izmisljam nesto sto vec postoji.

Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
*.sksyu.net.

+171 Profil

Re: Balansiranje stabla

^{03.06.2007. u 14:33 - pre 205 meseci}

Izvini ali koja je razlika izmedju prve i druge slike? Koliko ja vidim identicne su, samo sto je jedna iskosena a druga ne

Inace zbog onog jednog node-a koji ima dva parenta mislim da ne moze da se zove stablo, nego graph.

Za .NET mozes pogledati sledeci link
http://msdn2.microsoft.com/en-us/library/aa289152(VS.71).aspx

Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
*.sksyu.net.

+171 Profil

Re: Balansiranje stabla

^{03.06.2007. u 15:09 - pre 205 meseci}

Uf, sad vidim sta zelis - ti zelis balanisrano da ih nacrtas, posto kada si spomenuo balansiranje stabla prva asocijacija mi je bila balansiranje nodova a ne crtanje

Inace mislim da neko univerzalno resenje ne postoji za grpah-ove, mislim moze da se namesti ali uvek moze drukcije, dok da je u pitanju tree onda bi mozda moga da resis preko visine drveta, mada sada kada pogledam ovo tvoje 'stablo' mogao bi mozda i preko visine da nacrtas.

Odgovor na temu

DeYo
Dejan Vukmirovic
developer @ Mogul
Pozarevac/Bgd/Stockholm

Član broj: 36771
Poruke: 85
*.dynamic.sbb.co.yu.

Sajt: www.linkedin.com/in/dejan..

Profil

Re: Balansiranje stabla

^{03.06.2007. u 15:28 - pre 205 meseci}

Citat:

negyxo: Uf, sad vidim sta zelis - ti zelis balanisrano da ih nacrtas, posto kada si spomenuo balansiranje stabla prva asocijacija mi je bila balansiranje nodova a ne crtanje :)

Sad kad i ja razmislim naslov teme bas i ne odgovara onome sto sam hteo da pitam.

Citat:

negyxo:Inace mislim da neko univerzalno resenje ne postoji za grpah-ove, mislim moze da se namesti ali uvek moze drukcije, dok da je u pitanju tree onda bi mozda moga da resis preko visine drveta, mada sada kada pogledam ovo tvoje 'stablo' mogao bi mozda i preko visine da nacrtas.

Mislio sam da krenem od "nivoa" u kojem ima najvise cvorova pa navise i nanize da nadovezujem, ali nikako to da isteram do kraja.

Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
*.sksyu.net.

+171 Profil

Re: Balansiranje stabla

^{03.06.2007. u 16:38 - pre 205 meseci}

Pa da bi pronasao koji nivo ima najvise nodove-a i nje tesko napisati algoritam. Mogao bi da nadjes algoritam za traversing kroz k-array tree i njega da iskoristis.

http://en.wikipedia.org/wiki/Tree_traversal

Odgovor na temu

bkaradzic
Branimir Karadžić
ArenaNet
Seattle, WA

Član broj: 14953
Poruke: 1630
67.151.201.*

Sajt: https://github.com/bkarad..

+11 Profil

Re: Balansiranje stabla

^{04.06.2007. u 21:25 - pre 205 meseci}

Probaj:
http://www.graphviz.org/

https://github.com/bkaradzic/bgfx

Odgovor na temu

DeYo
Dejan Vukmirovic
developer @ Mogul
Pozarevac/Bgd/Stockholm

Član broj: 36771
Poruke: 85
*.dynamic.sbb.co.yu.

Sajt: www.linkedin.com/in/dejan..

Profil

Re: Balansiranje stabla

^{07.06.2007. u 13:55 - pre 205 meseci}

Citat:

bkaradzic: Probaj:
http://www.graphviz.org/

Ovo deluje odlicno. Hvala. Ali aplikacija koju resavam je u Javi i koliko sam video na sajtu razvoj paketa za Javu je prekinut jos za verziju 1.2, uz dodatne komentare da su imali mnogo problema sa integrisanjem tog paketa u aplete. Da koristim Graphviz kao posebnu aplikaciju ne mogu jer sam uslovljen time da citavo resenje mora da bude unutar jedne aplikacije.

Elem, kreirao sam svoj algoritam kojim sam prihvatljivo resio problem.

U grubim koracima:
- locira se nivo koji ima max broj cvorova, u tom nivou cvorovi se "rasire" na parna mesta [0,2,4...] nazovimo indexe
- krece se "na dole" za svaki od cvorova iz nivoa kroz koji se prolazi radim sledece:
* na osnovu relacija iz grana pronalazim sve "roditelje", pamtim max i min indexe roditelja
* poziciju tj. index cvora sracunavama kao (max+min)/2
* ukoliko je sracunati index vec zauzet od strane drugog cvora, uvecavam index za 1 sve dok ne pronadjem prazno mesto (evidencija praznih mesta je u matrici - Vector x Hashtable)
- analaogno za "na gore"

Naravno, sama implementacija u Javi nije bas tako prosta. Kao sto pretpostavljam da ne bi bila ni u drugim jezicima.

_{[Ovu poruku je menjao DeYo dana 07.06.2007. u 15:23 GMT+1]}

Odgovor na temu