[es] - Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{23.11.2010. u 15:46 - pre 175 meseci}

Znate li gde mogu naci implementaciju algoritama za pronalazenje Ojlerove putanje ili ciklusa ili jos bolje neku gotovu aplikaciju sa source-om

><> <>< <><><><><><><> ><>

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{23.11.2010. u 15:56 - pre 175 meseci}

Ovde imaš algoritam za konstrukciju Ojlerovog puta. Nije ga teško implementirati.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{23.11.2010. u 15:58 - pre 175 meseci}

He he Wikipedia :)

Ima li nesto konkretnije?
Takodje ako znate neku C# bibilioteku za iscrtavanje grafova bilo bi lepo?

><> <>< <><><><><><><> ><>

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{23.11.2010. u 16:01 - pre 175 meseci}

Kako misliš konkretnije? Dat ti je kompletan algoritam.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{23.11.2010. u 16:03 - pre 175 meseci}

Pa recimo...

><> <>< <><><><><><><> ><>

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{24.11.2010. u 16:42 - pre 175 meseci}

Evo ti kompletnog programa u prilogu napisanog u jeziku C++. Treba da ga kompajliraš bilo kojim C++ kompajlerom.

Evo, kako se unosi graf:

5
0 1 1 0 0
0 1 1 1
0 1 1
0 1
0

znači da graf ima 5 čvorova numerisanih brojevima od 0 do 4, pri čemu je čvor 0 povezan samo sa čvorovima 1 i 2, a među čvorovima 1, 2, 3 i 4 svaki je povezan sa svakim, osim sa samim sobom.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Prikačeni fajlovi

euler.cpp - 4.83k

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{24.11.2010. u 21:55 - pre 175 meseci}

Uh havala nisam ovako nesto ocekivao, hvala puno!. Kompajlirao sam kod preko online kompajlera http://www.onlinecompiler.net/ i probao sam da unesem graf koj ste vi napisali i graf sa tri medjusobno povezana cvora preko matrice susedstva ali rezultati nisu tacni. Rezultati se nalaze u attachmentu.

Planiram da uradim i graficki interfejs u SIlverlight-u za ovaj algoritam, naravno ako budem koristio vas kod pisace i vase ime... :)

Evo neikih implementacija koje razmatram, mada sve mi deluju bezveze...
http://programmersforum.ru/showthread.php?t=8626
http://www.tuxv.net/2007/05/eulerian-path.html
http://en.pudn.com/downloads14...ows/other/detail629506_en.html
http://bytes.com/topic/c/answers/618742-euler-circuit

><> <>< <><><><><><><> ><>

Prikačeni fajlovi

graf.jpg - 40.44k

graf2.jpg - 18.67k

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{25.11.2010. u 09:56 - pre 175 meseci}

Nije ti unos dobar. Prvo, nule i jedinice se moraju odvajati razmakom. Drugo, u prvom redu imaš povezanost čvora 0 sa čvorovima od 0 do n-1, u drugom povezanost čvora 1 sa čvorovima od 1 do n-1. Unos dakle ima trugaoni, a ne kvadratni oblik. Kompletan graf reda 3 ima opis

3
0 1 1
0 1
0

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{25.11.2010. u 10:34 - pre 175 meseci}

Evo ispravljene verzije programa, s tim da važe iste napomene o unosu.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Prikačeni fajlovi

euler.cpp - 5.05k

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{25.11.2010. u 21:44 - pre 175 meseci}

Super! Sve radi...
Nemam sad puno vremena da proucim kod ali kad budem krenuo da radim aplikaciju, javicu se...

Puno pozdrava...

><> <>< <><><><><><><> ><>

Odgovor na temu

miki069

Član broj: 161528
Poruke: 2056
212.200.34.*

+391 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{25.11.2010. u 23:38 - pre 175 meseci}

@Nedeljko, Alexsis: Da li program, napisan po istom algoritmu, značajno brže radi ako je pisan u C++
u odnosu na Delphi? U čemu pisan radi najbrže?
Radi se o generisanju velikog broja prostih brojeva.
Ili generator velikog broja komninacija, varijacija, permutacija.
Dakle ogroman broj IF i WHILE DO naredbi.
Bitna mi je brzina izvršenja.
U određenim situacijama Delphi mi tek sutra da rešenje.
Delphi i VB znam i proverio sam da je program u Delphiju najmanje 5 puta brži,
nego program napisan u VB-u, bez ikakve modifikacije algoritma, na istom računaru.
C++ ne znam, ali učio bih ga ako je odgovor na prvo pitanje "DA i to najmanje toliko puta".

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 09:17 - pre 175 meseci}

C, C++ i Delphi su jezici čiji se iyvorni kod kompajlira u mašinski, a ne neki bajtkod koji se interpretira kao kod VB. Zato programi pisani po istim algoritmima rade brže u njima. Oni su po pitanju brzine međusobno ravnopravni.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3570

Jabber: djoka_l

+1527 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 09:58 - pre 175 meseci}

Samo da dopunim Nedeljka:

C++ i Delphi su, praktično, ravnopravni što se tiče brzine izvođenja, samo što je C++ ravnopravniji

Prosečan programer ne može da izvuče neku veliku prednost od pisanja u C++, ali je jezik bliži asembleru, pa majstori mogu da ga bolje doteraju da radi brže. Recimo, C++ kompajler može da iskompajlira 64-bitni kod, dok Delphi daje 32-bitni. Pametnim korišćenjem registry deklaracije može da se uštedi u tesnim petljama, ali je moguće da Delphi ipak da bolje optimizovan kod nego C++.

Ono što ti savetujem je da prvo dobro pogledaš svoj Delphi kod i vidiš da li nešto možeš bolje da uradiš nego da počeneš od nule da radiš u C++. Naravno, bilo bi dobro da ipak naučiš kasnije i C++ jer Delphi gubi svoje pozicije i nije neka investicija za budućnost...

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 10:43 - pre 175 meseci}

I ona verzija je bila bagovita. Evo, šaljem ispravku. Treća sreća.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Prikačeni fajlovi

euler.cpp - 5.26k

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 15:25 - pre 175 meseci}

He he hvala Nedeljko...

@miki069 Postoje metode za odredjivanje brzine izvrsavanja koda tj. algoritma preko kojih mogu da se uporede razliciti algoritmi tako da ako ti je to bitno (da uporedjujes algoritme) onda bi vise trebao time da se pozabavas ali ako samo gledas na brzinu izvrsavanja programa pisanog u razlicitim programskim jezicima onda stoji ovo sto ti djoka kaze.

Znaci ako je jezik blizi masinskom i ako je kod dobro optimizovan onda se i program brze izvrsava.

><> <>< <><><><><><><> ><>

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.teletrader.com.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 15:34 - pre 175 meseci}

Samo što je baš i ne vidim da je C++ bliži mašinskom kodu od Delphi-ja.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 15:45 - pre 175 meseci}

Pa dobro ne bukvalno da je blizi, nego da ima neke odlike masinskih jezika kao recimo pokazivaci, rad sa memorijom... sto iskusni programeri mogu da iskoriste i dosta ubrzaju program.

><> <>< <><><><><><><> ><>

Odgovor na temu

Cabo
Lokanje u bircuzu

Član broj: 10942
Poruke: 684
*.mi.sanu.ac.rs.

+5 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 16:40 - pre 175 meseci}

Citat:

Alexsis: Pa dobro ne bukvalno da je blizi, nego da ima neke odlike masinskih jezika kao recimo pokazivaci, rad sa memorijom... sto iskusni programeri mogu da iskoriste i dosta ubrzaju program.

LOL

Ni Delfi, ni C++ nemaju veze sa mašincem.

Asembler je blizu, ali ne preterano.

Delfi je nadgradnja Paskala, i kao takav takođe ima pokazivače. To što ih korisnik/programer (LOL @ korisnik...

) ne vidi baš često u „svakodnevnom“ kodu je druga priča.

Kliknite da vidite kako da pišete matematičke formule u [tex]TeX[/tex]-u bez slanja slika

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.mts.telekom.rs.

+2801 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{26.11.2010. u 19:39 - pre 175 meseci}

Ala si pametan... cccc

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Alexsis
Conspiritor
Nis/Aleksinac

Član broj: 30602
Poruke: 251
*.dynamic.isp.telekom.rs.

+1 Profil

Re: Ojlerov (Eulerian) graf- source code za pronalazenje putanje/ciklusa?

^{22.12.2010. u 21:37 - pre 174 meseci}

@Nedeljko
Ponovo pozdrav! :)

Krenuo sam da radim aplikaciju, medjutim posto aplikaciju radim u Silverlight-u ovaj kod je neupotrebljiv.

Imas li mozda c# verziju ovog programa ili jos bolje neku funkciju kojoj bi se prosledio graf recimo u obliku vektora a ona da vrati Ojlerov put (naravno ja bih vec nekako nasao nacina da taj vektor izgenerism preko korisnickog iterfejsa).

Ja sam pokusao da analiziram ovaj kod i da eventualno prepravim funkciju eulerPath(list<int> &path) da odgovara gore pomenutoj ali ocigledno nisam dovoljno strucan...

><> <>< <><><><><><><> ><>

Odgovor na temu