Usmjereni grafovi u SAGE-u
verzija: SageMath 8.4
Kod konstrukcije digrafa vrijede sva ista pravila kao i kod konstrukcije grafa, jedino umjesto klase Graph treba koristiti klasu DiGraph.
In [1]:
from IPython.core.display import Image
In [2]:
digraf1=DiGraph({"u":["x"],"v":["u","x"],"w":["u"],"x":["w"]})
Kod crtanja digrafa vrijede ista pravila kao i kod crtanja grafa. Također, sve one opcije koje smo koristili kod crtanja grafa se mogu koristiti i kod crtanja digrafa pa ovdje nećemo toliko posebno spominjati sve te opcije.
Digraf1
In [3]:
digraf1.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])
outstupanj vrha v
In [4]:
digraf1.out_degree("v")
Out[4]:
instupanj vrha v
In [5]:
digraf1.in_degree("v")
Out[5]:
outstupnjevi svih vrhova
In [6]:
digraf1.out_degree()
Out[6]:
In [7]:
digraf1.out_degree(labels=True)
Out[7]:
instupnjevi svih vrhova
In [8]:
digraf1.in_degree()
Out[8]:
In [9]:
digraf1.in_degree(labels=True)
Out[9]:
outstupnjevi vrhova u i v
In [10]:
digraf1.out_degree(["u","v"])
Out[10]:
In [11]:
digraf1.out_degree(["u","v"],labels=True)
Out[11]:
instupnjevi vrhova u i v
In [12]:
digraf1.in_degree(["u","v"])
Out[12]:
In [13]:
digraf1.in_degree(["u","v"],labels=True)
Out[13]:
možemo analogno tražiti stupnjeve vrhova u pripadnom grafu
In [14]:
digraf1.degree(labels=True)
Out[14]:
matrica susjedstva
vrhovi se smještaju u matricu susjedstva onim redom kojim su u listi digraf1.vertices()
In [15]:
digraf1.vertices()
Out[15]:
In [16]:
digraf1.adjacency_matrix()
Out[16]:
vrhovi iz kojih postoji luk prema vrhu x (in-susjedi vrha x)
In [17]:
digraf1.neighbors_in("x")
Out[17]:
vrhovi prema kojima postoji luk iz vrha x (out-susjedi vrha x)
In [18]:
digraf1.neighbors_out("x")
Out[18]:
susjedni vrhovi vrha x u pripadnom grafu
In [19]:
digraf1.neighbors("x")
Out[19]:
da li je digraf povezan
In [20]:
digraf1.is_connected()
Out[20]:
komponente povezanosti - ima samo jednu komponentu jer je digraf povezan
In [21]:
digraf1.connected_components()
Out[21]:
da li je digraf dipovezan (jako povezan)
In [22]:
digraf1.is_strongly_connected()
Out[22]:
dikomponente - digraf1 ima dvije dikomponente
In [23]:
digraf1.strongly_connected_components()
Out[23]:
dikomponenta koja sadrži vrh x
In [24]:
digraf1.strongly_connected_component_containing_vertex("x")
Out[24]:
digraf dikomponenata - vrhovi predstavljaju dikomponente, a iz prvog vrha prema drugom postoji luk jedino ako se iz prve dikomponente može ući u drugu dikomponentu.
In [25]:
dig1=digraf1.strongly_connected_components_digraph()
In [26]:
dig1.show(pos={dig1.vertices()[0]:[0,0],dig1.vertices()[1]:[20,0]},vertex_shape='h',vertex_size=5000)
dikomponente kao inducirani podgrafovi
In [27]:
dikomponente=digraf1.strongly_connected_components_subgraphs();dikomponente
Out[27]:
In [28]:
graphs_list.show_graphs(dikomponente)
In [29]:
graphics_array([dikomponente[0].plot(graph_border=True),dikomponente[1].plot(graph_border=True)]).show(figsize=[4,2])
da li digraf nema usmjerenih ciklusa
In [30]:
digraf1.is_directed_acyclic()
Out[30]:
najkraći usmjereni put od vrha v prema vrhu u i njegova duljina
In [31]:
digraf1.shortest_path("v","u")
Out[31]:
In [32]:
digraf1.shortest_path_length("v","u")
Out[32]:
ne postoji usmjereni put od vrha u prema vrhu v
In [33]:
digraf1.shortest_path("u","v")
Out[33]:
In [34]:
digraf1.shortest_path_length("u","v")
Out[34]:
najkraći usmjereni putovi od vrha u prema svim preostalim vrhovima i njihove udaljenosti
In [35]:
digraf1.shortest_paths("u")
Out[35]:
In [36]:
digraf1.shortest_path_lengths("u")
Out[36]:
Digraf2
In [37]:
digraf2=DiGraph({"u":["v"],"v":["u","x"],"w":["u","x"]})
In [38]:
digraf2.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])
matrica susjedstva
In [39]:
digraf2.vertices()
Out[39]:
In [40]:
digraf2.adjacency_matrix()
Out[40]:
digraf nije dipovezan
In [41]:
digraf2.is_strongly_connected()
Out[41]:
digraf ima tri dikomponente
In [42]:
digraf2.strongly_connected_components()
Out[42]:
digraf dikomponenata
In [43]:
dig2=digraf2.strongly_connected_components_digraph();dig2
Out[43]:
In [44]:
dig2.show(pos={dig2.vertices()[0]:[0,0],dig2.vertices()[1]:[20,-10],dig2.vertices()[2]:[40,0]},
vertex_shape='h',vertex_size=3000,figsize=[5,3],ymax=3)
dikomponente kao inducirani podgrafovi
In [45]:
dikomponente2=digraf2.strongly_connected_components_subgraphs();dikomponente2
Out[45]:
In [46]:
graphs_list.show_graphs(dikomponente2)
In [47]:
gr2=graphics_array([dikomponente2[0].plot(graph_border=True),dikomponente2[1].plot(graph_border=True,
pos={"u":[0,1],"v":[1,0]}),dikomponente2[2].plot(graph_border=True)])
gr2.show(figsize=[7,4])
digraf2 sadrži usmjerene cikluse
In [48]:
digraf2.is_directed_acyclic()
Out[48]:
Digraf3
In [49]:
digraf3=DiGraph({"u":["v","v"],"v":["x"],"w":["u","x"]})
In [50]:
digraf3.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},
vertex_size=500,figsize=[3,3])
matrica susjedstva
In [51]:
digraf3.vertices()
Out[51]:
In [52]:
digraf3.adjacency_matrix()
Out[52]:
digraf nije dipovezan
In [53]:
digraf3.is_strongly_connected()
Out[53]:
digraf ima četiri dikomponente
In [54]:
digraf3.strongly_connected_components()
Out[54]:
digraf ne sadrži usmjerene cikluse
In [55]:
digraf3.is_directed_acyclic()
Out[55]:
Digraf4
In [56]:
digraf4=DiGraph({"u1":["u3"],"u2":["u1"],"u3":["u2"],"u4":["u1","u3"]})
In [57]:
digraf4.show(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},vertex_size=400,figsize=[3,3])
matrica susjedstva
In [58]:
digraf4.vertices()
Out[58]:
In [59]:
mat4=digraf4.adjacency_matrix();mat4
Out[59]:
ukupni broj usmjerenih $(u_1,u_2)$-šetnji duljine 2
In [60]:
(mat4^2)[0,1]
Out[60]:
ukupni broj usmjerenih $(u_2,u_1)$-šetnji duljine 2
In [61]:
(mat4^2)[1,0]
Out[61]:
ukupni broj usmjerenih $(u_4,u_3)$-šetnji duljine 5
In [62]:
(mat4^5)[3,2]
Out[62]:
Digraf5
In [63]:
digraf5=DiGraph({"v1":["v2","v4"],"v2":["v4"],"v3":["v2"],"v4":["v3"]})
In [64]:
digraf5.show(graph_border=True,vertex_color="yellow",pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400,figsize=[3,3])
digraf4 i digraf5
In [65]:
graphics_array([digraf4.plot(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},
vertex_size=400),digraf5.plot(graph_border=True,vertex_color="yellow",
pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400)]).show(figsize=[6,4])
digraf4 i digraf5 su izomorfni digrafovi
In [66]:
digraf4.is_isomorphic(digraf5)
Out[66]:
izomorfizam: $u_1\leftrightarrow v_2,\quad u_2\leftrightarrow v_3,\quad u_3\leftrightarrow v_4,\quad u_4\leftrightarrow v_1$
In [67]:
digraf4.is_isomorphic(digraf5,certificate=True)
Out[67]:
ispitivanje izomornosti pomoću networkx modula
In [68]:
import networkx as nx
In [69]:
D4=nx.DiGraph()
D4.add_edges_from([('u1','u3'),('u2','u1'),('u3','u2'),('u4','u1'),('u4','u3')])
In [70]:
D5=nx.DiGraph()
D5.add_edges_from([('v1','v2'),('v1','v4'),('v2','v4'),('v3','v2'),('v4','v3')])
In [71]:
DM=nx.isomorphism.DiGraphMatcher(D4,D5)
In [72]:
DM.is_isomorphic()
Out[72]:
In [73]:
DM.mapping
Out[73]:
postoji samo jedan izomorfizam između digrafova digraf4 i digraf5
In [74]:
for u in DM.isomorphisms_iter():
print u
matrica permutacije
In [75]:
grupa=SymmetricGroup(4)
grupa([2,3,4,1])
Out[75]:
In [76]:
P=grupa([2,3,4,1]).matrix().transpose();P
Out[76]:
In [77]:
P*digraf4.adjacency_matrix()*P.transpose()==digraf5.adjacency_matrix()
Out[77]:
Turnir
In [78]:
turnir=DiGraph({'a':['c','d'],'b':['a','c','e'],'c':['f'],'d':['b','c'],'e':['a','c','d','f'],'f':['a','b','d']})
turpoz={'a':[2,0],'b':[4,0],'c':[6,2],'d':[4,4],'e':[2,4],'f':[0,2]}
In [79]:
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)
vektor uspjeha turnira
In [80]:
turnir.vertices()
Out[80]:
In [81]:
turnir.out_degree(labels=True)
Out[81]:
In [82]:
turnir.out_degree()
Out[82]:
najkraći usmjereni put od vrha a do vrha d
In [83]:
turnir.shortest_path("a","d")
Out[83]:
najkraći usmjereni put od vrha a do vrha e
In [84]:
turnir.shortest_path("a","e")
Out[84]:
najkraći put istaknut na digrafu
In [85]:
def najkraci_put(G,v1,v2,raspored_vrhova=None,tezine=False,laj="circular",velicina_vrha=300):
put=G.shortest_path(v1,v2,by_weight=tezine)
ostali_vrhovi=list(set(G.vertices()).difference(set([v1,v2])))
bridovi=G.edges(labels=False)
bridovi_put=[]
for i in xrange(len(put)-1):
if (put[i],put[i+1]) in bridovi:
bridovi_put.append((put[i],put[i+1]))
else:
bridovi_put.append((put[i+1],put[i]))
if raspored_vrhova==None:
slika=G.plot(edge_colors={"red":bridovi_put},vertex_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
layout=laj,edge_labels=tezine,vertex_size=velicina_vrha)
else:
slika=G.plot(edge_colors={"red":bridovi_put},vertex_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
pos=raspored_vrhova,edge_labels=tezine,vertex_size=velicina_vrha)
return slika
In [86]:
najkraci_put(turnir,"a","d",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [87]:
najkraci_put(turnir,"a","e",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
Brentov algoritam
Za traženje usmjerenih ciklusa u bilo kojem digrafu, dolje je implementiran Brentov algoritam. Taj algoritam za zadani digraf daje neki, na slučajni način pronađeni, usmjereni ciklus.
In [88]:
def usmjereni_ciklus(D):
if not(D.is_directed_acyclic): return "nema usmjerenih ciklusa"
x0 = choice(D.vertices())
f = {}
for v in D.vertices():
f[v] = choice(D.neighbors_out(v))
#racunanje lambde
power = 1
lam = 1
tortoise = x0
hare = f[x0]
while tortoise != hare:
if power == lam:
tortoise = hare
power *= 2
lam = 0
hare = f[hare]
lam += 1
# mu = pozicija prvog ponavljanja duljine lambda
mu = 0
tortoise = hare = x0
for i in xrange(lam):
hare = f[hare]
while tortoise != hare:
tortoise = f[tortoise]
hare = f[hare]
mu += 1
ciklus=[tortoise]
for i in xrange(lam):
tortoise=f[tortoise]
ciklus.append(tortoise)
return ciklus
nekoliko usmjerenih ciklusa u našem promatranom turniru
In [89]:
for i in xrange(5):
print usmjereni_ciklus(turnir)
ako želimo usmjereni ciklus istaknuti na digrafu
In [90]:
def usmjereni_ciklus_digraf(D,raspored_vrhova=None,laj="circular",velicina_vrha=300):
ciklus = usmjereni_ciklus(D)
vrhovi2 = list(set(D.vertices()).difference(set(ciklus)))
lukovi_ciklus = []
for i in xrange(len(ciklus)-1):
lukovi_ciklus.append((ciklus[i],ciklus[i+1]))
if raspored_vrhova == None:
slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
layout=laj,vertex_size=velicina_vrha)
else:
slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
pos=raspored_vrhova,vertex_size=velicina_vrha)
return slika
nekoliko usmjerenih ciklusa istaknutih na digrafu
In [91]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [92]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [93]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [94]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
promatrani turnir je Hamiltonov digraf
In [95]:
turnir.is_hamiltonian()
Out[95]:
In [96]:
turnir.hamiltonian_cycle().show()
Hamiltonov ciklus istaknut na digrafu
In [97]:
def hamiltonov_ciklus(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
if not(G.is_hamiltonian()):
return "Error: Graf nije Hamiltonov"
bridovi=G.hamiltonian_cycle().edges(labels=False)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
return slika
In [98]:
hamiltonov_ciklus(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])
Neki Hamiltonov put u promatranom turniru
In [99]:
def usmjereni_hamiltonov_put(G):
try:
H=G.copy()
H.add_edges(zip(G.vertices(),['vrh']*G.num_verts()))
H.add_edges(zip(['vrh']*G.num_verts(),G.vertices()))
ciklus=H.hamiltonian_cycle()
ciklus.delete_vertex('vrh')
return ciklus.edges(labels=False)
except ValueError:
return "Error: Digraf nema Hamiltonov put"
In [100]:
usmjereni_hamiltonov_put(turnir)
Out[100]:
Neki Hamiltonov put istaknut na digrafu
In [101]:
def usmjereni_hamiltonov_put_digraf(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
bridovi = usmjereni_hamiltonov_put(G)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
return slika
In [102]:
usmjereni_hamiltonov_put_digraf(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])
promatrani turnir nije Eulerov digraf
In [103]:
turnir.is_eulerian()
Out[103]:
Dva turnira s tri vrha
In [104]:
trokut1=DiGraph({"a":["b"],"b":["c"],"c":["a"]})
trokut2=DiGraph({"a":["b","c"],"b":["c"]})
trokutpoz={"a":[0,0],"b":[2,0],"c":[1,1.5]}
In [105]:
graphics_array([trokut1.plot(graph_border=true,pos=trokutpoz),trokut2.plot(graph_border=true,pos=trokutpoz)]).show(figsize=[6,4])
trokut1 je Eulerov digraf, a trokut2 nije Eulerov digraf
In [106]:
trokut1.is_eulerian()
Out[106]:
In [107]:
trokut2.is_eulerian()
Out[107]:
trokut1 je Hamiltonov digraf, a trokut2 nije Hamiltonov digraf
In [108]:
trokut1.is_hamiltonian()
Out[108]:
In [109]:
trokut2.is_hamiltonian()
Out[109]:
međutim, trokut2 ipak ima usmjereni Hamiltonov put
In [110]:
usmjereni_hamiltonov_put_digraf(trokut2,trokutpoz).show(figsize=[3,3])
Rangiranje
In [111]:
def snaga_vrha(T,v0):
indeks=T.vertices().index(v0)
matrica=T.adjacency_matrix()+(T.adjacency_matrix())^2
return sum(matrica.row(indeks))
In [112]:
def rang_lista(turnir,izlaz="html"):
rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
if izlaz == "lista":
return rezultat
elif izlaz == "html":
return table([['igrači','broj pobjeda','snaga pobjeda']]+rezultat)
rang lista za turnir
In [113]:
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)
In [114]:
def rang_lista(turnir,izlaz="html"):
rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
if izlaz == "lista":
return rezultat
elif izlaz == "html":
return table([['igraci','broj pobjeda','snaga pobjeda']]+rezultat)
In [115]:
rang_lista(turnir)
Out[115]:
In [116]:
rang_lista(turnir,izlaz="lista")
Out[116]:
rang lista za turnir2
In [117]:
turnir2=DiGraph({"A":["B","C","D"],"B":["D","E"],"C":["B","D"],"E":["A","C","D"]})
In [118]:
turnir2.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
In [119]:
rang_lista(turnir2)
Out[119]:
In [120]:
rang_lista(turnir2,izlaz="lista")
Out[120]:
rang lista za turnir3
In [121]:
turnir3=DiGraph({"A":["C","D"],"B":["A","C","E"],"C":["D"],"D":["B"],"E":["A","C","D"]})
In [122]:
turnir3.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
In [123]:
rang_lista(turnir3)
Out[123]:
Bellman-Fordov algoritam
U ovom dijelu je napravljena implementacija Bellman-Fordovog algoritma (posebno prilagođena ručnom rješavanju zadataka). Također, implementirana je i poboljšana verzija Dijkstrinog algoritma koja je također posebno prilagođena ručnom rješavanju zadataka. Inače, Dijkstrin algoritam je implementiran u SAGE-u i već smo ga koristili kod težinskih grafova. Bellman-Fordov algoritam je implementiran samo za težinske digrafove, a Dijkstrin algoritam je implementiran za težinske grafove i digrafove.
In [124]:
def BellmanFord(D,v0):
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
P = {}
udaljenost = {}
V = D.vertices()
E = D.edges()
udaljenost[0]={}
for v in V:
if v == v0:
udaljenost[0][v] = 0
P[v] = None
else:
udaljenost[0][v] = Infinity
P[v] = None
for i in range(1, len(V)+1):
udaljenost[i]=copy(udaljenost[i-1])
promjena=False
for v in V:
for u in D.neighbors_in(v):
if udaljenost[i][v] > udaljenost[i-1][u]+tezina_brida[(u,v)]:
udaljenost[i][v] = udaljenost[i-1][u]+tezina_brida[(u,v)]
P[v]=u
promjena=True
if promjena==False:
break
if udaljenost[len(udaljenost)-1]!=udaljenost[len(udaljenost)-2]: print "error: digraf ima negativne cikluse"
return (udaljenost[len(udaljenost)-1], P)
In [125]:
def Dijkstra_digraf(D,v0):
MM=min(map(lambda x: x[2],D.edges()))
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
P={}
udaljenost={}
Q=set(D.vertices())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=Infinity
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == Infinity: break
v=choice(filter(lambda x: udaljenost[x]==m, Q))
Q.remove(v)
for u in set(D.neighbors_out(v)).intersection(Q):
if udaljenost[u] > udaljenost[v]+tezina_brida[(v,u)]:
udaljenost[u] = udaljenost[v]+tezina_brida[(v,u)]
P[u] = v
if MM<0: print "error: Dijkstra ne radi ispravno na negativnim težinama"
return (udaljenost,P)
In [126]:
def Dijkstra_graf(G,v0):
MM=min(map(lambda x: x[2],G.edges()))
tezina_brida={}
for e in G.edges():
tezina_brida[(e[0],e[1])]=e[2]
tezina_brida[(e[1],e[0])]=e[2]
P={}
udaljenost={}
Q=set(G.vertices())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=Infinity
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == Infinity: break
v=choice(filter(lambda x: udaljenost[x]==m, Q))
Q.remove(v)
for u in set(G.neighbors(v)).intersection(Q):
if udaljenost[u] > udaljenost[v]+tezina_brida[(v,u)]:
udaljenost[u] = udaljenost[v]+tezina_brida[(v,u)]
P[u] = v
if MM<0: print "error: Dijkstra ne radi ispravno na negativnim težinama"
return (udaljenost,P)
In [127]:
def rucni_BellmanFord(D,v0,poredak=None):
koraci={}
if poredak==None:
V=D.vertices()
else:
V=poredak
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
for i in xrange(1,len(V)+1):
koraci[i]=copy(koraci[i-1])
promjena=False
for v in V:
for u in D.neighbors_in(v):
if koraci[i][v][1] > koraci[i-1][u][1]+tezina_brida[(u,v)]:
koraci[i][v] = (u, koraci[i-1][u][1]+tezina_brida[(u,v)])
promjena=True
if promjena==False:
break
tablica=[]
for i in xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
if koraci[len(koraci)-1]!=koraci[len(koraci)-2]: print "error: digraf ima negativne cikluse"
return table(tablica)
In [128]:
def rucni_Dijkstra_digraf(D,v0,poredak=None):
if poredak==None:
V=D.vertices()
else:
V=poredak
koraci={}
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
MM=min(map(lambda x: x[2],D.edges()))
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
Q=set(D.vertices())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==Infinity:
break
else:
koraci[k]=copy(koraci[k-1])
w=choice(filter(lambda x: koraci[k-1][x][1]==m, Q))
Q.remove(w)
koraci[k][w]='*'
for v in set(D.neighbors_out(w)).intersection(Q):
if koraci[k-1][v][1] > koraci[k-1][w][1]+tezina_brida[(w,v)]:
koraci[k][v] = (w, koraci[k-1][w][1]+tezina_brida[(w,v)])
k += 1
tablica=[]
for i in xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
if MM<0: print "error: Dijkstra ne radi ispravno na negativnim tezinama"
return table(tablica)
In [129]:
def rucni_Dijkstra_graf(G,v0, poredak=None):
if poredak==None:
V=G.vertices()
else:
V=poredak
koraci={}
tezina_brida={}
for e in G.edges():
tezina_brida[(e[0],e[1])]=e[2]
tezina_brida[(e[1],e[0])]=e[2]
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
Q=set(G.vertices())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==Infinity:
break
else:
koraci[k]=copy(koraci[k-1])
w=choice(filter(lambda x: koraci[k-1][x][1]==m, Q))
Q.remove(w)
koraci[k][w]='*'
for v in set(G.neighbors(w)).intersection(Q):
if koraci[k-1][v][1] > koraci[k-1][w][1]+tezina_brida[(w,v)]:
koraci[k][v] = (w, koraci[k-1][w][1]+tezina_brida[(w,v)])
k += 1
tablica=[]
for i in xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
return table(tablica)
Funkcija stablo_min_putova_DSTG služi za isticanje stabla najkraćih putova od nekog vrha na težinskom grafu ili digrafu na kojeg je primijenjen neki od naših implementiranih algoritama. Stoga opcija algoritam može imati neku od tri vrijednosti: BellmanFord, Dijkstra_digraf, Dijkstra_graf. Pritom, prva dva algoritma primijenjujemo na težinske digrafove, a zadnji na težinske grafove.
In [130]:
def stablo_min_putova_DSTG(D,v0,algoritam=BellmanFord,raspored_vrhova=None,laj="circular",brid0="red",vrh0="yellow",velicina=300):
P=algoritam(D,v0)[1]
bridovi=[]
for x in P:
if D.is_directed():
if P[x]!=None: bridovi.append((P[x],x))
else:
if P[x]!=None:
if (P[x],x) in D.edges(labels=False):
bridovi.append((P[x],x))
else:
bridovi.append((x,P[x]))
ostali_bridovi=list(set(D.edges(labels=False)).difference(set(bridovi)))
if raspored_vrhova==None:
slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,layout=laj,
edge_labels=True,vertex_size=velicina)
else:
slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,pos=raspored_vrhova,
edge_labels=True,vertex_size=velicina)
return slika
Nekoliko naredbi koje omogućuju lakše crtanje s Graphvizom
In [131]:
def graf_string(G,slika=None,fontV=12,fontE=12,xy=None,bojaVrha="white",bojaBrida="black",debljinaV=1,debljinaE=1,
bojaTezine="black",bojeVrhova=None,bojeBridova=None,tezine=True,dekor=False,d={},kut={}):
"""Pretvara sage graf G u graphviz format.
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
bojaVrha -> boje svih vrhova na slici
bojaBrida -> boje svih bridova na slici
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
bojeVrhova -> rjecnik boja za svaki pojedini vrh ako zelimo da vrhovi budu razlicito obojani
bojeBridova -> rjecnik boja za svaki pojedini brid ako zelimo bridove obojati u razlicitim bojama
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
if G.is_directed():
rijec='digraph {\n '
strelica='>'
else:
rijec='graph {\n '
strelica='-'
if slika!=None:
rijec+='size="%d,%d!"\n ' % slika
rijec+='node [shape=circle width=0 height=0 margin=0 style=filled fontsize=%d penwidth=%d];\n ' % (fontV,debljinaV)
if dekor:
rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true decorate=true fontsize=%d penwidth=%d];\n '
% (bojaBrida,bojaTezine,fontE,debljinaE))
else:
rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true,fontsize=%d penwidth=%d];\n '
% (bojaBrida,bojaTezine,fontE,debljinaE))
if bojeVrhova==None:
bojeVrhova={}
for v in G.vertices():
bojeVrhova[v]=bojaVrha
if xy!=None:
for v in G.vertices():
rijec+='"%s" [label="%s" pos="%d,%d!" fillcolor=%s];\n ' % (str(v),str(v),xy[v][0],xy[v][1],bojeVrhova[v])
else:
for v in G.vertices():
rijec+='"%s" [label="%s" style=filled fillcolor=%s];\n ' % (str(v),str(v),bojeVrhova[v])
if bojeBridova==None:
bojeBridova={}
for e in G.edges():
bojeBridova[(e[0],e[1])]=bojaBrida
if tezine==False:
for e in G.edges():
rijec+='"%s" -> "%s" [color=%s];\n ' % (str(e[0]),str(e[1]),bojeBridova[(e[0],e[1])])
if tezine==True:
if d=={}:
for e in G.edges():
rijec+='"%s" -%s "%s" [color=%s label="%d"];\n ' % (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2])
else:
for e in G.edges():
if (e[0],e[1]) in d.keys():
rijec+=('"%s" -%s "%s" [color=%s headlabel="%d" labeldistance=%d labelangle=%d];\n '
% (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2],d[(e[0],e[1])],kut[(e[0],e[1])]))
else:
rijec+=('"%s" -%s "%s" [color=%s label="%d"];\n '
% (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2]))
rijec+='}'
return rijec
In [132]:
def crtaj_graphviz(G,ime,slika=None,fontV=12,fontE=12,xy=None,bojaVrha="white",bojaBrida="black",debljinaV=1,debljinaE=1,
bojaTezine="black",bojeVrhova=None,bojeBridova=None,tezine=True,dekor=False,d={},kut={}):
"""Crta sage graf G pomocu graphviza.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
bojaVrha -> boje svih vrhova na slici
bojaBrida -> boje svih bridova na slici
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
bojeVrhova -> rjecnik boja za svaki pojedini vrh ako zelimo da vrhovi budu razlicito obojani
bojeBridova -> rjecnik boja za svaki pojedini brid ako zelimo bridove obojati u razlicitim bojama
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
rijec=graf_string(G,slika,fontV,fontE,xy,bojaVrha,bojaBrida,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
In [133]:
def graphviz_stablo_min_putova(D,v0,ime,algoritam=BellmanFord,slika=None,fontV=12,fontE=12,xy=None,debljinaV=1,debljinaE=1,
vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",tezine=True,
dekor=False,d={},kut={}):
"""Istice stablo najkracih putova od vrha v0 prema svim preostalim vrhovima na tezinskom digrafu (ili grafu) na
kojeg je primijenjen neki od nasih implementiranih algoritama.
Opcija 'algoritam' moze imati neku od tri vrijednosti: BellmanFord, Dijkstra_digraf, Dijkstra_graf.
Slika se crta u graphviz formatu.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
vrh0 -> boje vrha v0
vrh1 -> boja preostalih vrhova
brid0 -> boja bridova koji pripadaju stablu
brid1 -> boja bridova koji ne pripadaju stablu
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
P=algoritam(D,v0)[1]
bridovi=[]
for x in P:
if D.is_directed():
if P[x]!=None: bridovi.append((P[x],x))
else:
if P[x]!=None:
if (P[x],x) in D.edges(labels=False):
bridovi.append((P[x],x))
else:
bridovi.append((x,P[x]))
ostali_vrhovi=D.vertices()
ostali_vrhovi.remove(v0)
bojeVrhova={v0:vrh0}
for v in ostali_vrhovi:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in D.edges():
if (e[0],e[1]) in bridovi:
bojeBridova[(e[0],e[1])]=brid0
else:
bojeBridova[(e[0],e[1])]=brid1
rijec=graf_string(D,slika,fontV,fontE,xy,vrh1,brid1,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
digraf6 - Bellman-Ford i Dijkstra dobro rade
In [134]:
var('v1 v2 v3 v4 v5 v6 v7 v8')
Out[134]:
In [135]:
digraf6=DiGraph({v1:{v2:1,v5:4},
v2:{v3:1,v5:3},
v3:{v4:5,v5:1},
v4:{v3:1},
v5:{v3:1,v4:1}
},weighted=True)
In [136]:
D6pos={v1:[0,2],v2:[2,4],v3:[5,4],v4:[6,0],v5:[2,0]}
In [137]:
rucni_BellmanFord(digraf6,v1,[v1,v2,v3,v4,v5])
Out[137]:
In [138]:
BellmanFord(digraf6,v1)
Out[138]:
In [139]:
stablo_min_putova_DSTG(digraf6,v1,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=2000).show(figsize=[6,4])
ljepša slika
In [140]:
graphviz_stablo_min_putova(digraf6,v1,"D6.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",vrh1="pink",
brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[140]:
In [141]:
rucni_Dijkstra_digraf(digraf6,v1,[v1,v2,v3,v4,v5])
Out[141]:
In [142]:
Dijkstra_digraf(digraf6,v1)
Out[142]:
In [143]:
stablo_min_putova_DSTG(digraf6,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])
ljepša slika
In [144]:
graphviz_stablo_min_putova(digraf6,v1,"D6dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[144]:
pogledajmo još iz vrha $v_4$ kao početnog vrha
In [145]:
rucni_BellmanFord(digraf6,v4,[v1,v2,v3,v4,v5])
Out[145]:
In [146]:
BellmanFord(digraf6,v4)
Out[146]:
In [147]:
stablo_min_putova_DSTG(digraf6,v4,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])
ljepša slika
In [148]:
graphviz_stablo_min_putova(digraf6,v4,"D6tri.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[148]:
In [149]:
rucni_Dijkstra_digraf(digraf6,v4,[v1,v2,v3,v4,v5])
Out[149]:
In [150]:
Dijkstra_digraf(digraf6,v4)
Out[150]:
In [151]:
graphviz_stablo_min_putova(digraf6,v4,"D6cetiri.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[151]:
digraf7 - zbog negativnih težina Dijkstra ne radi dobro; a kako nema negativnih ciklusa, Bellman-Ford radi ispravno
In [152]:
digraf7=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:4},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
In [153]:
rucni_BellmanFord(digraf7,v1,[v1,v2,v3,v4,v5])
Out[153]:
In [154]:
BellmanFord(digraf7,v1)
Out[154]:
In [155]:
graphviz_stablo_min_putova(digraf7,v1,"D7.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[155]:
In [156]:
rucni_Dijkstra_digraf(digraf7,v1,[v1,v2,v3,v4,v5])
Out[156]:
In [157]:
Dijkstra_digraf(digraf7,v1)
Out[157]:
In [158]:
graphviz_stablo_min_putova(digraf7,v1,"D7dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[158]:
digraf8 - ima usmjereni ciklus negativne težine. Stoga, niti Bellman-Ford, niti Dijkstra ne rade dobro na ovom digrafu.
In [159]:
digraf8=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:1},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
In [160]:
rucni_BellmanFord(digraf8,v1)
Out[160]:
In [161]:
BellmanFord(digraf8,v1)
Out[161]:
In [162]:
graphviz_stablo_min_putova(digraf8,v1,"D8.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[162]:
In [163]:
rucni_Dijkstra_digraf(digraf8,v1)
Out[163]:
In [164]:
Dijkstra_digraf(digraf8,v1)
Out[164]:
In [165]:
graphviz_stablo_min_putova(digraf8,v1,"D8dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[165]:
digraf9 - digraf sadrži usmjereni ciklus negativne težine koji se dvaput obišao u toku izvođenja Bellman-Fordovog algoritma i naravno dobivamo krive rezultate. U ovom slučaju Dijkstra radi ispravno, ali to je samo splet okolnosti zbog same strukture digrafa koja ovdje dobro odgovara Dijkstrinom algoritmu iz vrha $v_1$ (općenito ne možemo garantirati točnost rezultata).
In [166]:
digraf9=DiGraph({v1:{v2:3},
v2:{v3:-2},
v3:{v4:1},v4:{v2:-1,v5:1},
v5:{v6:1},v6:{v7:1},v7:{v8:1}},weighted=True)
In [167]:
D9pos={v1:[0,0.5],v2:[2,0.4],v3:[4,1],v4:[6,0.4],v5:[8,0.4],v6:[10,0.3],v7:[12,1],v8:[8,2]}
In [168]:
rucni_BellmanFord(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
Out[168]:
In [169]:
BellmanFord(digraf9,v1)
Out[169]:
In [170]:
stablo_min_putova_DSTG(digraf9,v1,algoritam=BellmanFord,raspored_vrhova=D9pos,velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
In [171]:
graphviz_stablo_min_putova(digraf9,v1,"D9.png",algoritam=BellmanFord,slika=(9,8),xy=D9pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontV=16,debljinaE=2,fontE=16)
Out[171]:
In [172]:
rucni_Dijkstra_digraf(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
Out[172]:
In [173]:
Dijkstra_digraf(digraf9,v1)
Out[173]:
In [174]:
stablo_min_putova_DSTG(digraf9,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D9pos,
velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
In [175]:
graphviz_stablo_min_putova(digraf9,v1,"D9dva.png",algoritam=Dijkstra_digraf,slika=(9,8),xy=D9pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontV=16,debljinaE=2,fontE=16)
Out[175]:
digraf10 - iako ima usmjereni ciklus negativne težine, Bellman-Ford radi ispravno iz vrha $v_1$ kao početnog vrha, zato jer se taj negativni ciklus ne može doseći iz vrha $v_1$ pa su rezultati točni i možemo garantirati njihovu točnost. I Dijkstra također radi ispravno iz vrha $v_1$, ali općenito ne možemo garantirati njegovu točnost.
In [176]:
digraf10=DiGraph({v1:{v4:1},
v2:{v1:1,v3:1},
v3:{v2:-2,v4:1}},weighted=True)
In [177]:
D10pos={v1:[0,2],v2:[4,3],v3:[7,3.5],v4:[1,0]}
In [178]:
rucni_BellmanFord(digraf10,v1,[v1,v2,v3,v4])
Out[178]:
In [179]:
BellmanFord(digraf10,v1)
Out[179]:
In [180]:
graphviz_stablo_min_putova(digraf10,v1,"D10.png",algoritam=BellmanFord,slika=(7,6),xy=D10pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v2,v3):10,(v3,v2):10,(v1,v4):8},kut={(v2,v3):-2,(v3,v2):-2,(v1,v4):-5})
Out[180]:
In [181]:
rucni_Dijkstra_digraf(digraf10,v1)
Out[181]:
In [182]:
Dijkstra_digraf(digraf10,v1)
Out[182]:
In [183]:
graphviz_stablo_min_putova(digraf10,v1,"D10dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D10pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v2,v3):10,(v3,v2):10,(v1,v4):8},kut={(v2,v3):-2,(v3,v2):-2,(v1,v4):-5})
Out[183]:
algoritam Dijkstra_graf primijenjen na težinski graf
In [184]:
var('A,B,C,D,E,F,G,H,I')
Out[184]:
In [185]:
graf=Graph({A:{B:5,C:2,D:4,E:10},
B:{D:8},
C:{E:7,F:5},
D:{E:6,G:2},
E:{F:3,G:2,H:3},
F:{H:2,I:4},
G:{H:3},
H:{I:5}
},weighted=True)
In [186]:
grafPOS={A:[-2,0],B:[-2,2],C:[-2,-2],D:[0,2],E:[0,0],F:[0,-2],G:[2,2],H:[2,0],I:[2,-2]}
In [187]:
rucni_Dijkstra_graf(graf,A,[A,B,C,D,E,F,G,H,I])
Out[187]:
In [188]:
Dijkstra_graf(graf,A)
Out[188]:
In [189]:
stablo_min_putova_DSTG(graf,A,algoritam=Dijkstra_graf,raspored_vrhova=grafPOS,velicina=300).show(figsize=[4,4])
In [190]:
graphviz_stablo_min_putova(graf,A,"tezinski.png",algoritam=Dijkstra_graf,xy=grafPOS,slika=(4,4),vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontE=16,debljinaE=1.5)
Out[190]:
Topološko sortiranje
In [191]:
acDigraf=DiGraph({2:[1,4],3:[1,4,5],4:[5],6:[1,4],7:[2,3,6,8],8:[5,6]})
In [192]:
acPOS={1:[0,0],2:[8,0],3:[2,-2],4:[6,-2],5:[4,-4],6:[2,2],7:[6,2],8:[4,4]}
In [193]:
acDigraf.show(pos=acPOS)
digraf jest aciklički
In [194]:
acDigraf.is_directed_acyclic()
Out[194]:
topološki sortirani vrhovi promatranog acikličkog digrafa
In [195]:
acDigraf.topological_sort()
Out[195]:
Jaka orijentacija
In [196]:
graf2=graphs.Grid2dGraph(3,3)
graf2.relabel()
In [197]:
graf2.show(save_pos=True,figsize=[3,3])
jedna jaka orijentacija na promatranom grafu
In [198]:
jaki_graf2=graf2.strong_orientation();jaki_graf2
Out[198]:
In [199]:
jaki_graf2.show(pos=graf2.get_pos(),figsize=[3,3])
jedna jaka orijentacija na kubnom grafu
In [200]:
kub=graphs.CubeGraph(3)
kub.relabel()
kub.strong_orientation().show(figsize=[3,3])
Transportne mreže
In [201]:
var('i u x v y w z p')
Out[201]:
In [202]:
mreza1=DiGraph({i:{u:7,x:2},u:{x:1,v:5},x:{y:4},
v:{x:3,y:2,w:4},y:{z:5},w:{z:3,p:3},
z:{p:6}},weighted=True)
In [203]:
mreza1_pos={i:[0,2],x:[2,0],y:[6,0],z:[10,0],p:[12,2],u:[2,4],v:[6,4],w:[10,4]}
In [204]:
mreza1.show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))
vrijednost maksimalnog protoka od izvora $i$ do ponora $p$
In [205]:
mreza1.flow(i,p)
Out[205]:
možemo dobiti i digraf u kojemu će težina luka biti količina protoka kroz pojedini luk. Ukoliko kroz neki luk nema protoka, taj luk se neće nacrtati.
In [206]:
mreza1.flow(i,p,value_only=False)
Out[206]:
In [207]:
mreza1.flow(i,p,value_only=False)[1].show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))
možemo dobiti potrebne informacije u obliku tablice ako definiramo svoju funkciju
In [208]:
def maksimalni_protok(mreza,v0,v1):
protok=mreza.flow(v0,v1,value_only=False)
lukovi=mreza.edges(labels=False)
lukovi2=protok[1].edges(labels=False)
kapacitet_luk=[]
protok_luk=[]
for e in lukovi:
kapacitet_luk.append(mreza.edge_label(e[0],e[1]))
if (e[0],e[1]) in lukovi2:
protok_luk.append(protok[1].edge_label(e[0],e[1]))
else:
protok_luk.append(0)
lukovi=['luk']+lukovi
kapacitet_luk=['kapacitet luka']+kapacitet_luk
protok_luk=['protok kroz luk']+protok_luk
tablica=[lukovi,kapacitet_luk,protok_luk]
tablica=map(list,zip(*tablica))
print "Vrijednost maksimalnog protoka: ", protok[0]
return table(tablica)
In [209]:
maksimalni_protok(mreza1,i,p)
Out[209]:
možemo općenito tražiti vrijednost maksimalnog protoka između bilo koja dva vrha koja nisu nužno izvor i ponor
In [210]:
mreza1.flow(i,v)
Out[210]:
In [211]:
maksimalni_protok(mreza1,i,v)
Out[211]:
In [212]:
mreza1.flow(u,z)
Out[212]:
In [213]:
maksimalni_protok(mreza1,u,z)
Out[213]:
od vrha $z$ do vrha $u$ ne postoji protok
In [214]:
mreza1.flow(z,u)
Out[214]:
In [215]:
maksimalni_protok(mreza1,z,u)
Out[215]:
minimalni $(i,p)$-rez
vrijednost minimalnog reza
In [216]:
mreza1.edge_cut(i,p,use_edge_labels=True)
Out[216]:
vrijednost minimalnog reza i bridovi iz tog reza
In [217]:
mreza1.edge_cut(i,p,use_edge_labels=True,value_only=False)
Out[217]:
vrijednost minimalnog reza, bridovi iz tog reza i particija vrhova
In [218]:
mreza1.edge_cut(i,p,use_edge_labels=True,vertices=True)
Out[218]:
Želimo li minimalni rez istaknuti na digrafu, definiramo svoju funkciju. Lukovi iz minimalnog reza su po defaultu obojani crvenom bojom (može se njihova boja po želji promijeniti), a vrhovi iz jedne particije su obojani žutom bojom, a iz druge particije svijetlo plavom bojom.
In [219]:
def minimalni_rez(mreza,v1,v2,metoda="FF",raspored_vrhova=None,laj="circular",brid="red",velicina=300):
rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
bridovi=map(lambda e: (e[0],e[1]),rez[1])
ostali_bridovi=list(set(mreza.edges(labels=False)).difference(set(bridovi)))
if raspored_vrhova==None:
slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},layout=laj,edge_labels=True,vertex_size=velicina)
else:
slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},pos=raspored_vrhova,edge_labels=True,vertex_size=velicina)
return slika
In [220]:
def graphviz_minimalni_rez(mreza,v1,v2,ime,metoda="FF",slika=None,fontV=12,fontE=12,debljinaV=1,debljinaE=1,xy=None,
vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",tezine=True,dekor=False,d={},kut={}):
"""Istice minimalni (v1,v2)-rez na transportnoj mrezi.
metoda='FF' -> rez se trazi Ford-Fulkersonovim algoritmom
metoda='LP' -> rez se trazi metodom linearnog programiranja
Slika se crta u graphviz formatu.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
xy -> rjecnik koordinata vrhova grafa G
vrh0 -> boja vrhova iz particije vrha v1
vrh1 -> boja vrhova iz particije vrha v2
brid0 -> boja bridova koji pripadaju minimalnom rezu
brid1 -> boja bridova koji ne pripadaju minimalnom rezu
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
bridovi=map(lambda e: (e[0],e[1]),rez[1])
bojeVrhova={}
for v in rez[2][0]:
bojeVrhova[v]=vrh0
for v in rez[2][1]:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in mreza.edges(labels=False):
if e in bridovi:
bojeBridova[e]=brid0
else:
bojeBridova[e]=brid1
rijec=graf_string(mreza,slika,fontV,fontE,xy,vrh1,brid1,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
In [221]:
minimalni_rez(mreza1,i,p,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
In [222]:
graphviz_minimalni_rez(mreza1,i,p,"mreza1.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
Out[222]:
minimalni $(u,z)$-rez
In [223]:
mreza1.edge_cut(u,z,use_edge_labels=True,vertices=True)
Out[223]:
In [224]:
minimalni_rez(mreza1,u,z,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
In [225]:
graphviz_minimalni_rez(mreza1,u,z,"mreza1dva.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
Out[225]:
još jedan primjer s drugom transportnom mrežom
In [226]:
mreza2=DiGraph({i:{A:3,C:2,E:6},A:{B:4},C:{D:2},
D:{p:4},E:{F:2,H:2},F:{B:2,G:1},
G:{p:5},H:{D:4,G:1},B:{p:6}},weighted=True)
In [227]:
mreza2_pos={i:[0,4],A:[2,8],B:[7,8],C:[2,0],D:[7,0],E:[3,4],F:[4.5,6.5],G:[6,4],H:[4.5,1.5],p:[10,4]}
In [228]:
mreza2.show(pos=mreza2_pos,edge_labels=True,vertex_size=500,figsize=(6,4),ymin=-0.1)
In [229]:
crtaj_graphviz(mreza2,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaVrha="khaki",bojaBrida="black",bojaTezine="blue",
fontV=24,fontE=24,debljinaE=2,d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})
Out[229]:
vrijednost maksimalnog protoka od izvora do ponora
In [230]:
mreza2.flow(i,p)
Out[230]:
količina protoka kroz pojedine lukove
In [231]:
maksimalni_protok(mreza2,i,p)
Out[231]:
minimalni $(i,p)$-rez
In [232]:
mreza2.edge_cut(i,p,use_edge_labels=True,vertices=True)
Out[232]:
In [233]:
minimalni_rez(mreza2,i,p,raspored_vrhova=mreza2_pos).show(figsize=[6,4])
In [234]:
graphviz_minimalni_rez(mreza2,i,p,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaTezine="blue",fontV=24,fontE=24,debljinaE=2,
d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})
Out[234]:
In [ ]: