__author__= 'Melita Mihaljevic' __date__= '2007' import sys import math class Graph : def __init__(self): """inicijalizacija grafa""" self.vrhovi = [] #lista vrhova u grafu self.bridovi = {} #dictionary bridova u grafu(zapisuje se brid i tezina, ukoliko nije zadana zapisuje se 1 self.lista_susjedstva ={} #dictionary koji sadrzi listu susjedstva self.brid_susjedi=[] #ucitava graf na jedan od mogucih nacina koji je zadan kao parametar, te se na taj nacin igra s vrhovima, za pocetak je zadana u datoteci, poslje samo taj dio promijenim i cijeli labos ce mi raditi kako spada. def ucitaj_graf(self,tip,ime_datoteke): self.nacin= tip self.ime_datoteke=ime_datoteke if self.nacin == "datoteka": f= open(self.ime_datoteke,'r') for line in f: line.strip() line = line[:len(line)-1] self.daj_vrh= line.split("#")[0] vrh1= self.daj_vrh.split(",")[0] vrh2= self.daj_vrh.split(",")[1] if vrh1 not in self.vrhovi: self.vrhovi.append(vrh1) if vrh2 not in self.vrhovi: self.vrhovi.append(vrh2) print line.split("#")[1] if line.split("#")[1]: # postoji tezina i treba ju zapisati self.tezina= line.split("#")[1] else: self.tezina= 1 self.bridovi[self.daj_vrh]=[] self.bridovi[self.daj_vrh].append(self.tezina) else: print('ostali nacini nisu jos implementriani') print self.vrhovi print self.bridovi #dodaje zadani brid grafu na temelju dva vrha i tezine brida: def dodaj_brid(self,vrh1,vrh2,weight): tezina= weight string= str(vrh1)+","+str(vrh2) self.bridovi[string]=[] self.bridovi[string].append(tezina) if vrh1 not in self.vrhovi: self.vrhovi.append(vrh1) if vrh2 not in self.vrhovi: self.vrhovi.append(vrh2) #vraca listu vrhova u zadanom grafu: def pvrhovi(self): return self.vrhovi[:] #vraca popis bridova u zadanom grafu u obliku 'brid':tezina def pbridovi(self): return self.bridovi # vraca tezinu brida: def get_weight(self,vrh1,vrh2): string1= str(vrh1)+","+ str(vrh2) string2= str(vrh2)+","+str(vrh1) if string1 in self.bridovi: return int(self.bridovi[string1][0]) if string2 in self.bridovi: return int(self.bridovi[string2][0]) #vraca vrhove koji pripadaju pojedinom bridu: def pripada_bridu(self): self.pripada={} for string in self.bridovi: vrh1=string.split(",")[0] vrh2=string.split(",")[1] self.pripada[string]=[] self.pripada[string].append(vrh1) self.pripada[string].append(vrh2) #vraca listu susjedstva iz osnovnog oblika zadanog grafa def plista_susjedstva(self): for string in self.bridovi.keys(): vrh1= string.split(",")[0] vrh2= string.split(",")[1] if vrh1 not in self.lista_susjedstva.keys(): self.lista_susjedstva[vrh1]=[] if vrh2 not in self.lista_susjedstva[vrh1]: self.lista_susjedstva[vrh1].append(vrh2) else: pass if vrh2 not in self.lista_susjedstva.keys(): self.lista_susjedstva[vrh2]=[] if vrh1 not in self.lista_susjedstva[vrh2]: self.lista_susjedstva[vrh2].append(vrh1) else: pass return self.lista_susjedstva #vraca stupanj vrha u grafu: def stupanj(self, vrh): return(len(self.lista_susjedstva[vrh])) #provjerava jesu li dva vrha susjedi: def is_susjed(self,vrh1,vrh2): for smtn in self.bridovi: tmpvrh1= smtn.split(",")[0] tmpvrh2= smtn.split(",")[1] if tmpvrh1==vrh1 and tmpvrh2==vrh2: return 1 elif tmpvrh1==vrh2 and tmpvrh2==vrh1: return 1 else: pass return 0 #mice iz liste ukoliko su obrisani vrhovi ili bridovi u grafu: def makni_iz_liste(self): for vrh in self.lista_susjedstva.keys(): if vrh not in self.vrhovi: del self.lista_susjedstva[vrh] for vrh in self.lista_susjedstva.keys(): for vrh1 in self.lista_susjedstva[vrh]: if self.is_susjed(vrh,vrh1): pass else: self.lista_susjedstva[vrh].remove(vrh1) return self.lista_susjedstva #vraca matricu susjedstva iz osnovnog oblika zadanog grafa def pmatrica_susjedstva(self): #inicijalizacija matrice susjedstva- matrica nxn koji na pocetku popunjava nulama: self.matrica_susjedstva = [[0]*len(self.vrhovi)for i in range(len(self.vrhovi))] counter1 = 0 counter2 =0 for vrh1 in self.vrhovi: counter1 =counter1+1 for vrh2 in self.vrhovi: counter2 = counter2+1 if self.is_susjed(vrh1,vrh2): self.matrica_susjedstva[counter1-1][counter2-1]=1 else: pass counter2=0 return self.matrica_susjedstva #vraca matricu incidencije def pmatrica_incidencije(self): #inicijalizacija matrice incidencije: self.matrica_incidencije=[[0]*len(self.bridovi)for i in range(len(self.vrhovi))] counter=0 x=self.pripada_bridu() for string in self.bridovi: counter=counter+1 for vrh in self.vrhovi: if vrh in self.pripada[string]: self.matrica_incidencije[self.vrhovi.index(vrh)][counter-1]=1 return self.matrica_incidencije #nakon nekih operacija nad grafom tipa brisanja brida ili vrha vraca osvjezene zapise grafova def update(self): mi=self.pmatrica_incidencije() ms=self.pmatrica_susjedstva() ls= self.makni_iz_liste() #vraca graf bez vrha- potrebno je obrisati vrh i sve brdove incidentne s njim def obrisi_vrh(self,vrh): incidentni = self.pripada_bridu() obrisi=[] for x in self.pripada: if vrh in self.pripada[x]: obrisi.append(x) del self.bridovi[x] del self.vrhovi[self.vrhovi.index(vrh)] for x in obrisi: del self.pripada[x] x= self.update() #vraca graf bez brida G-e -> samo pobrisem brid, a vrhovi ostaju, uvijek dobijem podgraf def obrisi_brid(self,brid): if brid not in self.bridovi: vrh= brid.split(",")[0] vrh1= brid.split(",")[1] brid = vrh1+ "," +vrh del self.bridovi[brid] x= self.update() return self.bridovi #vraca kopiju zadanog grafa- kopije vrhova i bridova, sad moram vidjeti jos da li treba i kopija liste i matrica def coppy_graph(self): self.coppy_vrhovi=[] self.coppy_vrhovi =self.pvrhovi() self.coppy_bridovi={} self.copp_bridovi= self.pbridovi() #*******************primjeri grafova************************ class Primjer: def __init__(self): """Primjeri grafova """ #vraca potpuni graf-svi vrhovi susjedni. Potrebno je zadati broj vrhova: def get_potpuni(self,broj_vrhova): graf= Graph() self.foo=graf if broj_vrhova == 0: print'nul graf' if broj_vrhova < 0 : print'krivo zadani vrhovi' exit (0) for i in range(broj_vrhova): graf.vrhovi.append(str(i)) for i in range(broj_vrhova): for j in range(1,broj_vrhova): if i KOCKA NIJE IMPLEMENTIRANA def get_kocka(self,n): graf= Graph() #*************U zadanom jednostavnom grafu nalazi najkracu i najdulju zatvorenu stazu******************* class Povezanost(Graph,Primjer): def __init__(self): """povezanost """ #za zadani jednostavni graf pronalazi najkracu zatvorenu stazu: def najkraca_staza(self): primjer= Primjer() primjer.get_kotac(7) put =[] tmp_put=[] lista=[] stog=[] mini= len(primjer.foo.vrhovi) for vrh in primjer.foo.vrhovi: counter = 1 #za svaki vrh inicijaliziram pocetno stanje ciklus = vrh #s kojim vrhom treba zavrsiti ciklus trenutni_vrh=vrh prethodni_vrh=vrh tmp_put.append(vrh) #zapisuje put kojim prolazim graf for vrh1 in primjer.foo.lista_susjedstva[vrh]: #za svakog susjeda trenutnog vrha stog.append(vrh1) #dodaj ga na stog jer sve treba stog.reverse() #ispitati while stog: trenutni_vrh = stog.pop() #dok ima sta za skidat tmp_put.append(trenutni_vrh) #zapisi put counter =counter +1 #povecaj brojac lista[:]= primjer.foo.lista_susjedstva[trenutni_vrh] #pogledaj susjede trenutnog vrha lista.reverse() for smtn in lista: #za svaki vrh koji je susjed if smtn == ciklus and mini > counter and smtn != prethodni_vrh: # provjerim da li je zatvoren ciklus i da jos ne postoji minimalna zatvorena staza mini = counter counter = counter-1 del put[:] put[:]=tmp_put put.append(ciklus) tmp_put.pop() trenutni_vrh = tmp_put[len(tmp_put)-1: ] prethodni_vrh= tmp_put[len(tmp_put)-2:len(tmp_put)-1] break elif smtn == prethodni_vrh: pass elif counter >= mini : #tu isto moram pobrisati ono dokle sam dosla, a ne samo izaci jer mi se onda tu povecava counter counter = counter-1 tmp_put.pop() trenutni_vrh=tmp_put[len(tmp_put)-1:] break else: stog.append(smtn) del lista[:] prethodni_vrh = trenutni_vrh del stog[:] del tmp_put[:] print 'put',put print 'mini',mini def is_most(self,vrh1,vrh2): tmp=1 for x in self.booll[vrh1]: if x in self.booll[vrh2]:#ako imaju jos jednog zajednickog susjeda onda nisu most tmp=0 return tmp #provjerava je li zadani graf Elulerovski - postoji zatvorena staza koja sadrzi svaki brid od G: def is_euler(self): print 'blah' for x in self.booll.keys(): print len(self.booll[x]) print x if len(self.booll[x])% 2: print 'nije' return 0 else: print 'je' return 1 #po FLEURYEVOM algoritmu pronalazi eulerovsku stazu: def pronadji_eulerovsku_stazu(self): put= [] counter=0 vrh = self.primjer.foo.vrhovi[0] print 'vrhovi',self.primjer.foo.vrhovi,vrh ciklus= vrh trenutni_vrh ='x' put.append(vrh) #zapisujem vrh odakle sam krenula while len(self.primjer.foo.vrhovi)!= 1: #dok se ne podudaraju trenutni vrh i vrh koji oznacava da je zatvoren ciklus: for x in self.primjer.foo.lista_susjedstva[vrh]: print 'jsjd',vrh, counter, len(self.primjer.foo.lista_susjedstva[vrh]) if self.is_most(vrh,x) == 0: prethodni_vrh = vrh vrh =x break else: counter = counter +1 if counter == (len(self.primjer.foo.lista_susjedstva[vrh])): prethodni_vrh = vrh vrh = x put.append(x) counter=0 if prethodni_vrh> vrh: string = str(vrh)+","+str(prethodni_vrh) else: string = str(prethodni_vrh)+","+ str(vrh) self.primjer.foo.obrisi_brid(string) if not self.primjer.foo.lista_susjedstva[prethodni_vrh]: self.primjer.foo.obrisi_vrh(prethodni_vrh) print'put', put, prethodni_vrh return put #za zadani jednostavno graf oduzimanjem bridova dobiva se eulerovski graf: def get_eulerian_graph(self): vrh = self.primjer.foo.vrhovi[0] #kreni od prvog vrha print 'vrh',vrh x= 0 while x != 1: if len(self.primjer.foo.lista_susjedstva[vrh])%2 !=0: #dok nije paran stupanj vrha vrh1 = self.primjer.foo.lista_susjedstva[vrh][0] #uzmi prvi vrh i obrisi taj brid print 'vrh1' ,vrh1 if vrh1 > vrh: string = vrh+","+ vrh1 else: string = vrh1+"," +vrh print'string', string self.primjer.foo.obrisi_brid(string) #obrisi brid koji smeta do eulerovosti vrh = vrh1 print'vrh1', vrh1 if self.is_euler(): print'eulerovski' x=1 else: #zadani vrh je ok pa nadji onog koji nije ok : for vrh1 in self.primjer.foo.vrhovi: if len(self.primjer.foo.lista_susjedstva[vrh1])%2 ==0: pass else: vrh= vrh1 novi_vrhovi=[] for brid in self.primjer.foo.bridovi: vrh1 = brid.split(',')[0] vrh2 = brid.split(',')[1] if vrh1 not in novi_vrhovi: novi_vrhovi.append(vrh1) if vrh2 not in novi_vrhovi: novi_vrhovi.append(vrh2) self.primjer.foo.vrhovi[:]= novi_vrhovi #za zadani jednostavni graf pronalazi najdulju zatvorenu stazu:-paziti jer najdulja staza ne ide preko bridova vise.hm.. mozd mogu koristit obrisi brid :) def najdulja_staza(self): self.primjer = Primjer() self.primjer.get_Petterson() put=[] tmp_put=[] lista= [] stog= [] max = 0 ok = [] tmp_susjedi={} self.booll= self.primjer.foo.lista_susjedstva if self.is_euler(): #ako je graf eulerovski onda je max staza jednaka broju bridova max = len(self.primjer.foo.bridovi) print 'max',max eulerovska_staza = self.pronadji_eulerovsku_stazu() print eulerovska_staza else: self.get_eulerian_graph() print'bridovi', self.primjer.foo.bridovi max = len(self.primjer.foo.bridovi) print'max',max eulerovska_staza= self.pronadji_eulerovsku_stazu() print eulerovska_staza #************************DIJKSTRIN ALGORITAM************************************** #klasa koja implementira djikstrin algoritam - ucitavam tezinske grafove class Dijkstra: def __init__(self): """Dijkstrin algoritam """ #vraca listu G- lista susjedstva sa zadanim tezinama: def get_G(self): self.graf = Graph() self.graf.ucitaj_graf("datoteka","dijkstra") self.graf.plista_susjedstva() self.vrhovi = self.graf.pvrhovi() self.bridovi= self.graf.pbridovi() self.G={} for vrh in self.graf.vrhovi: self.G[vrh]={} for vrh1 in self.graf.lista_susjedstva[vrh]: tezina = self.graf.get_weight(vrh,vrh1) self.G[vrh][vrh1]=tezina return self.G #implementacija dijkstrinog algoritma: def get_dijkstra(self,start='0',end=None): G = self.get_G() infinity= sys.maxint # inicijalizacija : distances ={} previous ={} for v1 in self.vrhovi: for v2 in self.vrhovi: if not self.graf.is_susjed(v1,v2): if v1 != v2: self.graf.dodaj_brid(v1,v2,infinity) distances[v1]= infinity previous[v1]= None distances[start]= 0 vertices = self.graf.pvrhovi() while vertices: minimal = vertices[0] for vertex in vertices: if distances[vertex]< distances[minimal]: minimal= vertex del vertices[vertices.index(minimal)] for v in self.graf.vrhovi: if self.graf.is_susjed(minimal,v): if distances[v]> distances[minimal]+ self.graf.get_weight(minimal,v): distances[v]= distances[minimal]+ self.graf.get_weight(minimal,v) previous[v]=minimal if not end: end = max(self.graf.vrhovi) path =[end] t = previous[end] while t: path.insert(0,t) t = previous[t] print distances[end],path return 0 #**********************TRGOVACKI PUTNIK ************************************** class Salesman: def __init__(self): """usporedba heuristickog algoritma i iscrpne pretrage""" #implementacija iscrpne pretrage za rjesavanje TSP def fact(x): if x == 0: return 1 return x * fact(x-1) def iscrpna_pretraga(self): lista_vrhova= [] lista_vrhova = self.graf.pvrhovi() lista_prijedjenih= [] duljina_puta = 0 odabir =[] # svi putovi od kojih odaberem najpogodniji (put ,duljina) put = [] #zapis (0,1),(1,2)... broj_slucajeva = fact(len(lista_vrhova)-1)/2 # broj slucajeva koje moram ispitati i ali ne moram ispitati svaki ukoliko vidim da neki ne vodi nigdje :) #implementacija heuristickog algoritma za rjesavanje TSP def heuristicki(self): print "globalna pohlepa" #usporedba 2 algoritma: # def usporedi(self): #************************************STABLA*************************************** class Stabla: def __init__(self): """implementira algoritme za prebrajanje razapinjujucih i u tezinskom grafu pronalazi min """ #ispisuje bilo koje razapinjujuce stablo: def ispisi_razapinjujuce_stablo(self): self.primjer= Primjer() self.primjer.get_potpuni(7) vrhovi_stabla=[] def oznaci_vrh(k): visited[k]= True for i in self.var.foo.vrhovi: if self.primjer.primjer.is_susjed(i,k) and not visited[i]: vrhovi_stabla.append((k,i)) oznaci_vrh(i) visited ={} for vrh in self.primjer.foo.vrhovi: visited[vrh]= False for vrh in self.primjer.foo.vrhovi: if not visited[vrh]: oznaci_vrh(vrh) print vrhovi_stabla #po kirchofovu teoremu izracunava broj razapinjujucih stabala: def kirchoff(self): self.var= Primjer() self.var.get_potpuni(7) self.Q= [[0]*len(self.var.foo.vrhovi)for i in range(len(self.var.foo.vrhovi))] for i in range(len(self.var.foo.vrhovi)): for j in range(len(self.var.foo.vrhovi)): if i== j: self.Q[i][j]= len(self.var.foo.lista_susjedstva[str(i)]) elif str(i) in self.var.foo.lista_susjedstva[str(j)]: self.Q[i][j]= -1 else: self.Q[i][j]= 0 del self.Q[0] for i in range(len(self.var.foo.vrhovi)-1): del self.Q[i][0] print self.Q # sad od ovog moram si determinantu izracunati :) i to je broj razapinjujucih stabala #vraca razapinjuce stablo min duljine po kruskalovom algoritmu : # moram prvo dodati da mi ukoliko bi zatvorio ciklus onda brisem taj brid, tj nije dostupan taj brid sam moram vidjeti kako ce mi ispitivati za ciklus def postoji_zajednicki_brid(self,brid1,brid2): vrh11 = brid1.split(",")[0] vrh12 = brid1.split(",")[1] vrh21 = brid2.split(",")[0] vrh22 = brid2.split(",")[1] #kada nadjem zajednicki brid moram provjeriti cini li on ciklus: if self.graf.is_susjed(vrh11,vrh21): x= vrh11 +","+vrh21 elif self.graf.is_susjed(vrh11,vrh22): x= vrh11+","+vrh22 elif self.graf.is_susjed(vrh12,vrh21): x= vrh12+","+vrh21 elif self.graf.is_susjed(vrh12,vrh22): x= vrh12+","+vrh22 else: x= 0 return x #ukoliko postoji mogucnost da brid cini ciklus sa vec obidjenim bridovima, pronalazi ga, i takav brid treba obrisati def pronadji_ciklus(self,brid): tmp_put= [] tmp_vrh=[] moguci_put=[] ciklus = brid.split(",")[0] #svejedno je od kojeg vrha krecem ako zelim zatvoriti ciklus trenutni_vrh = brid.split(",")[1] prethodni_vrh = ciklus tmp_vrh.append(trenutni_vrh) counter = 0 mogucnosti = [] while 1: for vrh in self.pomocna_lista[trenutni_vrh]: if vrh == prethodni_vrh: #preskoci prethodni vrh continue if vrh == ciklus: #ako je ciklus vrati da je i obrisi brid return 1 moguci_brid1 = vrh +","+trenutni_vrh moguci_brid2 = trenutni_vrh +","+vrh if moguci_brid1 in self.put or moguci_brid2 in self.put: mogucnosti.append(vrh) #radi mi kao stog stavim sve mogucnosti counter = counter +1 #tu moram dodati da jos obrise dok imam else: continue if counter == 0: del mogucnosti[:] return 0 prethodni_vrh= trenutni_vrh trenutni_vrh = mogucnosti.pop() tmp_vrh.append(trenutni_vrh) counter = 0 sys.exit(0) #ukoliko je pronadjen brid koji bi sa prijedjenima cinio ciklus, obrisi ga def obrisi_brid_ciklus(self): for brid1 in self.put: for brid2 in self.put: if brid1 != brid2: x = self.postoji_zajednicki_brid(brid1,brid2) if x: m=self.pronadji_ciklus(x) if m : self.graf.obrisi_brid(x) #implementacija kruskalovog algoritma za pronalazak razapinjuceg stabla najmanje tezine def kruskal(self): self.graf= Graph() self.graf.ucitaj_graf("datoteka") self.prijednjeni_vrhovi=[] self.pomocna_lista = {} vrhovi= self.graf.pvrhovi() self.bridovi={} self.put={} self.graf.plista_susjedstva() for i in self.graf.lista_susjedstva: self.pomocna_lista[i]=[] for x in self.graf.lista_susjedstva[i]: self.pomocna_lista[i].append(x) self.prijedjeni_vrhovi=[] self.bridovi= self.graf.pbridovi() min_tezina= max(self.bridovi.values()) #inicijaliziram na najvecu mogucu vrijenost for i in self.bridovi: if self.bridovi[i]== min_tezina: min_brid = i while 1: for vrh in vrhovi: #za svaki vrh for vrh1 in self.graf.lista_susjedstva[vrh]: #i njegov susjed tezina = self.graf.get_weight(vrh1,vrh) #pronadji najmanju tezinu if tezina< min_tezina: min_tezina = tezina for i in self.bridovi: if self.bridovi[i][0]== str(min_tezina): min_brid = i mini_vrh2= min_brid.split(",")[1] mini_vrh1= min_brid.split(",")[0] if mini_vrh1 not in self.prijedjeni_vrhovi: self.prijedjeni_vrhovi.append(mini_vrh1) if mini_vrh2 not in self.prijedjeni_vrhovi: self.prijedjeni_vrhovi.append(mini_vrh2) self.put[min_brid]=min_tezina self.graf.obrisi_brid(min_brid) self.obrisi_brid_ciklus() # funkcija koja brise onaj brid koji bi mogao biti ciklus m = len(vrhovi) count = 0 for i in vrhovi: if i in self.prijedjeni_vrhovi: count = count +1 if m == count: break min_tezina= max(self.bridovi.values()) #inicijaliziram tezinu na max vrijednost for i in self.bridovi: if self.bridovi[i]== min_tezina: min_brid = i print 'put',self.put return self.put #*********************************PLANARNOST******************************* #provjerava razlicite kriterije planarnosti i algoritme: class Planarnost: def __init__(self): """provjerava da li je zadani graf planarani""" #provjerava je li graf K5: def is_K5(self): return(len(self.g.foo.vrhovi)==5) and (len(self.g.foo.bridovi)==20) #provjerava je li graf K33: def is_K33(self): vx= self.g.foo.vrhovi ex = self.g.foo.bridovi if (len(vx)!=6) or (len(ex)!=18): return False white = self.g.foo.lista_susjedstva(vx[0]) if len(white)!=3: return False black =[x for x in vx if white.count(x)== 0] for v in white : x= self.g.foo.lista_susjedstva(v) x.sort if x != black: return False return True def remove_0degs(self): map(self.g.foo.obrisi_vrh,[x for x in self.g.foo.vrhovi if self.g.foo.stupanj(x) ==0]) def remove_1degs(self): while 1: vx = [x for x in self.g.foo.vrhovi if self.g.foo.stupanj(x) == 1] if vx == []: return map (self.g.foo.obrisi_vrh,vx) def remove_2degs(self): while 1: vx = [x for x in self.g.foo.vrhovi if self.g.foo.stupanj(x) ==2] if vx == []: return x = vx[0] conn = self.g.foo.lista_susjedstva[x] if not self.g.foo.is_susjed(conn[0],conn[1]): self.g.foo.dodaj_brid(conn[0],conn[1],1) self.g.foo.update() self.g.foo.obrisi_vrh(x) def remove_edges(self): self.remove_0degs() self.remove_2degs() self.remove_1degs() def non_planar_by_limit(self): n = len(self.g.foo.vrhovi) m = len(self.g.foo.bridovi)/2 if n < 3: return False if m> (3*n-6): return True return False def non_planar(self,l): if l == []: return self.is_K5() or self.is_K33() if self.non_planar_by_limit(): return True if self.non_planar( l[1:]): return True a,b = l[0] print l print self.g.foo.bridovi self.g.foo.obrisi_brid(str(a)+","+str(b)) self.remove_edges() l =[(a,b) for (a,b) in l[1:] if self.g.foo.is_susjed(a,b)] return self.non_planar(l) def less_than_6deg(self): return [1 for x in self.g.foo.vrhovi if self.g.foo.stupanj(x)<6] !=[] def planaran(self): self.g = Primjer() self.g.get_Petterson() self.remove_edges() print 'bridovi',self.g.foo.bridovi if not self.less_than_6deg(): return False ex = [] for niz in self.g.foo.bridovi: a = niz[0] b = niz[2] if a=2: return 0 return 1 #ukoliko pojedini vrhovi imaju vise od jednog zajednickog susjeda provjeri da li ti susjedi cine brid tj jesu li oni susjedi : def is_susjedstvo_vise(self): match= 0 susjedi=[] lista_1=[] lista_2=[] for vrh1 in self.nesto.foo.vrhovi: lista_1[:]= self.nesto.foo.lista_susjedstva[vrh1] for vrh2 in self.nesto.foo.lista_susjedstva[vrh1]: lista_2[:]= self.nesto.foo.lista_susjedstva[vrh2] for x in lista_2: if x in lista_1: susjedi.append(x) print susjedi,vrh1,vrh2,x for l in susjedi: for m in susjedi: if m!=l: if m in self.nesto.foo.lista_susjedstva[l]: return 0 del susjedi[:] return 1 #vraca 1 ako je graf vrsno 3 obojiv: def vrh_3_obojiv(self): self.nesto= Primjer() self.nesto.get_potpuni(7) print self.susjedstvo_1() if self.susjedstvo_1(): print "po prvom kriteriju " print "zadani graf je vrsno 3 obojiv" return 1 elif self.is_susjedstvo_vise(): print"po drugom kriteriju" print "zadani graf je vrsno 3 obojiv" return 1 else: print "zadani graf nije vrsno 3 obojiv" return 0 #vraca 1 ako je graf bridno 3 obojiv #graf sigurno nije bridno 3 obojiv ako mu je stupanj pojedninog vrha > 3, ukoliko je max stupanj pojedinog vrha 3 nije bridno 3 obojiv ako je izomorfan s Petersonovim grafom koji je 3-regularan ali je 4-bridno obojiv #provjerava sve mogucnosti je li graf 3 obojiv ukoliko je max stupanj vrha 3 : def provjeri_3_bridno(self): stog = [] #stog na koji cu stavljati sve mogucnosti koje sam mogla obojati(boju i brid) #stog : # [{'vrh1':boja1,'vrh2':boja2},obidji_vrh,trenutni_vrh,boje,pomocna_lista] # sve mora pamtiti obidji_vrh=[] # lista koja cuva koji se sljedeci vrh gleda i njegovi bridovi boja = {} #inicijaliziram dictionary boja i mogucih vrhova for vrh in self.graf.vrhovi: boja[vrh]=['c','p','z'] trenutni_vrh = self.graf.vrhovi[0] #krecem bojanje potpuno opcenito od prvog vrha pomocna_lista ={} #definirat pomocnu listu koju mogu brisati tako da znam sto sam presla for i in self.graf.lista_susjedstva:#kopija liste sujedstva koju mogu mijenjati pomocna_lista[i]=[] for j in self.graf.lista_susjedstva[i]: pomocna_lista[i].append(j) mogucnost= {} #koliko ima mogucnosti za pojedini brid za obojati #mogucnosti: # 3 3 (3) - potpuno opcenito mogu odabrati koji cu brid obojati kojom bojom # 2 2 - ovdje nije opcenito nego odaberem za svaki brid svoju boju , a drugu mogucnost s # trenutnim stanjem stavljam na stog # 1 2- obojam onaj koji ima jednu mogucnost s onom kojom sam mogla obojati, a drugu s # ovom koja ostane # 1 i ima jos u listi vise od 1 vrhova koji nisu prijedjeni - prijedji taj vrh i idi dalje # 1 i ima u listi jedan vrh koji je upravo susjed - obojaj brid i vrati 1 jer je moguce graf # obojati bridno s 3 boje # 0 i ima na stogu - uzmi sa stoga mogucnost bojanja i kreni s tim # 0 i nema na stogu - vrati 0 jer su obidjene sve mogucnosti, nije moguce obojat s 3 boje #petlja u kojoj sve ispitujem: O={} # kojom cu bojom obojati koji vrh counter = 0 lista=[] ima = 0 while 1: # za trenutni vrh pogledaj listu susjedstva i promotri koliko ima mogucnosti za obojati # (gledanje je li lista prazna cu ici na kraju jer ovdje na pocetku znam da nije prazna) for vrh in pomocna_lista[trenutni_vrh]: for i in boja[vrh]: if i in boja[trenutni_vrh]: counter = counter + 1 lista.append(i) if counter != 0: mogucnost[vrh]= counter #koliko mogucnosti imam else: continue print counter if counter !=0: print'ima', ima, counter ima =1 counter = 0 print 'mogucnost i vrhovi', mogucnost, trenutni_vrh if len(mogucnost) == 3: #nije samo na pocetku nego i tu imam slucjeve koje moram dodati> print "pocetna ima 3 susjeda" print mogucnost mogucnost1 = mogucnost.popitem() mogucnost2 = mogucnost.popitem() mogucnost3 = mogucnost.popitem() if mogucnost1[1]==3 and mogucnost2[1]==3 and mogucnost3[1]==3: boja[mogucnost1[0]].remove('c') # ovdje mi je svejedno kako rasporedim boja[trenutni_vrh].remove('c') boja[mogucnost2[0]].remove('p') boja[trenutni_vrh].remove('p') boja[mogucnost3[0]].remove('z') boja[trenutni_vrh].remove('z') pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[trenutni_vrh].remove(mogucnost2[0]) pomocna_lista[trenutni_vrh].remove(mogucnost3[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) pomocna_lista[mogucnost2[0]].remove(trenutni_vrh) pomocna_lista[mogucnost3[0]].remove(trenutni_vrh) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if mogucnost2[0] not in obidji_vrh: obidji_vrh.append(mogucnost2[0]) if mogucnost3[0] not in obidji_vrh: obidji_vrh.append(mogucnost3[0]) if len(mogucnost) ==2: print "najcesca mogucnost pogledaj podstupnjeve" print mogucnost mogucnost1= mogucnost.popitem() mogucnost11=mogucnost1[1] mogucnost2 = mogucnost.popitem() mogucnost21 = mogucnost2[1] print mogucnost1,mogucnost2,mogucnost11, mogucnost21, O #potpuno mi je svejedno kako rasporedim ako su 3 mogucnosti, to samo uzmem al je #to samo na pocetku: if mogucnost11 == 3 and mogucnost21 ==3:# isto kao i za 3 3 3 boja[mogucnost1[0]].remove('c') boja[trenutni_vrh].remove('c') boja[mogucnost2[0]].remove('p') boja[trenutni_vrh].remove('p') pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[trenutni_vrh].remove(mogucnost2[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) pomocna_lista[mogucnost2[0]].remove(trenutni_vrh) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if mogucnost2[0] not in obidji_vrh: obidji_vrh.append(mogucnost2[0]) print 'boja , pomocna_lista',boja,pomocna_lista,obidji_vrh # ovdje mi vise nije svejedno kako odabirem jer je vise mogucnosti: if mogucnost11 ==2 and mogucnost21 == 2: boja1 = boja[trenutni_vrh][0]#prve dvije odaberem, a ovo sto imam stavim na stog boja2 = boja[trenutni_vrh][1] boja11= boja2 boja21= boja1 pomocna_boja = {} for i in boja: pomocna_boja[i]= [] for j in boja[i]: pomocna_boja[i].append(j) l={} for i in pomocna_lista: l[i]=[] for j in pomocna_lista[i]: l[i].append(j) stog.append(((mogucnost1[0],boja11),(mogucnost2[0],boja21),obidji_vrh,trenutni_vrh,pomocna_boja,l)) boja[mogucnost1[0]].remove(boja1) boja[trenutni_vrh].remove(boja1) boja[mogucnost2[0]].remove(boja2) boja[trenutni_vrh].remove(boja2) pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[trenutni_vrh].remove(mogucnost2[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) pomocna_lista[mogucnost2[0]].remove(trenutni_vrh) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if mogucnost2[0] not in obidji_vrh: obidji_vrh.append(mogucnost2[0]) if mogucnost11 ==1 and mogucnost21 ==2: for i in boja[mogucnost1[0]]: if i in boja[trenutni_vrh]: boja1 = i boja[mogucnost1[0]].remove(boja1) boja[trenutni_vrh].remove(boja1) for j in boja[mogucnost2[0]]: if j in boja[trenutni_vrh]: boja2= j boja[mogucnost2[0]].remove(boja2) boja[trenutni_vrh].remove(boja2) pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[trenutni_vrh].remove(mogucnost2[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) pomocna_lista[mogucnost2[0]].remove(trenutni_vrh) if mogucnost2[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost2[0]) if mogucnost21 ==1 and mogucnost11 ==2: for i in boja[mogucnost2[0]]: if i in boja[trenutni_vrh]: boja1= i boja[mogucnost2[0]].remove(boja1) boja[trenutni_vrh].remove(boja1) for j in boja[mogucnost1[0]]: if j in boja[trenutni_vrh]: boja2=j boja[mogucnost1[0]].remove(boja2) boja[trenutni_vrh].remove(boja2) pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[trenutni_vrh].remove(mogucnost2[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) pomocna_lista[mogucnost2[0]].remove(trenutni_vrh) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if mogucnost2[0] not in obidji_vrh: obidji_vrh.append(mogucnost2[0]) if len(mogucnost) ==1 and ima: print "cesto na kraju"# tu mogu imati 2 mogucnosti pa moram to dodati mogucnost1 = mogucnost.popitem() if mogucnost1[1]==1: for i in boja[mogucnost1[0]]: if i in boja[trenutni_vrh]: boja1= i elif mogucnost1[1]==2: for i in boja[mogucnost1[0]]: if i in boja[trenutni_vrh]: boja1 = i for i in boja[mogucnost1[0]]: if i in boja[trenutni_vrh]: if i != boja1: boja2 = i pomocna_boja ={} for i in boja: pomocna_boja[i]=[] for j in boja[i]: pomocna_boja[i].append(j) l= {} for i in pomocna_lista: l[i]=[] for j in pomocna_lista[i]: l[i].append(j) stog.append(((mogucnost1[0],boja2),('0','0'),obidji_vrh,trenutni_vrh, pomocna_boja,l)) boja[mogucnost1[0]].remove(boja1) boja[trenutni_vrh].remove(boja1) pomocna_lista[trenutni_vrh].remove(mogucnost1[0]) pomocna_lista[mogucnost1[0]].remove(trenutni_vrh) if mogucnost1[0] not in obidji_vrh: obidji_vrh.append(mogucnost1[0]) if not ima: print'nema mogucnosti' # tu imam dvije provjere jer ili ima nesto na stogu ili nema nista na stogu if not stog: # prazan je stog i nema mogucnosti a ostalo je neprijedjenih # vrhova, onda je kraj jer se ne moye obojati return 0 skini_stog= stog.pop() mogucnost1 = skini_stog[0][0] boja1 = skini_stog[0][1] mogucnost2 = skini_stog[1][0] boja2= skini_stog[1][1] obidji_vrh = skini_stog[2] trenutni_vrh = skini_stog[3] pboja = skini_stog[4] for nesto in pboja: boja[nesto][:]= pboja[nesto] ppomocna_lista= skini_stog[5] for nesto in ppomocna_lista: pomocna_lista[nesto][:]= ppomocna_lista[nesto] print'@@', skini_stog print'__',mogucnost1,boja1 print'__',mogucnost2,boja2 print'_', obidji_vrh print'//',trenutni_vrh print'??',boja print'//',pomocna_lista print'LL',l print 'pomocna_boja',pomocna_boja print pomocna_boja, boja,l,pomocna_lista,self.graf.lista_susjedstva pomocna_boja.clear() l.clear() print boja, pomocna_lista boja[mogucnost1].remove(boja1) boja[trenutni_vrh].remove(boja1) if boja2 != '0': print'blah', boja2, boja boja[mogucnost2].remove(boja2) boja[trenutni_vrh].remove(boja2) pomocna_lista[trenutni_vrh].remove(mogucnost1) if mogucnost2 !='0': pomocna_lista[trenutni_vrh].remove(mogucnost2) pomocna_lista[mogucnost2].remove(trenutni_vrh) pomocna_lista[mogucnost1].remove(trenutni_vrh) if mogucnost1 not in obidji_vrh: obidji_vrh.append(mogucnost1) if mogucnost2 !='0': if mogucnost2 not in obidji_vrh: obidji_vrh.append(mogucnost1) if len(obidji_vrh)==1: print "gotov sam s ispitivanjem jer sam uspjela obojati " return 1 trenutni_vrh = obidji_vrh.pop() if len(pomocna_lista[trenutni_vrh]) == 3: pomozi = trenutni_vrh trenutni_vrh= obidji_vrh.pop() obidji_vrh.append(pomozi) ima = 0 print'boja', boja print'obidji', obidji_vrh, print trenutni_vrh, pomocna_lista #provjerava je li graf bridno 3-obojiv i ako je vraca 1: def brid_3_obojiv(self): self.graf=Graph() self.graf.ucitaj_graf("datoteka","bridno") matrica = self.graf.pmatrica_incidencije() self.graf.plista_susjedstva() print matrica nije= 0 je = 0 neznam = 0 for i in range(len(matrica)): if matrica[i].count(1)>3: print "Graf nije bridno 3 obojiv jer je barem jedan vrh stupnja veceg od 3" nije = 1 elif matrica[i].count(1)== 3: print "neznam jel graf bridno 3 obojiv" neznam = 1 else : je= 1 if nije : print "graf nije bridno 3 obojiv" return 0 elif je and not neznam: print "graf je bridno 3 obojiv" return 1 elif neznam: x = self.provjeri_3_bridno() if x : print "graf je bridno 3 obojiv" return 1 else: print "graf nije 3 bridno obojiv" return 0 #****************************SETNJE***************************************** class Setnje: def __init__(self): """nalazi kritican put u zadanom tezinskom grafu """ #**************************SPARIVANJA*************************************** class Sparivanja: def __init__(self): """u zadanom bipartitnom grafu obiljezenim vrhovima nadji i prebroji sva potpuna sparivanja""" # oboja vrhove grafa ako je graf bipartitni def color_bipartite(self): self.colors =[] vrh = self.graf.vrhovi[0] self.colors.append((vrh,0)) i = 0 while len(self.colors) != len(self.graf.vrhovi): trenutni_vrh = self.colors[i][0] boja= self.colors[i][1] if boja == 0: boja1 =1 else: boja1 = 0 for vrh in self.graf.lista_susjedstva[trenutni_vrh]: if (vrh,boja1) not in self.colors: self.colors.append((vrh,boja1)) i = i + 1 #prebraja sva potpuna sparivanja u zadanom grafu def potpuna_sparivanja(self): self.graf = Graph() self.graf.ucitaj_graf("datoteka","bipartitni1") self.graf.plista_susjedstva() self.color_bipartite() girls=[v for v,c in self.colors if c==0] boys=[v for v,c in self.colors if c== 1] def slave (g,b): if g==[]: return 1 available = [x for x in self.graf.lista_susjedstva[g[0]]if b.count(x)!=0] if available == [0]: return 0 cnt = 0 for x in available: cnt = cnt + slave(g[1:],[y for y in b if g!=x]) return cnt x = slave(girls,boys) print 'rezultat',x return x #******************ISPROBAVANJA********************************** #x=Primjer() #g= x.get_Petterson() #planarnost = Planarnost() #planarnost.planaran() #sparivanja = Sparivanja() #sparivanja.potpuna_sparivanja() #stabla =Stabla() #x=stabla.kruskal() #dijkstra= Dijkstra() #dijkstra.get_dijkstra() #graf=Graph() #primjer=Primjer() povezanost = Povezanost() #m= povezanost.najkraca_staza() x= povezanost.najdulja_staza() #stabla = Stabla() #stabla.kirchoff() #bojanje = Bojanja() #bojanje.vrh_3_obojiv() #bojanje.brid_3_obojiv() #x=graf.ucitaj_graf("datoteka") #v=graf.pvrhovi() #b=graf.pbridovi() #print v #print b #m=graf.plista_susjedstva() #max= graf.pmatrica_susjedstva() #mat=graf.pmatrica_incidencije() #ob= graf.obrisi_brid('ab') #ov= graf.obrisi_vrh('d')