Svojstva grafova u pythonu
In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
In [3]:
platform.python_version()
Out[3]:
In [4]:
import networkx as nx
In [5]:
nx.__version__
Out[5]:
In [6]:
from pylab import *
In [7]:
%matplotlib inline
In [8]:
import DSTG
In [9]:
from IPython.core.display import Image
In [10]:
P=nx.petersen_graph()
poz=nx.shell_layout(P,[[5,6,7,8,9],[0,1,2,3,4]])
nx.draw(P,pos=poz,with_labels=True)
Tri načina spremanja grafa u datoteku¶
In [11]:
nx.write_adjlist(P,"petersen.adjlist")
In [12]:
nx.write_edgelist(P,"petersen.edgelist")
In [13]:
nx.write_multiline_adjlist(P,"petersen.multiadjlist")
Sadržaji pojedinih datoteka¶
In [14]:
dat=open("petersen.adjlist",'r')
d1=dat.read()
dat.close()
dat=open("petersen.edgelist",'r')
d2=dat.read()
dat.close()
dat=open("petersen.multiadjlist",'r')
d3=dat.read()
dat.close()
In [15]:
print(d1)
In [16]:
print(d2)
In [17]:
print(d3)
Učitavanje grafa iz datoteke¶
In [18]:
Z1=nx.read_adjlist("petersen.adjlist")
Z2=nx.read_edgelist("petersen.edgelist")
Z3=nx.read_multiline_adjlist("petersen.multiadjlist")
Gornje funkcije imaju i neke dodatne parametre. Npr., create_using govori kakvu vrstu grafa treba napraviti (graf, multigraf, digraf, multidigraf).Po defaultu je create_using=nx.Graph()
In [19]:
Z1=nx.read_adjlist("petersen.adjlist",create_using=nx.Graph())
In [20]:
Z1
Out[20]:
In [21]:
Z2
Out[21]:
In [22]:
Z3
Out[22]:
Primjer za multigraf
In [23]:
bridovi=[(0,0),(0,1),(0,1),(0,3),(0,3),(0,4),(1,1),
(1,2),(1,2),(1,4),(2,2),(2,3),(2,3),(2,4),
(3,3),(3,4)]
In [24]:
Z=nx.from_edgelist(bridovi,create_using=nx.MultiGraph())
In [25]:
nx.write_adjlist(Z,"multigraf.adjlist")
nx.write_edgelist(Z,"multigraf.edgelist")
nx.write_multiline_adjlist(Z,"multigraf.multiadjlist")
In [26]:
dat=open("multigraf.adjlist",'r')
m1=dat.read()
dat.close()
dat=open("multigraf.edgelist",'r')
m2=dat.read()
dat.close()
dat=open("multigraf.multiadjlist",'r')
m3=dat.read()
dat.close()
In [27]:
print(m1)
In [28]:
print(m2)
In [29]:
print(m3)
Učitavanje multigrafa iz neke od gornjih datoteka
In [30]:
G1=nx.read_adjlist("multigraf.adjlist",create_using=nx.MultiGraph())
In [31]:
G1viz=nx.nx_agraph.to_agraph(G1)
In [32]:
G1viz.draw('G1.png',prog='dot')
In [33]:
Image(filename='G1.png')
Out[33]:
Učitavanje grafova iz datoteka s kojima ćemo dalje raditi¶
GRAF 1¶
Učitavanje grafa iz datoteke i pretvaranje njegovih vrhova u tip integer
In [34]:
graf1=nx.read_adjlist("graf1.adjlist",nodetype=int)
vrhovi grafa su cijeli brojevi
In [35]:
graf1.nodes()
Out[35]:
sadrzaj datoteke graf1.adjlist
In [36]:
datoteka1=open("graf1.adjlist")
print(datoteka1.read())
datoteka1.close()
crtanje grafa s eksplicitnim postavkama vrhova
In [37]:
pozicije1={1:(0,2),2:(0,0),3:(2,2),4:(1,1),5:(2,0),6:(3,1)}
nx.draw(graf1,pos=pozicije1,with_labels=True)
Učitavanje prethodnog grafa iz datoteke, ali bez pretvaranja vrhova u tip integer. Vrhovi će biti tipa string.
In [38]:
graf1str=nx.read_adjlist("graf1.adjlist")
In [39]:
graf1str.nodes()
Out[39]:
In [40]:
pozicije1str={'1':(0,2),'2':(0,0),'3':(2,2),'4':(1,1),'5':(2,0),'6':(3,1)}
nx.draw(graf1str,pos=pozicije1str,with_labels=True)
GRAF 2¶
učitavanje multigrafa iz datoteke i pretvaranje vrhova u tip integer
In [41]:
graf2=nx.read_adjlist("graf2.adjlist",create_using=nx.MultiGraph(),nodetype=int)
vrhovi grafa su cijeli brojevi
In [42]:
graf2.nodes()
Out[42]:
bridovi
In [43]:
graf2.edges()
Out[43]:
sadržaj datoteke graf2.adjlist
In [44]:
datoteka2=open("graf2.adjlist")
print(datoteka2.read())
datoteka2.close()
In [45]:
graf2viz=nx.nx_agraph.to_agraph(graf2)
graf2viz.draw('G2.png',prog='circo')
Image(filename='G2.png')
Out[45]:
GRAF 3¶
učitavanje multigrafa iz datoteke i pretvaranje vrhova u tip integer
In [46]:
graf3=nx.read_adjlist("graf3.adjlist",nodetype=int)
sadržaj datoteke graf3.adjlist
In [47]:
datoteka3=open("graf3.adjlist")
print(datoteka3.read())
datoteka3.close()
In [48]:
pozicije3={1:(0,2),2:(2,2),3:(4,2),4:(4,0),5:(2,0),6:(0,0),7:(-0.5,1),8:(4.5,1)}
nx.draw(graf3,pos=pozicije3,with_labels=True)
Je li graf prazan?¶
grafovi graf1, graf2 i graf3 nisu prazni jer svaki od njih ima barem jedan brid
In [49]:
graf1.number_of_edges(),graf2.number_of_edges(),graf3.number_of_edges()
Out[49]:
možemo definirati svoju funkciju koja će vraćati True ako je graf prazan, a u protivnom False
In [50]:
def EmptyQ(G):
if G.number_of_edges()==0:
return True
else:
return False
In [51]:
EmptyQ(graf1),EmptyQ(graf2),EmptyQ(graf3)
Out[51]:
Ima li graf petlji?¶
grafovi graf1, graf2 i graf3 nemaju petlji
In [52]:
graf1.number_of_selfloops(),graf2.number_of_selfloops(),graf3.number_of_selfloops()
Out[52]:
Multigraf¶
grafovi graf1 i graf3 nisu multigrafovi, a graf2 jest
In [53]:
graf1.is_multigraph(),graf2.is_multigraph(),graf3.is_multigraph()
Out[53]:
Je li graf usmjeren?¶
graf1, graf2 i graf3 su neusmjereni grafovi
In [54]:
graf1.is_directed(),graf2.is_directed(),graf3.is_directed()
Out[54]:
Je li graf bipartitan?¶
graf1, graf2 i graf3 nisu bipartitni grafovi
In [55]:
nx.is_bipartite(graf1),nx.is_bipartite(graf2),nx.is_bipartite(graf3)
Out[55]:
kubični graf jest bipartitan
In [56]:
nx.is_bipartite(nx.cubical_graph())
Out[56]:
biparticija kubičnog grafa
In [57]:
nx.bipartite.sets(nx.cubical_graph())
Out[57]:
želimo li biparticije u obliku liste
In [58]:
skup=nx.bipartite.sets(nx.cubical_graph())
lista1=[x for x in skup[0]]
lista2=[x for x in skup[1]]
In [59]:
lista1,lista2
Out[59]:
Je li graf povezan?¶
graf1, graf2 i graf3 su povezani grafovi
In [60]:
nx.is_connected(graf1),nx.is_connected(graf2),nx.is_connected(graf3)
Out[60]:
broj povezanih komponenti u grafu¶
In [61]:
nx.number_connected_components(graf1),nx.number_connected_components(graf2),nx.number_connected_components(graf3)
Out[61]:
In [62]:
G=nx.complete_graph(5)
H=nx.complete_bipartite_graph(2,3)
U=nx.disjoint_union(G,H)
In [63]:
nx.draw_circular(U,with_labels=True)
In [64]:
nx.number_connected_components(U)
Out[64]:
komponente povezanosti grafa (vrhovi iz iste komponente)¶
In [65]:
list(nx.connected_components(U))
Out[65]:
In [66]:
list(nx.connected_components(graf1))
Out[66]:
komponente povezanosti grafa (svaka komponenta kao zasebni graf)¶
In [67]:
V=list(nx.connected_component_subgraphs(U))
prva komponenta povezanosti
In [68]:
nx.draw(V[0],with_labels=True)
druga komponenta povezanosti
In [69]:
nx.draw(V[1],with_labels=True)
Je li graf potpun?¶
definiramo svoju funkciju
In [70]:
def CompleteQ(G):
if G.number_of_selfloops()>0: return False
if len(set(G.edges()))!=G.number_of_edges(): return False
if G.number_of_edges()!=(G.number_of_nodes()**2-G.number_of_nodes())/2:
return False
else:
return True
In [71]:
CompleteQ(graf1),CompleteQ(graf2),CompleteQ(graf3)
Out[71]:
In [72]:
CompleteQ(nx.petersen_graph()),CompleteQ(nx.complete_graph(8))
Out[72]:
In [73]:
graf4=nx.read_adjlist("graf4.adjlist",create_using=nx.MultiGraph(),nodetype=int)
In [74]:
graf4viz=nx.nx_agraph.to_agraph(graf4)
graf4viz.draw('G4.png',prog='circo')
Image(filename='G4.png')
Out[74]:
In [75]:
CompleteQ(graf4)
Out[75]:
Je li graf jednostavan?¶
definiramo svoju funkciju
In [76]:
def SimpleQ(G):
if G.number_of_selfloops()>0: return False
if len(set(G.edges()))!=G.number_of_edges():
return False
else:
return True
In [77]:
SimpleQ(graf1),SimpleQ(graf2),SimpleQ(graf3),SimpleQ(graf4),SimpleQ(nx.petersen_graph())
Out[77]:
Je li graf regularan?¶
ukoliko je graf regularan funkcija vraća True i stupanj regularnosti, a u protivnom vraća samo False
In [78]:
list(dict(graf1.degree()).values())
Out[78]:
In [79]:
def RegularQ(G):
if len(list(dict(graf1.degree()).values()))==1:
return (True,G.degree().values()[0])
else:
return False
In [80]:
RegularQ(graf1),RegularQ(graf2),RegularQ(graf3),RegularQ(graf4),RegularQ(nx.complete_graph(8)),RegularQ(nx.petersen_graph())
Out[80]:
Je li graf aciklički?¶
In [81]:
def AcyclicQ(G):
if G.number_of_edges()==G.number_of_nodes()-nx.number_connected_components(G):
return True
else:
return False
In [82]:
AcyclicQ(graf1), AcyclicQ(graf2), AcyclicQ(graf3), AcyclicQ(nx.path_graph(7))
Out[82]:
Je li graf stablo?¶
In [83]:
def TreeQ(G):
if nx.number_connected_components(G)==1 and G.number_of_edges()==G.number_of_nodes()-1:
return True
else:
return False
In [84]:
TreeQ(graf1),TreeQ(graf2),TreeQ(graf3),TreeQ(nx.star_graph(5))
Out[84]:
Je li graf Eulerov?¶
In [85]:
nx.is_eulerian(graf1), nx.is_eulerian(graf2), nx.is_eulerian(graf3)
Out[85]:
In [86]:
nx.is_eulerian(nx.complete_graph(11)), nx.is_eulerian(nx.complete_graph(10))
Out[86]:
Eulerova tura u grafu graf3¶
In [87]:
DSTG.ispis(list(nx.eulerian_circuit(graf3)),80)
susjedni vrhovi nekog vrha u grafu¶
susjedni vrhovi vrha 2 u grafu graf1
In [88]:
list(graf1.neighbors(2))
Out[88]:
In [89]:
[n for n in graf1.neighbors(2)]
Out[89]:
susjedni vrhovi vrha 4 u grafu graf3
In [90]:
list(graf3.neighbors(4))
Out[90]:
In [91]:
[n for n in graf3.neighbors(4)]
Out[91]:
udaljenost dva vrha u grafu¶
In [92]:
nx.shortest_path_length(graf2,3,1)
Out[92]:
In [93]:
nx.shortest_path_length(graf2,2,5)
Out[93]:
Najkraći put između dva vrha u grafu¶
In [94]:
nx.shortest_path(graf2,3,1)
Out[94]:
In [95]:
nx.shortest_path(graf2,2,5)
Out[95]:
In [96]:
nx.shortest_path(graf3,1,7)
Out[96]:
Udaljenost od zadanog vrha prema svim preostalim vrhovima u grafu¶
In [97]:
nx.shortest_path_length(graf2,2)
Out[97]:
In [98]:
nx.shortest_path_length(graf2,4)
Out[98]:
In [99]:
nx.shortest_path_length(graf3,1)
Out[99]:
Najkraći putovi od zadanog vrha prema svim preostalim vrhovima u grafu¶
In [100]:
nx.shortest_path(graf2,2)
Out[100]:
In [101]:
nx.shortest_path(graf2,4)
Out[101]:
In [102]:
nx.shortest_path(graf3,1)
Out[102]:
In [103]:
nx.single_source_shortest_path(graf2,4)
Out[103]:
Najkraće udaljenosti između svaka dva vrha u grafu¶
In [104]:
list(nx.shortest_path_length(graf1))
Out[104]:
In [105]:
list(nx.shortest_path_length(graf2))
Out[105]:
In [106]:
list(nx.shortest_path_length(graf3))
Out[106]:
Najkraći putovi između svaka dva vrha u grafu¶
In [107]:
nx.shortest_path(graf1)
Out[107]:
In [108]:
nx.shortest_path(graf2)
Out[108]:
In [109]:
nx.shortest_path(graf3)
Out[109]:
Ekscentricitet vrha - maksimalna udaljenost vrha od svih preostalih vrhova u grafu¶
In [110]:
nx.eccentricity(graf1)
Out[110]:
In [111]:
nx.eccentricity(graf2)
Out[111]:
In [112]:
nx.eccentricity(graf3)
Out[112]:
In [113]:
nx.eccentricity(graf2,1)
Out[113]:
Radijus grafa - minimalni ekscentricitet¶
In [114]:
nx.radius(graf1)
Out[114]:
In [115]:
nx.radius(graf2)
Out[115]:
In [116]:
nx.radius(graf3)
Out[116]:
Dijametar grafa - maksimalni ekscentricitet¶
In [117]:
nx.diameter(graf1)
Out[117]:
In [118]:
nx.diameter(graf2)
Out[118]:
In [119]:
nx.diameter(graf3)
Out[119]:
Struk grafa¶
In [120]:
DSTG.struk(graf1)
Out[120]:
In [121]:
DSTG.struk(graf2)
Out[121]:
In [122]:
DSTG.struk(graf3)
Out[122]:
Rezni bridovi¶
Ovdje je dana samo naivna implementacija koja daje sve rezne bridove grafa. Jednostavno se prolazi kroz sve bridove grafa i ako brisanjem brida novi graf ima više komponenata povezanosti od početnog grafa, tada je taj obrisani brid rezni brid. Kasnije ćemo dati efikasniju implementaciju koja ne prolazi kroz sve bridove grafa jer se koristi činjenica da je neki brid u povezanom grafu rezni ako i samo ako pripada svakom razapinjućem stablu tog grafa. Za male grafove je i ova naivna implementacija zadovoljavajuća.
Postoji i gotova naredba u NetworkX modulu koja daje sve rezne bridove u jednostavnom grafu.
In [123]:
def rezni_bridovi(G):
rezni=[]
for brid in G.edges():
graf=G.copy()
graf.remove_edge(*brid)
if nx.number_connected_components(graf)>nx.number_connected_components(G):
rezni.append(brid)
return rezni
In [124]:
rezni_bridovi(graf1)
Out[124]:
In [125]:
list(nx.algorithms.bridges(graf1))
Out[125]:
In [126]:
rezni_bridovi(graf2)
Out[126]:
In [127]:
rezni_bridovi(graf3)
Out[127]:
In [128]:
list(nx.algorithms.bridges(graf3))
Out[128]:
Bridna povezanost grafa¶
koliko najmanje bridova treba ukloniti iz grafa da on postane nepovezan
In [129]:
DSTG.minimum_edge_cut(graf1)
Out[129]:
In [130]:
nx.edge_connectivity(graf1)
Out[130]:
In [131]:
bridovi1 = nx.minimum_edge_cut(graf1)
bridovi1
Out[131]:
In [132]:
G1 = graf1.copy()
G1.remove_edges_from(bridovi1)
list(nx.connected_components(G1))
Out[132]:
In [133]:
DSTG.minimum_edge_cut(graf2)
Out[133]:
In [134]:
nx.edge_connectivity(graf2)
Out[134]:
In [135]:
nx.minimum_edge_cut(graf2)
Out[135]:
In [136]:
DSTG.minimum_edge_cut(graf3)
Out[136]:
In [137]:
nx.edge_connectivity(graf3)
Out[137]:
In [138]:
nx.minimum_edge_cut(graf3)
Out[138]:
In [139]:
G3 = graf3.copy()
G3.remove_edges_from([(1,2),(6,5)])
list(nx.connected_components(G3))
Out[139]:
Vršna povezanost, rezni vrhovi i bikomponente¶
koliko najmanje vrhova treba ukloniti iz grafa da on postane nepovezan
graf1 nema reznih vrhova
In [140]:
nx.node_connectivity(graf1)
Out[140]:
In [141]:
nx.minimum_node_cut(graf1)
Out[141]:
In [142]:
list(nx.all_node_cuts(graf1))
Out[142]:
In [143]:
list(nx.biconnected_components(graf1))
Out[143]:
graf2 ima tri rezna vrha: 3, 4, 5
In [144]:
nx.node_connectivity(graf2)
Out[144]:
In [145]:
list(nx.all_node_cuts(graf2))
Out[145]:
In [146]:
list(nx.biconnected_components(graf2))
Out[146]:
graf3 nema reznih vrhova
In [147]:
nx.node_connectivity(graf3)
Out[147]:
In [148]:
nx.minimum_node_cut(graf2)
Out[148]:
In [149]:
list(nx.all_node_cuts(graf3))
Out[149]:
In [150]:
list(nx.biconnected_components(graf3))
Out[150]:
Zadatak
Zadana je matrica susjedstva $A=\begin{bmatrix}1&2&1&0\\ 2&0&1&0\\ 1&1&0&0\\ 0&0&0&0\end{bmatrix}$, čiji su vrhovi redom $v_1, v_2, v_3, v_4$.
- Ima li petlji u grafu? Da li je graf jednostavan?
- Ima li izoliranih vrhova u grafu?
- Izračunajte stupnjeve svih vrhova.
- Nacrtajte graf.
- Odredite broj šetnji duljine 2 i duljine 3 između vrhova $v_1$ i $v_2$, te vrhova $v_1$ i $v_4$.
Rješenje
Konstrukcija grafa
In [151]:
A=np.matrix([[1,2,1,0],[2,0,1,0],[1,1,0,0],[0,0,0,0]])
A1=np.matrix([[1,1,1,0],[1,0,1,0],[0,0,0,0],[0,0,0,0]])
In [152]:
G=nx.MultiGraph(A1)
In [153]:
H=nx.relabel_nodes(G,{0:'v1',1:'v2',2:'v3',3:'v4'})
U grafu je jedna petlja kod vrha $v_1$ pa graf nije jednostavan¶
In [154]:
H.number_of_selfloops()
Out[154]:
In [155]:
list(H.selfloop_edges())
Out[155]:
$v_4$ je izolirani vrh u promatranom grafu¶
In [156]:
H.degree()
Out[156]:
In [157]:
Hviz=nx.nx_agraph.to_agraph(H)
Hviz.draw('H.png',prog='circo')
Image(filename='H.png')
Out[157]:
Ukupno ima 3 $(v_1,v_2)$-šetnje duljine 2 u promatranom grafu. Nadalje, nema niti jedne $(v_1,v_4)$-šetnje duljine 2 u promatranom grafu.¶
In [158]:
print(A**2)
In [159]:
(A**2)[0,1]
Out[159]:
In [160]:
(A**2)[0,3]
Out[160]:
Ukupno ima 15 $(v_1,v_2)$-šetnje duljine 3 u promatranom grafu. Nadalje, nema niti jedne $(v_1,v_4)$-šetnje duljine 3 u promatranom grafu.¶
In [161]:
print(A**3)
In [162]:
(A**3)[0,1]
Out[162]:
In [163]:
(A**3)[0,3]
Out[163]:
Konjićeva tura¶
Ovdje je pokazano kako na lagani način možemo generirati graf kojim se modelira problem konjićeve ture na $m\times n$ ploči. Vi možete ići korak dalje i implementirati neki algoritam koji će u zadanom grafu pronaći Hamiltonov ciklus, ukoliko je zadani graf Hamiltonov.
In [164]:
import itertools
In [165]:
def konjic_skok(m,n):
vrhovi=list(itertools.product(range(1,m+1),range(1,n+1)))
bridovi=[(i,j) for i in vrhovi for j in vrhovi if (abs(i[0]-j[0])==1 and abs(i[1]-j[1])==2) or
(abs(i[0]-j[0])==2 and abs(i[1]-j[1])==1)]
G=nx.Graph()
G.add_nodes_from(vrhovi)
G.add_edges_from(bridovi)
return G
In [166]:
def pozicije_konjic(m,n):
pozicije={}
for i in range(1,m+1):
for j in range(1,n+1):
pozicije[(i,j)]=(i,j)
return pozicije
In [167]:
figure(figsize=(7,5))
nx.draw(konjic_skok(3,3),pos=pozicije_konjic(3,3),node_size=1100,node_color='cyan',with_labels=True)
In [168]:
figure(figsize=(8,8))
nx.draw(konjic_skok(8,8),pos=pozicije_konjic(8,8),node_size=300,node_color='yellow',edgecolors='black')
In [169]:
figure(figsize=(12,10))
nx.draw(konjic_skok(15,12),pos=pozicije_konjic(15,12),node_size=200,node_color='yellow',edgecolors='black')
In [ ]: