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
PLATON = {'DODEKAEDAR':{0:[0, 2.466], 1:[-2.345, 0.762], 2:[-1.449, -1.995], 3:[1.449, -1.995], 19:[2.345, 0.762],
10:[0, 1.628], 8:[-1.548, 0.503], 6:[-0.957, -1.317], 4:[0.957, -1.317], 18:[1.548, 0.503],
9:[-0.7, 0.965], 11:[0.7, 0.965], 17:[1.134, -0.368], 5:[0, -1.192], 7:[-1.134, -0.368],
13:[-0.302, 0.416], 12:[0.302, 0.416], 16:[0.489, -0.159], 15:[0, -0.514], 14:[-0.489, -0.159]},
'IKOZAEDAR':{1:[0, -0.314], 10:[0, 3.602], 8:[0, -1.165], 4:[0, 0.78], 5:[0.272, 0.157], 6:[-0.272, 0.157],
7:[3.12, -1.801], 9:[-3.12, -1.801], 0:[0.675, -0.39], 2:[-0.675, -0.39], 11:[1.009, 0.583],3:[-1.009, 0.583]},
'OKTAEDAR':{0:[-0.316, 0.182], 1:[0.316, 0.182], 2:[0, -0.365], 3:[0, 1.385], 4:[-1.2, -0.693], 5:[1.2, -0.693]},
'KOCKA':{0:[-0.333, -0.333], 4:[-1, -1], 1:[-0.333, 0.333], 7:[-1, 1], 3:[0.333, -0.333], 5:[1, -1],
2:[0.333, 0.333], 6:[1, 1]},
'TETRAEDAR':{0:[-0.866, -0.5], 1:[0.866, -0.5], 2:[0, 1], 3:[0, 0]}}
Funkcija kromatski_broj određuje kromatski broj grafa. Implementacija se bazira na algoritmu opisanom na linku Zgodan algoritam za određivanje kromatskog broja grafa u moodlu.
def kromatski_broj(G):
H = G.copy()
while True:
nuH = H.number_of_nodes()
vrhoviH = list(H.nodes())
nesusjedni_vrhovi = []
for i in range(nuH):
for j in range(i+1,nuH):
if not((vrhoviH[i],vrhoviH[j]) in H.edges()):
nesusjedni_vrhovi.append((vrhoviH[i],vrhoviH[j]))
if len(nesusjedni_vrhovi) == 0:
return nuH
else:
broj_zajednickih_susjeda = -1
for par in nesusjedni_vrhovi:
br = len(set(H.neighbors(par[0])).intersection(set(H.neighbors(par[1]))))
if br > broj_zajednickih_susjeda:
broj_zajednickih_susjeda = br
par_vrhova = par
H = nx.contracted_nodes(H,*par_vrhova)
Funkcija bojanje_vrhova daje neko optimalno bojanje vrhova grafa. Ukoliko ne uspije pronaći optimalno bojanje, tada daje neko bojanje pri čemu javlja poruku da dobiveno bojanje nije optimalno. Parametri funkcije su sljedeći:
G - ulazni grafcheck - Provjerava ima li graf manje od 120 vrhova. Ukoliko graf ima više od 120 vrhova, funkcija prekida izvođenje. Ako ipak želimo pokrenuti funkciju na grafu s više od 120 vrhova, treba staviti check=False.odredi_KB - Po defaultu je odredi_KB=True, što znači da će se najprije odrediti kromatski broj grafa i nakon toga probati pronaći optimalno bojanje pohlepnim algoritmima. Zbog poznavanja kromatskog broja, na kraju ćemo znati je li dobiveno bojanje ujedno i optimalno. Ako je odredi_KB=False, tada se kromatski broj grafa neće određivati, nego će se odmah ići tražiti neko bojanje vrhova grafa pohlepnim algoritmima, jedino na kraju nećemo znati je li dobiveno bojanje optimalno ili nije. Ako se u razumnom vremenu kromatski broj ipak ne može odrediti, tada je bolje isključiti određivanje kromatskog broja i pronaći samo neko bojanje vrhova grafa.num - broj iteracija za traženje pohlepnog bojanja vrhova grafa slučajnim rasporedom vrhova. Kod traženja bojanja, funkcija najprije izvrši Brelazov algoritam i nakon toga još najviše num puta ponovi pohlepno bojanje sa slučajnim rasporedom vrhova. Na kraju vrati bojanje s najmanjim dobivenim brojem boja. Ukoliko je poznati kromatski broj, tada broj iteracija može biti i znatno manji od num ako je algoritam uspio ranije pronaći bojanje vrhova s brojem boja koji je jednak kromatskom broju grafa. Po defaultu je stavljeno num=2000.def bojanje_vrhova(G,num=2000,odredi_KB=True,check=True):
OPT = G.number_of_nodes()
if (check) and (OPT > 120):
return "Broj vrhova > 120. Stavi check=False ako ipak zelis probati."
if odredi_KB:
KR_BR = kromatski_broj(G)
bojanje = nx.greedy_color(G,'DSATUR')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == KR_BR:
return bojanje
else:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
bojanje = nx.greedy_color(G,'largest_first')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == KR_BR:
return bojanje
else:
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
for i in range(num):
bojanje = nx.greedy_color(G,'random_sequential')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == KR_BR:
return bojanje
else:
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
print('Bojanje koristi {} boja, a kromatski broj grafa je {}'.format(OPT,KR_BR))
return OPTIMALNO_BOJANJE
else:
bojanje = nx.greedy_color(G,'DSATUR')
BROJ_BOJA = max(bojanje.values()) + 1
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
bojanje = nx.greedy_color(G,'largest_first')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
for i in range(num):
bojanje = nx.greedy_color(G,'random_sequential')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
print('Dobiveno bojanje koristi {} boja i mozda nije optimalno.'.format(OPT))
return OPTIMALNO_BOJANJE
Funkcija obojani_vrhovi prikazuje obojane vrhove na grafu preko bojanja koje je dobiveno fukcijom bojanje_vrhova. Parametri funkcije su sljedeći:
G - ulazni grafraspored_vrhova - rječnik s koordinatama vrhovavelicina_vrha - veličina nacrtanog vrha. Po defaultu je stavljeno velicina_vrha=300.def obojani_vrhovi(G,raspored_vrhova,velicina_vrha=300):
bojanje = bojanje_vrhova(G)
br = max(bojanje.values())
cmap = matplotlib.cm.get_cmap('rainbow')
boje = [cmap(i/br) for i in range(br+1)]
boje_vrhova = []
for v in G.nodes():
boje_vrhova.append(boje[bojanje[v]])
nx.draw(G,pos=raspored_vrhova,node_size=velicina_vrha,edgecolors='k',with_labels=True,node_color=boje_vrhova)
def bojanje_vrha(graf,w,boje):
obojaniSusjedi=list(set(nx.neighbors(graf,w)).intersection(set(boje.keys())))
trazenjeBoje=[]
for u in obojaniSusjedi:
trazenjeBoje.append(boje[u])
if set(boje.values()).difference(set(trazenjeBoje))!=set([]):
boje[w]=min(set(boje.values()).difference(set(trazenjeBoje)))
else:
boje[w]=max(boje.values())+1
return None
def stupanj_zasicenosti(graf,w,boje):
obojaniSusjedi=list(set(nx.neighbors(graf,w)).intersection(set(boje.keys())))
brojBoja=len(set(map(lambda x:boje[x],obojaniSusjedi)))
return brojBoja
def Welsh_Powell(graf):
vrhovi=list(graf.nodes())
vrhovi_sorted=[]
while vrhovi != []:
D=max(dict(graf.degree(vrhovi)).values())
max_vrh=[]
for v in vrhovi:
if graf.degree(v)==D: max_vrh=max_vrh+[v]
random.shuffle(max_vrh)
vrhovi_sorted.extend(max_vrh)
vrhovi=list(set(vrhovi).difference(set(max_vrh)))
obojaniVrhovi=[vrhovi_sorted[0]]
boje={vrhovi_sorted[0]:1}
del vrhovi_sorted[0]
while vrhovi_sorted != []:
w = vrhovi_sorted[0]
bojanje_vrha(graf,w,boje)
obojaniVrhovi.append(w)
del vrhovi_sorted[0]
return (obojaniVrhovi, boje, len(set(boje.values())))
def Brelaz(graf):
vrhovi=list(graf.nodes())
D=max(dict(graf.degree()).values())
max_vrh=()
for v in vrhovi:
if graf.degree(v)==D: max_vrh=max_vrh+(v,)
v1=random.choice(max_vrh)
obojaniVrhovi=[v1]
boje={v1:1}
del vrhovi[vrhovi.index(v1)]
while vrhovi != []:
#racunanje stupnjeva zasicenosti
ds={}
for v in vrhovi:
ds[v]=stupanj_zasicenosti(graf,v,boje)
#izdvajanje vrhova s maksimalnim stupnjem zasicenosti
ds_max=max(ds.values())
ds_maxVrh=()
for v in ds:
if ds[v]==ds_max: ds_maxVrh=ds_maxVrh+(v,)
w=random.choice(ds_maxVrh)
#bojanje vrha s maksimlnim stupnjem zasicenosti
bojanje_vrha(graf,w,boje)
obojaniVrhovi.append(w)
del vrhovi[vrhovi.index(w)]
return (obojaniVrhovi, boje, len(set(boje.values())))
Funkcije bridno_kromatski_broj, bojanje_bridova i obojani_bridovi funkciniraju na isti način kao i odgovarajuće ranije opisane funkcije za bojanje vrhova tako da se primijene na linijski grafa zadanog grafa.
def bridno_kromatski_broj(G):
return kromatski_broj(nx.line_graph(G))
def bojanje_bridova(G,num=2000,odredi_BKB=True,check=True):
H = nx.line_graph(G)
OPT = H.number_of_nodes()
if (check) and (OPT > 120):
return "Broj bridova > 120. Stavi check=False ako ipak zelis probati."
if odredi_BKB:
BKR_BR = kromatski_broj(H)
bojanje = nx.greedy_color(H,'DSATUR')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == BKR_BR:
return bojanje
else:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
bojanje = nx.greedy_color(H,'largest_first')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == BKR_BR:
return bojanje
else:
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
for i in range(num):
bojanje = nx.greedy_color(H,'random_sequential')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA == BKR_BR:
return bojanje
else:
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
print('Bojanje koristi {} boja, a bridno kromatski broj grafa je {}'.format(OPT,BKR_BR))
return OPTIMALNO_BOJANJE
else:
bojanje = nx.greedy_color(H,'DSATUR')
BROJ_BOJA = max(bojanje.values()) + 1
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
bojanje = nx.greedy_color(H,'largest_first')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
for i in range(num):
bojanje = nx.greedy_color(H,'random_sequential')
BROJ_BOJA = max(bojanje.values()) + 1
if BROJ_BOJA < OPT:
OPT = BROJ_BOJA
OPTIMALNO_BOJANJE = bojanje
print('Dobiveno bojanje koristi {} boja i mozda nije optimalno.'.format(OPT))
return OPTIMALNO_BOJANJE
def obojani_bridovi(G,raspored_vrhova,velicina_vrha=300,boja_vrha='y',debljinaBrida=2):
bojanje = bojanje_bridova(G)
br = max(bojanje.values())
cmap = matplotlib.cm.get_cmap('rainbow')
boje = [cmap(i/br) for i in range(br+1)]
boje_bridova = []
for e in G.edges():
try:
boje_bridova.append(boje[bojanje[(e[0],e[1])]])
except:
boje_bridova.append(boje[bojanje[(e[1],e[0])]])
nx.draw(G,pos=raspored_vrhova,node_size=velicina_vrha,edgecolors='k',with_labels=True,node_color=boja_vrha,
edge_color=boje_bridova,width=debljinaBrida)
Funkcija raspored_termina formira raspored termina na temelju obojanih bridova u bibartitnom grafu. Parametri funkcije su sljedeći:
G - bipartitni grafstupac - lista naziva pojedinih termina koji će biti u prvom stupcu tablice rasporeda. Ova lista mora imati broj elemenata jednak bridno kromatskom broju grafa G.particija - ova varijabla može poprimiti jednu od dvije vrijednosti: 1 ili 2. Po defaultu ima vrijednost 1. Zapravo nam govori po kojoj particiji vrhova u bipartitnom grafu G želimo napraviti raspored, da li po prvoj ili po drugoj particiji vrhova. Koja particija vrhova je prva, a koja druga ovisi na kojem se mjestu nalazi u uređenom paru nx.bipartite.sets(G). To su zapravo vrhovi grafa G koje želimo imati u prvom retku tablice rasporeda.permutacija - ovo je lista svih prirodnih brojeva koji su manji ili jednaki od bridno kromatskog broja grafa G. Svaka boja brida predstavlja jedan termin. Boja $k$ predstavlja $k$-ti termin ukoliko je permutacija=None kako je i stavljeno po defaultu.permutacija i naglasimo. Na primjer, ako imamo ukupno 4 različita termina, tada na primjer permutacija=[3,2,4,1] znači da će boja 1 predstavljati treći termin, boja 2 predstavljat će drugi termin, boja 4 predstavljat će treći termin, boja 1 predstavljat će četvrti termin. Na ovom primjeru permutacija=None zapravo je isto što i permutacija=[1,2,3,4].def raspored_termina(G,stupac,particija=1,permutacija=None):
BR = bridno_kromatski_broj(G)
if len(stupac) != BR:
return "Error: Broj termina nije jednak bridno kromatskom broju grafa"
redak = list(nx.bipartite.sets(G)[particija-1])
bojanje = bojanje_bridova(G)
if permutacija == None:
permutacija = list(range(BR))
else:
permutacija = list(map(lambda x: x-1, permutacija))
tablica = [[" "]*len(redak) for _ in range(BR)]
for brid in bojanje:
if brid[0] in redak:
tablica[permutacija[bojanje[brid]]][redak.index(brid[0])] = brid[1]
else:
tablica[permutacija[bojanje[brid]]][redak.index(brid[1])] = brid[0]
for i in range(BR):
tablica[i] = [stupac[i]] + tablica[i]
tablica = [[" "]+redak] + tablica
tablica = make_table(tablica)
apply_theme('basic_both')
set_global_style(align='center')
return tablica
Funkcija random_maximal_matching na ulazu osim grafa G ima i neko sparivanje M1 u grafu G, a na izlazu vraća maksimalno sparivanje koje sadrži sparivanje M1. Po defaultu je stavljeno M1=[ ], tj. ako ništa posebno ne navedemo, algoritam kreće od praznog sparivanja. Ukoliko imamo želju da naše maksimalno sparivanje sadrži određene bridove, onda ih navedemo u listi M1 na ulazu algoritma. Naravno, funkcija random_maximal_matching prije nego što krene tražiti maksimalno sparivanje koje sadrži sparivanje M1, provjerava da li je M1 zaista sparivanje u grafu G. Ukoliko nije, na izlazu vraća određenu poruku. Algoritam je i randomiziran tako da u svakom koraku na slučajni način bira neki od još neprovjerenih bridova.
def random_maximal_matching(G,M1=[]):
M = M1[:]
bridovi=list(G.edges())
provjera=[]
if M!=[]:
for (u,v) in M:
if not((u,v) in bridovi):
return "Error: U sparivanju M su nepostojeci bridovi."
for (u,v) in M:
if ((u in provjera) or (v in provjera)):
return "Error: M nije sparivanje u grafu G."
else:
provjera.extend([u,v])
bridovi=list(set(bridovi).difference(set(M)))
while bridovi != []:
b=random.choice(bridovi)
if not((b[0] in provjera) or (b[1] in provjera)):
M.append(b)
provjera.extend([b[0],b[1]])
bridovi.remove(b)
return M
def najvece_sparivanje_graf(G,raspored_vrhova,velicina_vrha=300,boja_vrha='y',debljinaBrida=7,bojaBrida='b',slika=[0.2,0.2]):
sparivanje = nx.max_weight_matching(G, maxcardinality=True)
plt.margins(x=slika[0],y=slika[1])
plt.axis('off')
nx.draw_networkx_nodes(G,pos=raspored_vrhova,node_size=velicina_vrha,node_color=boja_vrha,edgecolors='k')
nx.draw_networkx_edges(G,pos=raspored_vrhova,width=debljinaBrida,edgelist=sparivanje,edge_color=bojaBrida,alpha=0.5)
nx.draw_networkx_edges(G,pos=raspored_vrhova)
nx.draw_networkx_labels(G,pos=raspored_vrhova)
random_maximal_matchingUnaprijed zadani bridovi su u crvenoj boji, a dodani bridovi u plavoj boji. Mogu se te boje promijeniti pomoću parametara bojaBridaM i bojaBrida.
def maksimalno_sparivanje_graf(G,raspored_vrhova,M=[],velicina_vrha=300,boja_vrha='y',debljinaBrida=7,bojaBridaM='r',
bojaBrida='b',slika=[0.2,0.2]):
sparivanje = random_maximal_matching(G,M)
if M != []:
sparivanje = list(set(sparivanje).difference(set(M)))
plt.margins(x=slika[0],y=slika[1])
plt.axis('off')
nx.draw_networkx_nodes(G,pos=raspored_vrhova,node_size=velicina_vrha,node_color=boja_vrha,edgecolors='k')
nx.draw_networkx_edges(G,pos=raspored_vrhova,width=debljinaBrida,edgelist=sparivanje,edge_color=bojaBrida,alpha=0.5)
nx.draw_networkx_edges(G,pos=raspored_vrhova,width=debljinaBrida,edgelist=M,edge_color=bojaBridaM,alpha=0.5)
nx.draw_networkx_edges(G,pos=raspored_vrhova)
nx.draw_networkx_labels(G,pos=raspored_vrhova)