Generator grafu – C / C++ – Fórum – Programujte.com

Zdravim!

shanim jakekoliv materialy tykajici se algoritmu pro generovani neorientovanych grafu na zaklade zadanych parametru (pocet uzlu/hran, atd...).

Zkousel jsem googlit, ale zatim bezvysledne :( Takze kdybyste nahodou o necem vedeli, byl bych vdecny za jakykoliv link nebo nazev nejake publikace. Jinak ty algoritmy samozrejme nemusi byt v C/C++ (prestoze je v tom budu implementovat), jde mi pouze o ty postupy a napady.

Diky, Honza

a muzes to trochu specifikovat? co ma ten algoritmus vlastne generovat, ma li pocet uzlu a hran? jde-li jen o to vyresit ktery vrchol jse spojen se kterym a jakou vahu ma ktera hrana, pak je to proste jen hazeni cisel.
pokud by si ovsem chtel aby ten graf byl rovinny pak to sranda neni...

je to zadani bakalarky, takze rozhodne to snadny neni :)

jde o tohle: obecny neorientovany graf ma radu parametru - jak jsem jiz rekl: pocet uzlu, hran, prumer, polomer, atd... A ted ja mam za ukol podle zadanych parametru vygenerovat co nejvetsi mnozstvi ruznych (neizomorfnich) grafu.
Takze napr. zadam, ze chci vsechny grafy se 117 uzly jejichz stupne jsou vetsi nez 5 a nemaji vice hran nez 40 (ted nevim jestli treba zrovna tohle nejni nesmysl - mozna ze zadny takovy graf neexistuje, ale to je jedno, proste jen pro ukazku).

No a na toto pry existuji ruzne algoritmy, ale nedari se mi je nikde najit. Mohl bych sice zacit vymyslet svuj vlastni, ale vedouci prace me od toho zrazuje, ze pry je to moc slozite :-)

pozn.: co je prumer a polomer grafu?

porad ale nevim jestli graf ma byt rovinny nebo ne, to je docela podstatne.
pokud nemusi byt, pak to neni tak tezke: vicemene jde jen o to aby jsi hlidal ma-li vrchol pocet hran odpovidajici jeho stupni, a nahodne bys je spojoval. pokud by jsi chtel zjistit jejich pocet, uloha take neni tezka, pocet hran odpovida sume stupnu vsech vrcholu/2.

pokud by graf byl rovinny, stalo by urcite za to nejprve vygenerovat jeho minimalni kostru a k te potom prikreslovat.
take jde o to jestli mas vygenerovat pouze nejake vahy hran a jejich napojeni nebo primo nejake rovinne vykresleni grafu

jinak na tohle je asi wikipeida kratka, neco by jsi mohl nalezt http://en.wikipedia.org/wiki/Spring_based_algorithm zde, ale to se venuje spise problematice vykresleni jiz vygenerovaneho grafu.
na toto tema bude asi lepsi odborna literatura, zajimava je napr. Grafy a jejich aplikace od Jiriho Demela, ale tam bohuzel take mnoho veci souvisejicich tesne s tvym problemem nenalezl. publikaci tema grafu existuje mnoho, ale nevim ktera by nejak vyrazne pomohla....

Neviem o co presne ide ale ako inspiraciu skus mrknut na RDDTool. Snad pomoze ako to vyzera v praxi. http://oss.oetiker.ch/rrdtool/ Ale z vecami ako neorientovane grafy , stromy atd.. ti to asi nepomoze :(

2 sn3d: tohle ale asi pracuje s grafama pro zobrazeni zavislosti a namerenych hodnot a tak, ne? Ja potrebuju Teorii grafu (tedy grafy uzel-hrana-uzel...).

2 tmi: moc uz si ty definice nepamatuju, ale prumer je pokud vim nejvetsi vzdalenost mezi dvema ruznymi uzly. Jinak nejsem si jistej , jestli to maji byt rovinne (planarni) grafy nebo ne, a nejsem si jistej jestli na tom zalezi. Nevim jestli ty grafy budu vykreslovat, mozna postaci vzdycky graf v podobe tabulky incidence, nebo tak neco.

Kazdopadne diky za ty linky.

zistujem.. cital som nezmysel :D

jestli by stacila tabulka incidence pro obecny graf tak lze ulohu resit treba takto:
pro zadany pocet stupnu vsech vrcholu grafu a pocet hran nejprve vygenerujes grafy nahodnym rozdelenim incidenci, nemusis hlidat vubec nic (pokud nechces aby graf byl souvisly) (na zacatku zkontrolujes jeslti ma uloha reseni, tedy jestli suma vsech stupnu odpovida polovine poctu hran). pokud je zadan i prumer (tak jak jsi mi ho popsal), muzes se o ulohu postarat tim ze vsem hranam pridelis jednotkove vahy, a zvolis si jeden vrchol (idealne prvniho stupne), ze ktereho si najdes dijkstrou nejdelsi moznou cestu (staci ho mirne upravit) do nejakeho vrcholu (pokud ma graf vice komponent je treba si take dat pozor, nejsnaze asi tak ze dijkstru spustis ve vsech komponentach a z nich vyberes takovou kde ta cesta byla nejdelsi). pote zvolis hranu ktera vychazi z onoho na pocatku zvoleneho vrcholu a zaroven lezi na nalezene nejdelsi ceste a nastavis ji na takovou delku aby ta nejdelsi nalezena cesta mela hodnotu prumeru.

jednotlive grafy generujes tak ze postupne kazde hrane pridelis dva nesparovane vrcholy, a po kazdem vygenerovanem grafu nejake dve hrany permutujes. jestli chces vygenerovat vsechny takove grafy vybiras vsechny ruzne kombinace dvojic vrcholu,
takze ((m) nad (2)) * ((m-2) nad (2)) * ... tedy v nejhorsim pripade (m!)/(2 na (n+1)) {aspon myslim)}...

nevim jak moc jsem ti timto pomoh, protoze je to dost obecne a jen na hrubo pracujici reseni...
pozn: to je bakalarka? docela dobry tema... na jaky jsi skole?

jj, tohle co jsi napsal je urcity nastin reseni, takze nejak takhle bych zacal uvazovat, kdybych se pustil do implementace vlastniho algoritmu (mozna, ze nic jineho mi nezbude). Cilem te prace ale taky je prave sesbirat existujici algoritmy na generovani grafu, implementovat je a treba porovnat efektivnost a slozitost. Proto jsem tento thread zacal dotazem na pripadne odkazy ci knihy.

Nicmene, vymyslet vlastni bezvadne pracujici algoritmus a implementovat ho v GUI s nejakym vykreslovanim tech grafu treba, by mozna na samostatnou bakalarku stacilo :) Kouzlo te aplikace by bylo proste v tom, ze bych si mohl nastavit jakoukoliv kombinaci grafovych parametru (dalo by se jich pouzit tak 8) a pote vygenerovat vsechny nebo alespon co nejvice (na tom by prave zalezela kvalita toho algoritmu) prislusnych grafu.

P.S.: Vypocetni technika na FEL CVUT

nesnasim implementace algorimtu s GUI)). resit vykreslovani tim ze si jich par peknejch vyberes je sikovne opatreni, trochu mi to pripomina nejake operace provadene prekladacima strojema (mas prelozit nejakou mnozinu na jinou, tak se proste rozhodnes ze pulku ty prvni neakceptujes protoze se ti nelibi))).
co se tyce literatury asi doporucuju zajit do nejakeho specializovaneho knihkupectvi typu Matfyzpress nebo Carolinum (pripadne jeste Academia nebo Luxor) a tam se optat, ale rekl bych ze dost z tech knih na sklade mit nebudou (aspon ja jsem jich v regalech skutecne mnoho nevidal...)

P.S: a jake jsou tvoje prozatimni dojmy na skolu? pripada mi ze je FEL trochu moc zamerena na elektrotechniku a fyzkiku, muze se tomu vsemu clovek vyhnout kdyz chce predevsim programovat?

Re:P.S.: bohuzel FEL je fakulta elektrotechnicka, takze s elektrotechnikou se tam setkas :) Ne, tak elektrotechnika je hrozne sirokej pojem, ktery vlastne obsahuje i to programovani. Do nedavna to bylo tak, ze prvni rocnik meli vsichni studenti stejny a teprve od druhaku se rozrazovali do oboru (m.j. vypocetni technika). Takze kazdy musel projit v prvaku fyzikou, matematikama, nejakou tou chemii, apod. Ted tusim pred rokem se vypsal novy studijni obor, ktery je hned od prvaku zameren pouze a jen na IT predmety, a dokonce uz nejakou dobu koluji hlasky, ze katedra pocitacu chce zalozit vlastni fakultu v ramci CVUT, ale to moc nadejne nevidim...

nekde na netu sem videl bakalarku s podobnym tematem, zkus si to vygooglit

Jen par poznamek k tomu, co se tu pise:

1) jakpak se da Dijkstrovym algoritmem hledat NEJDELSI cesta? Tvrdim, ze jakakoli modifikace Dijkstry bud nebude hledat nejdelsi cestu nebo bude spatne :-).
PS: kdyby se umela nejdelsi cesta (nikoli sled) v grafu hledat jakymkoli rozumnym zpusobem, asi by pak nebyl problem odpovedet, zda graf obsahuje Hamiltonovskou cestu (tj. cestu prochazejici vsemi vrcholy) a to je notoricky znamy NP-uplny problem (lze s vcelku velkou pravdepodobnosti prelozit jako algoritmicky slozity problem).

2) prumerem grafu byva oznacovana nejdelsi z nejkratsich cest mezi libovolnymi dvema vrcholy; polomerem se oznacuje:
pro kazdy vrchol si vezmeme nejdelsi z nejkratsich cest do ostatnich vrcholu a z nich vezmeme tu nejkratsi :-), neboli min_v {max_u {d(u,v}} kde min_v znaci minimum pres vsechny vrcholy v grafu, max_u maximum pres vsechny vrcholy u a d(u,v) je delka nejkratsi cesty mezi u a v.

3) jestli ty grafy maji byt navzajem neizomorfni, tak ten napad s permutovanim je dle meho nazoru dost mimo (nejak jsem nemel silu premyslet nad tim, jak presne mel fungovat, ale obecne si myslim, ze zkouset libovolne umistovat hrany izomorfismu nezabranuje).

4) myslim si, ze at uz je graf rovinny nebo neni, rozhodne to neni snadne ... A pokud nerovinnost grafu ulohu nejak usnadnuje, pak by me vazne zajimalo jak :-).

1-jo mas pravdu, nevim co sem tim tehdy myslel. ale pokud by se to vygenerovalo bez cyklu tak by to slo:)
2-diky za info
3-asi sem si uz prestal uvazovat podminku neizomorfnosti, ale myslim ze obecne by se presmerovavani hran pouzit daly, treba tak ze by se menily stupne vrcholu - coz uz pokud se nemylim uz izomorfnost porusuje
4-poznas v konstantnim case zdali je graf rovinny? pokud ne tak to nerovinnost vzdy usnadnuje).
... nevim jestli moje nazory nejsou zcestne protoze jsme to resili celkem davno a ja nemam zaludek to znovu cist