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
import random
Funkcija struk daje struk grafa. Implementiran je algoritam koji se temelji na BFS algoritmu. Opis algoritma možete pronaći na moodlu na linku Računanje struka grafa.
def struk(G):
if G.number_of_selfloops()>0: return 1
if G.is_multigraph(): return 2
strukG=G.number_of_nodes()
parent={}
D={}
for v in G.nodes():
S=[]
R=[v]
parent[v]='null'
D[v]=0
while len(R)!=0:
x=R[0]
S.append(x)
del R[0]
for y in G.neighbors(x):
if y==parent[x]:
continue
if not(y in S):
parent[y]=x
D[y]=D[x]+1
R.append(y)
else:
strukG=min(strukG,D[x]+D[y]+1)
return strukG
Ovdje je implementiran jedan algoritam opisan u PDF-u Jedan algoritam za bridnu povezanost grafa za određivanje bridne povezanosti i minimalnog bridnog reza. Algoritam općenito radi na težinskim grafovima, a ukoliko je graf netežinski, algoritam na početku svim bridovima pridruži težinu 1. Implementacija radi na bilo kojem jednostavnom netežinskom ili težinskom grafu i također radi na bilo kojem (netežinskom) multigrafu.
def flatten(a):
for elem in a:
if type(elem) in (tuple,list):
for i in flatten(elem):
yield i
else:
yield elem
def pretvori(G):
if len(set(G.edges()))==len(G.edges()): return G
mul={}
bridovi=list(G.edges())
for (x,y) in bridovi:
mul[(x,y)]=bridovi.count((x,y))
H=nx.Graph(G)
for x in H.edges():
H[x[0]][x[1]]['weight']=mul[x]
return H
Krene se s proizvoljno odabranim vrhom a u grafu G1, a W je rječnik čiji ključevi su vrhovi grafa, a vrijednosti svih ključeva su postavljene na 0. Ovo je također pomoćna funkcija koja višestrukim izvođenjem unutar funkcije minimum_edge_cut dovodi do minimalnog bridnog reza.
def minimum_cut_phase(G1,W,a):
G=G1.copy()
V=G.nodes()
A=[a]
del W[a]
for k in W:
if G.get_edge_data(a,k):
W[k]+=G.get_edge_data(a,k)['weight']
while len(A)!=len(V):
m=max(W, key=W.get)
A.append(m)
del W[m]
for k in W:
if G.get_edge_data(m,k):
W[k]+=G.get_edge_data(m,k)['weight']
rez1=list(flatten([A[-1]]))
rez=[rez1,list(set(list(flatten(V))).difference(set(rez1)))]
tezina_reza = sum(list(map(lambda x: G[A[-1]][x]['weight'],list(G.neighbors(A[-1])))))
st=A[-2:]
if st[0] in G.neighbors(st[1]):
G.remove_edge(st[0],st[1])
susjedi=set(G.neighbors(st[0])).union(set(G.neighbors(st[1])))
presjek=set(G.neighbors(st[0])).intersection(set(G.neighbors(st[1])))
susjedi0=susjedi.difference(set(G.neighbors(st[1])))
susjedi1=susjedi.difference(set(G.neighbors(st[0])))
for x in susjedi:
if x in presjek:
tezina=G[x][st[0]]['weight']+G[x][st[1]]['weight']
G.add_weighted_edges_from([(x,tuple(st),tezina)])
if x in susjedi0:
tezina=G[x][st[0]]['weight']
G.add_weighted_edges_from([(x,tuple(st),tezina)])
if x in susjedi1:
tezina=G[x][st[1]]['weight']
G.add_weighted_edges_from([(x,tuple(st),tezina)])
G.remove_node(st[0])
G.remove_node(st[1])
return (tezina_reza,rez,G)
Funkcija minimum_edge_cut daje na izlazu uređenu trojku čija je prva komponenta minimalna težina bridnog reza, druga komponenta je pripadna particija vrhova grafa, a treća komponenta su pripadni bridovi koje treba ukloniti da graf postane nepovezan. Ukoliko je graf netežinski, tada je minimalna težina jednaka upravo minimalnom broju bridova koje treba ukloniti iz grafa da on postane nepovezan.
def minimum_edge_cut(G1):
G=G1.copy()
G=pretvori(G)
V=list(G.nodes())
E=list(G.edges())
nema_tezine=G[E[0][0]][E[0][1]]
if not(nema_tezine):
for x in E:
G[x[0]][x[1]]['weight']=1
minimalna_tezina=0
for b in E:
minimalna_tezina+=G[b[0]][b[1]]['weight']
a=random.choice(V)
W={}
for x in V:
W[x]=0
broj=len(V)
while broj>1:
rezultat=minimum_cut_phase(G,W,a)
if rezultat[0]<minimalna_tezina:
minimalni_rez=rezultat[1]
minimalna_tezina=rezultat[0]
G=rezultat[2]
W={}
for x in G.nodes():
W[x]=0
broj = len(G.nodes())
bridovi_minimalnog_reza = []
for u in minimalni_rez[0]:
for v in minimalni_rez[1]:
if (u,v) in G1.edges():
bridovi_minimalnog_reza.append((u,v))
return (minimalna_tezina, minimalni_rez, bridovi_minimalnog_reza)