Ovdje je implementirano nekoliko dodatnih funkcija za lakši i brži rad u pythonu.
Funkcije se nalaze u datoteci DSTG.py.
import networkx as nx
from ipy_table import *
import numpy as np
import matplotlib.pyplot as plt
import pylab
import random
import os
from IPython.core.display import Image
def BellmanFord(D,v0,v1=None):
"""Bellman-Fordov algoritam za najkrace putove u tezinskom digrafu D od vrha v0.
Ako digraf ima usmjereni ciklus negativne tezine koji se moze doseci iz vrha v0,
tada algoritam vraca error.
Ako je v1=None, na izlazu se daje uredjeni par od dva rjecnika. U prvom rjecniku su
dane udaljenosti pojedinih vrhova od vrha v0, a u drugom neposredni prethodnici
pojedinih vrhova na najkracem putu od vrha v0.
U protivnom se daje najkraci put izmedju vrhova v0 i v1 ukoliko postoji."""
tezina_brida={}
for e in D.edges(data=True):
if e[2]!={}:
tezina_brida[(e[0],e[1])]=e[2]['weight']
else:
tezina_brida[(e[0],e[1])]=1
P = {}
udaljenost = {}
V = D.nodes()
E = D.edges()
udaljenost[0]={}
for v in V:
if v == v0:
udaljenost[0][v] = 0
P[v] = None
else:
udaljenost[0][v] = np.inf
P[v] = None
for i in range(1, len(V)+1):
udaljenost[i]=udaljenost[i-1].copy()
promjena=False
for v in V:
for u in D.predecessors(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")
if v1==None: return (udaljenost[len(udaljenost)-1], P)
v=v1
min_put=[v1]
while v!=v0 and v!=None:
v=P[v]
min_put=[v]+min_put
if v==None:
return []
else:
return min_put
def Dijkstra_digraf(D,v0,v1=None):
"""Poboljsana verzija Dijkstrinog algoritma za najkrace putove u tezinskom digrafu D od vrha v0.
Ako digraf ima i negativnih tezina, tada algoritam vraca error.
Ako je v1=None, na izlazu se daje uredjeni par od dva rjecnika. U prvom rjecniku su dane
udaljenosti pojedinih vrhova od vrha v0, a u drugom neposredni prethodnici pojedinih vrhova
na najkracem putu od vrha v0.
U protivnom se daje najkraci put izmedju vrhova v0 i v1 ukoliko postoji."""
MM=min(map(lambda x: x[2]['weight'],D.edges(data=True)))
tezina_brida={}
for e in D.edges(data=True):
if e[2]!={}:
tezina_brida[(e[0],e[1])]=e[2]['weight']
else:
tezina_brida[(e[0],e[1])]=1
P={}
udaljenost={}
Q=set(D.nodes())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=np.inf
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == np.inf: break
v=random.choice(list(filter(lambda x: udaljenost[x]==m, Q)))
Q.remove(v)
for u in set(D.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 tezinama")
if v1==None: return (udaljenost,P)
v=v1
min_put=[v1]
while v!=v0 and v!=None:
v=P[v]
min_put=[v]+min_put
if v==None:
return []
else:
return min_put
def rucni_BellmanFord(D,v0,poredak=None):
"""Na izlazu daje tablicu kakva se dobiva kod rucnog provodjenja
Bellman-Fordovog algoritma na tezinskom digrafu s pocetnim vrhom v0.
Opcija poredak=None daje poredak vrhova u tablici kako se oni javljaju u listi
D.nodes(), a ako zelimo neki drugi poredak, onda mozemo sami navesti listu sa
zeljenim poretkom."""
koraci={}
if poredak==None:
V=list(D.nodes())
else:
V=poredak
tezina_brida={}
for e in D.edges(data=True):
tezina_brida[(e[0],e[1])]=e[2]['weight']
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',np.inf)
for i in range(1,len(V)+1):
koraci[i]=koraci[i-1].copy()
promjena=False
for v in V:
for u in D.predecessors(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 range(len(koraci)):
redak=[str(i)]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=to_latex_dijkstra(list(map(list,zip(*tablica))))
tablica=make_table(tablica)
apply_theme('basic_both')
set_global_style(align='center')
if koraci[len(koraci)-1]!=koraci[len(koraci)-2]: print("error: digraf ima negativne cikluse")
return tablica
def rucni_Dijkstra_digraf(D,v0,poredak=None):
"""Na izlazu daje tablicu kakva se dobiva kod rucnog provodjenja poboljsane verzije
Dijkstrinog algoritma na tezinskom digrafu s pocetnim vrhom v0.
Opcija poredak=None daje poredak vrhova u tablici kako se oni javljaju u listi
D.nodes(), a ako zelimo neki drugi poredak, onda mozemo sami navesti listu sa
zeljenim poretkom."""
if poredak==None:
V=list(D.nodes())
else:
V=poredak
koraci={}
tezina_brida={}
for e in D.edges(data=True):
tezina_brida[(e[0],e[1])]=e[2]['weight']
MM=min(map(lambda x: x[2]['weight'],D.edges(data=True)))
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',np.inf)
Q=set(D.nodes())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==np.inf:
break
else:
koraci[k]=koraci[k-1].copy()
w=random.choice(list(filter(lambda x: koraci[k-1][x][1]==m, Q)))
Q.remove(w)
koraci[k][w]='*****'
for v in set(D.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 range(len(koraci)):
redak=[str(i)]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=to_latex_dijkstra(list(map(list,zip(*tablica))))
tablica=make_table(tablica)
apply_theme('basic_both')
set_global_style(align='center')
if MM<0: print("error: Dijkstra ne radi ispravno na negativnim tezinama")
return tablica
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 networkx 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="{},{}!"\n '.format(*slika)
rijec+='node [shape=circle width=0 height=0 margin=0 style=filled fontsize={} penwidth={}];\n '.format(fontV,debljinaV)
if dekor:
rijec+='edge[color={},fontcolor={} overlap=false splines=true decorate=true fontsize={} penwidth={}];\n '.format(
bojaBrida,bojaTezine,fontE,debljinaE)
else:
rijec+='edge[color={},fontcolor={} overlap=false splines=true,fontsize={} penwidth={}];\n '.format(
bojaBrida,bojaTezine,fontE,debljinaE)
if bojeVrhova==None:
bojeVrhova={}
for v in G.nodes():
bojeVrhova[v]=bojaVrha
if xy!=None:
for v in G.nodes():
rijec+='"{}" [label="{}" pos="{},{}!" fillcolor={}];\n '.format(v,v,xy[v][0],xy[v][1],bojeVrhova[v])
else:
for v in G.nodes():
rijec+='"{}" [label="{}" style=filled fillcolor={}];\n '.format(v,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+='"{}" -{} "{}" [color={}];\n '.format(e[0],strelica,e[1],bojeBridova[(e[0],e[1])])
if tezine==True:
if d=={}:
for e in G.edges(data=True):
rijec+='"{}" -{} "{}" [color={} label="{}"];\n '.format(e[0],strelica,e[1],bojeBridova[(e[0],e[1])],e[2]['weight'])
else:
for e in G.edges(data=True):
if (e[0],e[1]) in d.keys():
rijec+='"{}" -{} "{}" [color={} headlabel="{}" labeldistance={} labelangle={}];\n '.format(e[0],strelica,
e[1],bojeBridova[(e[0],e[1])],e[2]['weight'],d[(e[0],e[1])],kut[(e[0],e[1])])
else:
rijec+='"{}" -{} "{}" [color={} label="{}"];\n '.format(
e[0],strelica,e[1],bojeBridova[(e[0],e[1])],e[2]['weight'])
rijec+='}'
return rijec
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 networkx 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 '{}' | dot -Kfdp -Tpng > {}".format(rijec,ime))
return Image(filename=ime)
def graphviz_najkraci_put(D,v1,v2,ime,algoritam=BellmanFord,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 najkraci put od vrha v1 do vrha v2 u tezinskom digrafu (ili grafu) D 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
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
xy -> rjecnik koordinata vrhova grafa G
vrh0 -> boja vrhova v1 i v2
vrh1 -> boja preostalih vrhova
brid0 -> boja bridova koji pripadaju najkracem putu
brid1 -> boja bridova koji ne pripadaju najkracem putu
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"""
put=algoritam(D,v1,v2)
ostali_vrhovi=list(set(D.nodes()).difference(set([v1,v2])))
bridovi_put=[]
for i in range(len(put)-1):
bridovi_put.append((put[i],put[i+1]))
bojeVrhova={v1:vrh0,v2:vrh0}
for v in ostali_vrhovi:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in D.edges():
if ((e[0],e[1]) in bridovi_put) or ((e[1],e[0]) in bridovi_put):
bojeBridova[e]=brid0
else:
bojeBridova[e]=brid1
rijec=graf_string(D,slika,fontV,fontE,xy,vrh1,brid1,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '{}' | dot -Kfdp -Tpng > {}".format(rijec,ime))
return Image(filename=ime)
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 P[x]!=None: bridovi.append((P[x],x))
ostali_vrhovi=list(D.nodes())
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) or ((e[1],e[0]) in bridovi):
bojeBridova[e]=brid0
else:
bojeBridova[e]=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)
def usmjereni_ciklus(D):
"""Daje neki usmjereni ciklus u digrafu ukoliko digraf nije aciklicki.
Zapravo je implementiran Brentov algoritam na nacin da ako vise
puta primijenimo algoritam na istom digrafu, opcenito ce se dobiti
na izlazu razliciti usmjereni ciklusi."""
if nx.is_directed_acyclic_graph(D): return "nema usmjerenih ciklusa"
x0 = random.choice(list(D.nodes()))
f = {}
for v in D.nodes():
f[v] = random.choice(list(D.neighbors(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 range(lam):
hare = f[hare]
while tortoise != hare:
tortoise = f[tortoise]
hare = f[hare]
mu += 1
ciklus=[tortoise]
for i in range(lam):
tortoise=f[tortoise]
ciklus.append(tortoise)
return ciklus
def graphviz_usmjereni_ciklus(D,ime,slika=None,fontV=12,fontE=12,debljinaV=1,debljinaE=1,xy=None,vrh0="yellow",vrh1="pink",
brid0="red",brid1="black",bojaTezine="black",tezine=False,dekor=False,d={},kut={}):
"""Istice neki usmjereni ciklus u tezinskom digrafu (ili grafu) D na
kojeg je primijenjen Brentov algoritam.
Brentov algoritam je implementiran na nacin da ako vise
puta primijenimo algoritam na istom digrafu, opcenito ce se dobiti
na izlazu razliciti usmjereni ciklusi.
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
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
xy -> rjecnik koordinata vrhova grafa G
vrh0 -> boja vrhova u usmjerenom ciklusu
vrh1 -> boja preostalih vrhova
brid0 -> boja bridova koji pripadaju usmjerenom ciklusu
brid1 -> boja bridova koji ne pripadaju usmjerenom ciklusu
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"""
ciklus=usmjereni_ciklus(D)
bridovi_ciklus=[]
for i in range(len(ciklus)-1):
bridovi_ciklus.append((ciklus[i],ciklus[i+1]))
bojeVrhova={}
for v in D.nodes():
if v in ciklus:
bojeVrhova[v]=vrh0
else:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in D.edges():
if e in bridovi_ciklus:
bojeBridova[e]=brid0
else:
bojeBridova[e]=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)
def snaga_vrha(T,v0):
indeks=list(T.nodes()).index(v0)
matrica=nx.adj_matrix(T)+nx.adj_matrix(T)**2
return int(matrica[indeks].sum())
def rang_lista(turnir,izlaz="html"):
rezultat1=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.nodes())
rezultat1=sorted(rezultat1,key=lambda x: x[2],reverse=True)
rezultat=list(map(lambda v: [str(v[0]),str(v[1]),str(v[2])],rezultat1))
if izlaz == "lista":
return rezultat1
elif izlaz == "html":
rezultat=[['igraci','broj pobjeda','snaga pobjeda']]+rezultat
tablica = make_table(rezultat)
apply_theme('basic_both')
set_global_style(align='center')
return tablica
def dfs_graf(G,v0):
V=list(G.nodes())
V.remove(v0)
vrhovi=[v0]+V
d={}
f={}
P={}
color={}
tree_edges=[]
back_edges=[]
for u in vrhovi:
color[u]="WHITE"
P[u]=None
time=0
for u in vrhovi:
if color[u]=="WHITE":
S=[u]
while S!=[]:
x=S[-1]
del S[-1]
if color[x]=="WHITE":
time+=1
d[x]=time
color[x]="GRAY"
S.append(x)
for v in G.neighbors(x):
if color[v]=="WHITE":
P[v]=x
S.append(v)
elif color[x]=="GRAY":
time+=1
f[x]=time
color[x]="BLACK"
redoslijed_vrhova=sorted(G.nodes(),key=lambda x: d[x])
tree_edges=[]
for u in redoslijed_vrhova:
if P[u]!=None:
tree_edges.append((u,P[u]))
back_edges=[]
for (u,v) in G.edges():
if ((u,v) in tree_edges) or ((v,u) in tree_edges):
pass
else:
back_edges.append((u,v))
return (redoslijed_vrhova,d,f,P,tree_edges,back_edges)
def DFS_orijentacija(G,v0):
"""Daje orijentaciju grafa G na temelju DFS algoritma koji je poceo
s vrhom v0. Ukoliko graf nema reznih bridova, tada je dobivena
ujedno i jaka orijentacija na grafu G. Na izlazu se daje digraf."""
D=nx.DiGraph()
lukovi=[]
vrijeme=dfs_graf(G,v0)[1]
bridoviDFS=dfs_graf(G,v0)[4]
for e in G.edges():
if ((e[0],e[1]) in bridoviDFS) or ((e[1],e[0]) in bridoviDFS):
if vrijeme[e[0]]<vrijeme[e[1]]:
lukovi.append((e[0],e[1]))
else:
lukovi.append((e[1],e[0]))
else:
if vrijeme[e[0]]<vrijeme[e[1]]:
lukovi.append((e[1],e[0]))
else:
lukovi.append((e[0],e[1]))
D.add_edges_from(lukovi)
return D
def to_latex_protok(tablica):
"""Pomocna funkcija za latex prikaz tablice kod rucnih prikaza protoka."""
for i in range(len(tablica)):
for j in range(len(tablica[0])):
if type(tablica[i][j]) in (int,str):
pass
else:
tablica[i][j] = '$(\\text{'+str(tablica[i][j][0])+'},\\text{'+str(tablica[i][j][1])+'})$'
return tablica
def maksimalni_protok(mreza,v0,v1,kapacitet='weight'):
protok=nx.maximum_flow(mreza,v0,v1,capacity=kapacitet)
kapacitet_luk=[]
protok_luk=[]
for e in mreza.edges(data=True):
kapacitet_luk.append(str(e[2][kapacitet]))
protok_luk.append(str(protok[1][e[0]][e[1]]))
lukovi=['luk']+list(mreza.edges())
kapacitet_luk=['kapacitet luka']+kapacitet_luk
protok_luk=['protok kroz luk']+protok_luk
tablica=[lukovi,kapacitet_luk,protok_luk]
tablica=to_latex_protok(list(map(list,zip(*tablica))))
tablica=make_table(tablica)
apply_theme('basic_both')
set_global_style(align='center')
print("Vrijednost maksimalnog protoka: ", protok[0])
return tablica
def minimalni_rez(mreza,i,p,kapacitet='weight'):
rez=nx.minimum_cut(mreza,i,p,capacity=kapacitet)[1]
bridovi_rez=[]
for u in rez[0]:
for v in rez[1]:
if (u,v) in mreza.edges():
bridovi_rez.append((u,v))
return {'particija':(rez[0],rez[1]),'bridovi':bridovi_rez}
def graphviz_minimalni_rez(D,v1,v2,ime,kapacitet='weight',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 u transportnoj mrezi D.
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
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
xy -> rjecnik koordinata vrhova grafa G
vrh0 -> boja vrhova u clanu particije u kojemu je vrh v1
vrh1 -> boja vrhova u clanu particije u kojemu je vrh 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"""
particija=minimalni_rez(D,v1,v2,kapacitet)
bojeVrhova={}
for v in particija['particija'][0]:
bojeVrhova[v]=vrh0
for v in particija['particija'][1]:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in D.edges():
if e in particija['bridovi']:
bojeBridova[e]=brid0
else:
bojeBridova[e]=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)