Usmjereni grafovi u pythonu

In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
'Linux-4.19.1-1-MANJARO-x86_64-with-arch-Manjaro-Linux'
In [3]:
platform.python_version()
Out[3]:
'3.7.1'
In [4]:
import networkx as nx
In [5]:
nx.__version__
Out[5]:
'2.2'
In [6]:
from pylab import *
In [7]:
%matplotlib inline
In [8]:
import matplotlib.gridspec as gridspec
In [9]:
import matplotlib as plt
In [10]:
plt.__version__
Out[10]:
'3.0.1'
In [11]:
from IPython.core.display import Image
In [12]:
import DSTG

digraf1

In [13]:
digraf1=nx.DiGraph([('u','x'),('v','u'),('v','x'),('w','u'),('x','w')])
In [14]:
DSTG.crtaj_graphviz(digraf1,'digraf1.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]})
Out[14]:
In [15]:
figure(figsize=(2.5,2.5))
nx.draw(digraf1,pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},with_labels=True,node_color='y',node_size=500)

Outstupanj vrha v

In [16]:
digraf1.out_degree('v')
Out[16]:
2

Instupanj vrha v

In [17]:
digraf1.in_degree('v')
Out[17]:
0

outstupnjevi svih vrhova

In [18]:
digraf1.out_degree()
Out[18]:
OutDegreeView({'u': 1, 'x': 1, 'v': 2, 'w': 1})

instupnjevi svih vrhova

In [19]:
digraf1.in_degree()
Out[19]:
InDegreeView({'u': 2, 'x': 2, 'v': 0, 'w': 1})

outstupnjevi vrhova u i v

In [20]:
digraf1.out_degree(['u','v'])
Out[20]:
OutDegreeView({'u': 1, 'v': 2})

instupnjevi vrhova u i v

In [21]:
digraf1.in_degree(['u','v'])
Out[21]:
InDegreeView({'u': 2, 'v': 0})

možemo tražiti stupnjeve vrhova u pripadnom grafu

In [22]:
digraf1.degree()
Out[22]:
DiDegreeView({'u': 3, 'x': 3, 'v': 2, 'w': 2})

matrica susjedstva

vrhovi se smještaju u matricu susjedstva onim redom kojim su u listi digraf1.nodes()

In [23]:
digraf1.nodes()
Out[23]:
NodeView(('u', 'x', 'v', 'w'))
In [24]:
nx.adj_matrix(digraf1).todense()
Out[24]:
matrix([[0, 1, 0, 0],
        [0, 0, 0, 1],
        [1, 1, 0, 0],
        [1, 0, 0, 0]], dtype=int64)
In [25]:
nx.to_pandas_adjacency(digraf1,dtype=int)
Out[25]:
u x v w
u 0 1 0 0
x 0 0 0 1
v 1 1 0 0
w 1 0 0 0

lukovi prema vrhu x

In [26]:
digraf1.in_edges('x')
Out[26]:
InEdgeDataView([('u', 'x'), ('v', 'x')])

lukovi iz vrha x

In [27]:
digraf1.out_edges('x')
Out[27]:
OutEdgeDataView([('x', 'w')])

vrhovi prema kojima postoji luk iz vrha x (out-susjedi vrha x)

In [28]:
list(digraf1.neighbors('x'))
Out[28]:
['w']
In [29]:
list(digraf1.successors('x'))
Out[29]:
['w']

vrhovi iz kojih postoji luk prema vrhu x (in-susjedi vrha x)

In [30]:
list(digraf1.predecessors('x'))
Out[30]:
['u', 'v']

da li je digraf povezan

In [31]:
nx.is_connected(digraf1.to_undirected())
Out[31]:
True

komponente povezanosti - ima samo jednu komponentu jer je digraf povezan

In [32]:
list(nx.connected_components(digraf1.to_undirected()))
Out[32]:
[{'u', 'v', 'w', 'x'}]

da li je digraf dipovezan (jako povezan)

In [33]:
nx.is_strongly_connected(digraf1)
Out[33]:
False

dikomponente - digraf1 ima dvije dikomponente

In [34]:
list(nx.strongly_connected_components(digraf1))
Out[34]:
[{'u', 'w', 'x'}, {'v'}]

dikomponente kao inducirani podgrafovi

In [35]:
dikomponente=list(nx.strongly_connected_component_subgraphs(digraf1))
dikomponente
Out[35]:
[<networkx.classes.digraph.DiGraph at 0x7ffa85d2add8>,
 <networkx.classes.digraph.DiGraph at 0x7ffa85d2ab00>]
In [36]:
DSTG.crtaj_graphviz(dikomponente[0],'dikomp1.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy={"u":[0,1],"w":[0,0],"x":[1,0]})
Out[36]:
In [37]:
DSTG.crtaj_graphviz(dikomponente[1],'dikomp2.png',slika=(1,1),bojaVrha='yellow',tezine=False)
Out[37]:
In [38]:
gs1=gridspec.GridSpec(1, 2,width_ratios=[3,1])
subplot(gs1[0])
axis('off')
imshow(imread('dikomp1.png'),aspect='equal',interpolation='bicubic')
subplot(gs1[1])
axis('off')
imshow(imread('dikomp2.png'),interpolation='bicubic');

da li digraf nema usmjerenih ciklusa

In [39]:
nx.is_directed_acyclic_graph(digraf1)
Out[39]:
False

najkraći usmjereni put od vrha $v$ prema vrhu $u$ i njegova duljina

In [40]:
nx.shortest_path(digraf1,'v','u')
Out[40]:
['v', 'u']
In [41]:
nx.shortest_path_length(digraf1,'v','u')
Out[41]:
1

najkraći usmjereni putovi od vrha $u$ prema svim preostalim vrhovima i njihove udaljenosti

In [42]:
nx.shortest_path(digraf1,'u')
Out[42]:
{'u': ['u'], 'x': ['u', 'x'], 'w': ['u', 'x', 'w']}
In [43]:
nx.shortest_path_length(digraf1,'u')
Out[43]:
{'u': 0, 'x': 1, 'w': 2}

digraf2

In [44]:
digraf2=nx.DiGraph([('u','v'),('v','u'),('v','x'),('w','u'),('w','x')])
In [45]:
DSTG.crtaj_graphviz(digraf2,'digraf2.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]})
Out[45]:
In [46]:
figure(figsize=(2.5,2.5))
nx.draw(digraf2,pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},with_labels=True,node_color='y',node_size=500)

matrica susjedstva

In [47]:
digraf2.nodes()
Out[47]:
NodeView(('u', 'v', 'x', 'w'))
In [48]:
nx.adj_matrix(digraf2).todense()
Out[48]:
matrix([[0, 1, 0, 0],
        [1, 0, 1, 0],
        [0, 0, 0, 0],
        [1, 0, 1, 0]], dtype=int64)
In [49]:
nx.to_pandas_adjacency(digraf2,dtype=int)
Out[49]:
u v x w
u 0 1 0 0
v 1 0 1 0
x 0 0 0 0
w 1 0 1 0

digraf nije dipovezan

In [50]:
nx.is_strongly_connected(digraf2)
Out[50]:
False

digraf ima tri dikomponente

In [51]:
list(nx.strongly_connected_components(digraf2))
Out[51]:
[{'x'}, {'u', 'v'}, {'w'}]

dikomponente kao inducirani podgrafovi

In [52]:
dikomponente2=list(nx.strongly_connected_component_subgraphs(digraf2))
dikomponente2
Out[52]:
[<networkx.classes.digraph.DiGraph at 0x7ffa85c26ba8>,
 <networkx.classes.digraph.DiGraph at 0x7ffa85c26a58>,
 <networkx.classes.digraph.DiGraph at 0x7ffa85c26860>]
In [53]:
dikomponente2[0].nodes(),dikomponente2[1].nodes(),dikomponente2[2].nodes()
Out[53]:
(NodeView(('x',)), NodeView(('u', 'v')), NodeView(('w',)))
In [54]:
DSTG.crtaj_graphviz(dikomponente2[1],'dikomp3.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy={"u":[0,1],"v":[1,1]})
Out[54]:
In [55]:
DSTG.crtaj_graphviz(dikomponente2[0],'dikomp4.png',slika=(1,1),bojaVrha='yellow',tezine=False)
Out[55]:
In [56]:
DSTG.crtaj_graphviz(dikomponente2[2],'dikomp5.png',slika=(1,1),bojaVrha='yellow',tezine=False)
Out[56]:
In [57]:
gs2=gridspec.GridSpec(1, 3, width_ratios=[3,1,1])
subplot(gs2[0])
axis('off')
imshow(imread('dikomp3.png'),interpolation='bicubic')
subplot(gs2[1])
axis('off')
imshow(imread('dikomp4.png'),interpolation='bicubic')
subplot(gs2[2])
axis('off')
imshow(imread('dikomp5.png'),interpolation='bicubic');

digraf2 sadrži usmjerene cikluse

In [58]:
nx.is_directed_acyclic_graph(digraf2)
Out[58]:
False

digraf3

In [59]:
digraf3=nx.MultiDiGraph([('u','v'),('u','v'),('v','x'),('w','u'),('w','x')])
In [60]:
DSTG.crtaj_graphviz(digraf3,'digraf3.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]})
Out[60]:

matrica susjedstva

In [61]:
digraf3.nodes()
Out[61]:
NodeView(('u', 'v', 'x', 'w'))
In [62]:
nx.adj_matrix(digraf3).todense()
Out[62]:
matrix([[0, 2, 0, 0],
        [0, 0, 1, 0],
        [0, 0, 0, 0],
        [1, 0, 1, 0]], dtype=int64)
In [63]:
nx.to_pandas_adjacency(digraf3,dtype=int)
Out[63]:
u v x w
u 0 2 0 0
v 0 0 1 0
x 0 0 0 0
w 1 0 1 0

digraf nije dipovezan

In [64]:
nx.is_strongly_connected(digraf3)
Out[64]:
False

digraf ima četiri dikomponente

In [65]:
list(nx.strongly_connected_components(digraf3))
Out[65]:
[{'x'}, {'v'}, {'u'}, {'w'}]

digraf ne sadrži usmjerene cikluse

In [66]:
nx.is_directed_acyclic_graph(digraf3)
Out[66]:
True

digraf4

In [67]:
digraf4=nx.DiGraph([('u1','u3'),('u2','u1'),('u3','u2'),('u4','u1'),('u4','u3')])
In [68]:
DSTG.crtaj_graphviz(digraf4,'digraf4.png',slika=(3,3),bojaVrha='yellow',tezine=False,xy={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]})
Out[68]:
In [69]:
figure(figsize=(3,3))
nx.draw(digraf4,pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},with_labels=True,node_color='y',node_size=500)

matrica susjedstva

In [70]:
digraf4.nodes()
Out[70]:
NodeView(('u1', 'u3', 'u2', 'u4'))
In [71]:
mat4=nx.adj_matrix(digraf4).todense();mat4
Out[71]:
matrix([[0, 1, 0, 0],
        [0, 0, 1, 0],
        [1, 0, 0, 0],
        [1, 1, 0, 0]], dtype=int64)
In [72]:
nx.to_pandas_adjacency(digraf4,dtype=int)
Out[72]:
u1 u3 u2 u4
u1 0 1 0 0
u3 0 0 1 0
u2 1 0 0 0
u4 1 1 0 0

ukupni broj usmjerenih $(u_1,u_2)$-šetnji duljine 2

In [73]:
mat4**2
Out[73]:
matrix([[0, 0, 1, 0],
        [1, 0, 0, 0],
        [0, 1, 0, 0],
        [0, 1, 1, 0]], dtype=int64)
In [74]:
(mat4**2)[0,2]
Out[74]:
1

ukupni broj usmjerenih $(u_2,u_1)$-šetnji duljine 2

In [75]:
(mat4**2)[2,0]
Out[75]:
0

ukupni broj usmjerenih $(u_4,u_3)$-šetnji duljine 5

In [76]:
(mat4**5)[3,1]
Out[76]:
1

digraf5

In [77]:
digraf5=nx.DiGraph([('v1','v2'),('v1','v4'),('v2','v4'),('v3','v2'),('v4','v3')])
In [78]:
DSTG.crtaj_graphviz(digraf5,'digraf5.png',slika=(3,3),bojaVrha='yellow',tezine=False,xy={"v1":[0,2],"v2":[0,0],"v3":[2,0],"v4":[2,2]})
Out[78]:
In [79]:
figure(figsize=(3,3))
nx.draw(digraf5,pos={"v1":[0,2],"v2":[0,0],"v3":[2,0],"v4":[2,2]},with_labels=True,node_color='y',node_size=500)

digraf4 i digraf5

In [80]:
figure(figsize=(9,7))
gs3=gridspec.GridSpec(1, 2)
subplot(gs3[0])
axis('off')
imshow(imread('digraf4.png'),interpolation='bicubic')
subplot(gs3[1])
axis('off')
imshow(imread('digraf5.png'),interpolation='bicubic');

digraf4 i digraf5 su izomorfni digrafovi

In [81]:
DM=nx.isomorphism.DiGraphMatcher(digraf4,digraf5)
In [82]:
DM.is_isomorphic()
Out[82]:
True

izomorfizam: $u_1\leftrightarrow v_2,\ \ u_2\leftrightarrow v_3,\ \ u_3\leftrightarrow v_4,\ \ u_4\leftrightarrow v_1$

In [83]:
DM.mapping
Out[83]:
{'u4': 'v1', 'u1': 'v2', 'u3': 'v4', 'u2': 'v3'}

postoji samo jedan izomorfizam između digrafova digraf4 i digraf5

In [84]:
for u in DM.isomorphisms_iter():
    print(u) 

{'u4': 'v1', 'u1': 'v2', 'u3': 'v4', 'u2': 'v3'}

Turnir

In [85]:
turnir=nx.DiGraph([('a','c'),('a','d'),('b','a'),('b','c'),('b','e'),('c','f'),('d','b'),('d','c'),
                   ('e','a'),('e','c'),('e','d'),('e','f'),('f','a'),('f','b'),('f','d')])
turpoz={'a':[2,0],'b':[4,0],'c':[6,2],'d':[4,4],'e':[2,4],'f':[0,2]}
In [86]:
DSTG.crtaj_graphviz(turnir,'turnir.png',slika=(5,3),bojaVrha='yellow',tezine=False,xy=turpoz,fontV=20)
Out[86]:

vektor uspjeha turnira

In [87]:
turnir.out_degree()
Out[87]:
OutDegreeView({'a': 2, 'c': 1, 'd': 2, 'b': 3, 'e': 4, 'f': 3})
In [88]:
list(dict(turnir.out_degree()).values())
Out[88]:
[2, 1, 2, 3, 4, 3]

najkraći usmjereni put od vrha a do vrha d

In [89]:
nx.shortest_path(turnir,'a','d')
Out[89]:
['a', 'd']

najkraći usmjereni put od vrha a do vrha e

In [90]:
nx.shortest_path(turnir,'a','e')
Out[90]:
['a', 'd', 'b', 'e']

najkraći put istaknut na digrafu

In [91]:
DSTG.graphviz_najkraci_put(turnir,'a','d',"turnir_ad.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[91]:
In [92]:
DSTG.graphviz_najkraci_put(turnir,'a','e',"turnir_ae.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[92]:

Brentov algoritam

Za traženje usmjerenih ciklusa u bilo kojem digrafu, implementiran je Brentov algoritam. Taj algoritam za zadani digraf daje neki, na slučajni način pronađeni, usmjereni ciklus.

nekoliko usmjerenih ciklusa u našem promatranom turniru

In [93]:
for i in range(5):
    print(DSTG.usmjereni_ciklus(turnir))

['c', 'f', 'd', 'c']
['d', 'b', 'c', 'f', 'd']
['f', 'b', 'a', 'c', 'f']
['a', 'c', 'f', 'b', 'a']
['f', 'b', 'c', 'f']

nekoliko usmjerenih ciklusa istaknutih na digrafu

In [94]:
DSTG.graphviz_usmjereni_ciklus(turnir,"ciklus1.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[94]:
In [95]:
DSTG.graphviz_usmjereni_ciklus(turnir,"ciklus2.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[95]:
In [96]:
DSTG.graphviz_usmjereni_ciklus(turnir,"ciklus3.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[96]:
In [97]:
DSTG.graphviz_usmjereni_ciklus(turnir,"ciklus4.png",slika=(5,3),xy=turpoz,tezine=False,fontV=20)
Out[97]:

promatrani turnir nije Eulerov digraf

In [98]:
nx.is_eulerian(turnir)
Out[98]:
False

Dva turnira s tri vrha

In [99]:
trokut1=nx.DiGraph([("a","b"),("b","c"),("c","a")])
trokut2=nx.DiGraph([("a","b"),("a","c"),("b","c")])
trokutpoz={"a":[0,0],"b":[2,0],"c":[1,1.5]}
In [100]:
DSTG.crtaj_graphviz(trokut1,'trokut1.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy=trokutpoz)
Out[100]:
In [101]:
DSTG.crtaj_graphviz(trokut2,'trokut2.png',slika=(2,2),bojaVrha='yellow',tezine=False,xy=trokutpoz)
Out[101]:

trokut1 je Eulerov digraf, a trokut2 nije Eulerov digraf

In [102]:
nx.is_eulerian(trokut1)
Out[102]:
True
In [103]:
nx.is_eulerian(trokut2)
Out[103]:
False

Rangiranje

In [104]:
Image(filename="turnir.png")
Out[104]:
In [105]:
DSTG.rang_lista(turnir)
Out[105]:
igracibroj pobjedasnaga pobjeda
e412
b310
f310
d26
a25
c14
In [106]:
DSTG.rang_lista(turnir,izlaz='lista')
Out[106]:
[['e', 4, 12],
 ['b', 3, 10],
 ['f', 3, 10],
 ['d', 2, 6],
 ['a', 2, 5],
 ['c', 1, 4]]

rang lista za turnir2

In [107]:
turnir2=nx.DiGraph([("A","B"),("A","C"),("A","D"),("B","D"),
                    ("B","E"),("C","B"),("C","D"),("E","A"),("E","C"),("E","D")])
In [108]:
T2=nx.nx_agraph.to_agraph(turnir2)
T2.node_attr['shape']='circle'
T2.node_attr['style']='filled'
T2.node_attr['fillcolor']='yellow'
T2.draw('turnir2.png',prog='circo')
In [109]:
Image(filename="turnir2.png")
Out[109]:
In [110]:
DSTG.rang_lista(turnir2)
Out[110]:
igracibroj pobjedasnaga pobjeda
E38
A37
B25
C24
D00
In [111]:
DSTG.rang_lista(turnir2,izlaz='lista')
Out[111]:
[['E', 3, 8], ['A', 3, 7], ['B', 2, 5], ['C', 2, 4], ['D', 0, 0]]

rang lista za turnir3

In [112]:
turnir3=nx.DiGraph([("A","C"),("A","D"),("B","A"),("B","C"),("B","E"),
                    ("C","D"),("D","B"),("E","A"),("E","C"),("E","D")])
In [113]:
T3=nx.nx_agraph.to_agraph(turnir3)
T3.node_attr['shape']='circle'
T3.node_attr['style']='filled'
T3.node_attr['fillcolor']='yellow'
T3.draw('turnir3.png',prog='circo')
In [114]:
Image(filename="turnir3.png")
Out[114]:
In [115]:
DSTG.rang_lista(turnir3)
Out[115]:
igracibroj pobjedasnaga pobjeda
B39
E37
A24
D14
C12

Bellman-Fordov i Dijkstrin algoritam

digraf6 - Bellman-Ford i Dijkstra dobro rade

In [116]:
digraf6=nx.DiGraph([('v1','v2',{'weight':1}),('v1','v5',{'weight':4}),
                    ('v2','v3',{'weight':1}),('v2','v5',{'weight':3}),
                    ('v3','v4',{'weight':5}),('v3','v5',{'weight':1}),
                    ('v4','v3',{'weight':1}),('v5','v3',{'weight':1}),
                    ('v5','v4',{'weight':1})])
In [117]:
D6pos={'v1':[0,2],'v2':[2,4],'v3':[5,4],'v4':[6,0],'v5':[2,0]}

funkcije koje vraća najkraće udaljenosti i putove iz zadanog vrha prema preostalim vrhovima

In [118]:
nx.single_source_bellman_ford(digraf6,'v1')
Out[118]:
({'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 4},
 {'v1': ['v1'],
  'v2': ['v1', 'v2'],
  'v5': ['v1', 'v2', 'v3', 'v5'],
  'v3': ['v1', 'v2', 'v3'],
  'v4': ['v1', 'v2', 'v3', 'v5', 'v4']})
In [119]:
nx.single_source_bellman_ford_path(digraf6,'v1')
Out[119]:
{'v1': ['v1'],
 'v2': ['v1', 'v2'],
 'v5': ['v1', 'v2', 'v3', 'v5'],
 'v3': ['v1', 'v2', 'v3'],
 'v4': ['v1', 'v2', 'v3', 'v5', 'v4']}
In [120]:
nx.single_source_bellman_ford_path_length(digraf6,'v1')
Out[120]:
{'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 4}
In [121]:
list(nx.all_pairs_bellman_ford_path(digraf6))
Out[121]:
[('v1',
  {'v1': ['v1'],
   'v2': ['v1', 'v2'],
   'v5': ['v1', 'v2', 'v3', 'v5'],
   'v3': ['v1', 'v2', 'v3'],
   'v4': ['v1', 'v2', 'v3', 'v5', 'v4']}),
 ('v2',
  {'v2': ['v2'],
   'v3': ['v2', 'v3'],
   'v5': ['v2', 'v3', 'v5'],
   'v4': ['v2', 'v3', 'v5', 'v4']}),
 ('v5', {'v5': ['v5'], 'v3': ['v5', 'v3'], 'v4': ['v5', 'v4']}),
 ('v3', {'v3': ['v3'], 'v4': ['v3', 'v5', 'v4'], 'v5': ['v3', 'v5']}),
 ('v4', {'v4': ['v4'], 'v3': ['v4', 'v3'], 'v5': ['v4', 'v3', 'v5']})]
In [122]:
list(nx.all_pairs_bellman_ford_path_length(digraf6))
Out[122]:
[('v1', {'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 4}),
 ('v2', {'v2': 0, 'v3': 1, 'v5': 2, 'v4': 3}),
 ('v5', {'v5': 0, 'v3': 1, 'v4': 1}),
 ('v3', {'v3': 0, 'v4': 2, 'v5': 1}),
 ('v4', {'v4': 0, 'v3': 1, 'v5': 2})]
In [123]:
nx.bellman_ford_predecessor_and_distance(digraf6,'v1')
Out[123]:
({'v1': [], 'v2': ['v1'], 'v5': ['v3'], 'v3': ['v2'], 'v4': ['v5']},
 {'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 4})

najkraći put od vrha $v_1$ do vrha $v_4$

In [124]:
nx.bellman_ford_path(digraf6,'v1','v4')
Out[124]:
['v1', 'v2', 'v3', 'v5', 'v4']
In [125]:
nx.bellman_ford_path_length(digraf6,'v1','v4')
Out[125]:
4

u promatranom digrafu ne postoji usmjereni ciklus negativne težine

In [126]:
nx.negative_edge_cycle(digraf6)
Out[126]:
False

Ručni algoritam

In [127]:
DSTG.rucni_BellmanFord(digraf6,'v1',poredak=['v1','v2','v3','v4','v5'])
Out[127]:
vrh | korak012345
v1$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$
v2$(-,\infty)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$
v3$(-,\infty)$$(-,\infty)$$(\text{v2},2)$$(\text{v2},2)$$(\text{v2},2)$$(\text{v2},2)$
v4$(-,\infty)$$(-,\infty)$$(\text{v5},5)$$(\text{v5},5)$$(\text{v5},4)$$(\text{v5},4)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v3},3)$$(\text{v3},3)$$(\text{v3},3)$
In [128]:
DSTG.BellmanFord(digraf6,'v1')
Out[128]:
({'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 4},
 {'v1': None, 'v2': 'v1', 'v5': 'v3', 'v3': 'v2', 'v4': 'v5'})
In [129]:
DSTG.graphviz_stablo_min_putova(digraf6,'v1',"D6.png",algoritam=DSTG.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,('v2','v5'):12},
                    kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})
Out[129]:
In [130]:
DSTG.rucni_Dijkstra_digraf(digraf6,'v1',poredak=['v1','v2','v3','v4','v5'])
Out[130]:
vrh | korak01234
v1$(-,0)$********************
v2$(-,\infty)$$(\text{v1},1)$***************
v3$(-,\infty)$$(-,\infty)$$(\text{v2},2)$**********
v4$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v3},7)$$(\text{v5},4)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v3},3)$*****
In [131]:
DSTG.Dijkstra_digraf(digraf6,'v1')
Out[131]:
({'v3': 2, 'v1': 0, 'v2': 1, 'v4': 4, 'v5': 3},
 {'v3': 'v2', 'v1': None, 'v2': 'v1', 'v4': 'v5', 'v5': 'v3'})
In [132]:
DSTG.graphviz_stablo_min_putova(digraf6,'v1',"D6dva.png",algoritam=DSTG.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,('v2','v5'):12},
                kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})
Out[132]:

pogledajmo još iz vrha $v_4$ kao početnog vrha

In [133]:
DSTG.rucni_BellmanFord(digraf6,'v4',poredak=['v1','v2','v3','v4','v5'])
Out[133]:
vrh | korak0123
v1$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$
v2$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$
v3$(-,\infty)$$(\text{v4},1)$$(\text{v4},1)$$(\text{v4},1)$
v4$(-,0)$$(-,0)$$(-,0)$$(-,0)$
v5$(-,\infty)$$(-,\infty)$$(\text{v3},2)$$(\text{v3},2)$
In [134]:
DSTG.BellmanFord(digraf6,'v4')
Out[134]:
({'v1': inf, 'v2': inf, 'v5': 2, 'v3': 1, 'v4': 0},
 {'v1': None, 'v2': None, 'v5': 'v3', 'v3': 'v4', 'v4': None})
In [135]:
DSTG.graphviz_stablo_min_putova(digraf6,'v4',"D6tri.png",algoritam=DSTG.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,('v2','v5'):12},
                kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})
Out[135]:
In [136]:
DSTG.rucni_Dijkstra_digraf(digraf6,'v4',poredak=['v1','v2','v3','v4','v5'])
Out[136]:
vrh | korak0123
v1$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$
v2$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$
v3$(-,\infty)$$(\text{v4},1)$**********
v4$(-,0)$***************
v5$(-,\infty)$$(-,\infty)$$(\text{v3},2)$*****
In [137]:
DSTG.Dijkstra_digraf(digraf6,'v4')
Out[137]:
({'v3': 1, 'v1': inf, 'v2': inf, 'v4': 0, 'v5': 2},
 {'v3': 'v4', 'v1': None, 'v2': None, 'v4': None, 'v5': 'v3'})
In [138]:
DSTG.graphviz_stablo_min_putova(digraf6,'v4',"D6cetiri.png",algoritam=DSTG.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,('v2','v5'):12},
                kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})
Out[138]:

digraf7 - zbog negativnih težina Dijkstra ne radi dobro; a kako nema negativnih ciklusa, Bellman-Ford radi ispravno

In [139]:
digraf7=nx.DiGraph([('v1','v2',{'weight':1}),('v1','v5',{'weight':4}),
                    ('v2','v3',{'weight':2}),('v2','v5',{'weight':3}),
                    ('v3','v4',{'weight':5}),('v3','v5',{'weight':4}),
                    ('v4','v3',{'weight':-1}),('v5','v3',{'weight':1}),
                    ('v5','v4',{'weight':-1})])
In [140]:
DSTG.rucni_BellmanFord(digraf7,'v1',poredak=['v1','v2','v3','v4','v5'])
Out[140]:
vrh | korak01234
v1$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$
v2$(-,\infty)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$
v3$(-,\infty)$$(-,\infty)$$(\text{v2},3)$$(\text{v4},2)$$(\text{v4},2)$
v4$(-,\infty)$$(-,\infty)$$(\text{v5},3)$$(\text{v5},3)$$(\text{v5},3)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v1},4)$
In [141]:
DSTG.BellmanFord(digraf7,'v1')
Out[141]:
({'v1': 0, 'v2': 1, 'v5': 4, 'v3': 2, 'v4': 3},
 {'v1': None, 'v2': 'v1', 'v5': 'v1', 'v3': 'v4', 'v4': 'v5'})
In [142]:
nx.negative_edge_cycle(digraf7)
Out[142]:
False
In [143]:
DSTG.graphviz_stablo_min_putova(digraf7,'v1',"D7.png",algoritam=DSTG.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,('v2','v5'):14},
                               kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})
Out[143]:
In [144]:
DSTG.rucni_Dijkstra_digraf(digraf7,'v1',poredak=['v1','v2','v3','v4','v5'])

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[144]:
vrh | korak01234
v1$(-,0)$********************
v2$(-,\infty)$$(\text{v1},1)$***************
v3$(-,\infty)$$(-,\infty)$$(\text{v2},3)$**********
v4$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v3},8)$$(\text{v5},3)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v1},4)$*****
In [145]:
DSTG.Dijkstra_digraf(digraf7,'v1') 

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[145]:
({'v3': 3, 'v1': 0, 'v2': 1, 'v4': 3, 'v5': 4},
 {'v3': 'v2', 'v1': None, 'v2': 'v1', 'v4': 'v5', 'v5': 'v1'})
In [146]:
DSTG.graphviz_stablo_min_putova(digraf7,'v1',"D7dva.png",algoritam=DSTG.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,('v2','v5'):14},
                               kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[146]:

digraf8 - ima usmjereni ciklus negativne težine. Stoga, niti Bellman-Ford, niti Dijkstra ne rade dobro na ovom digrafu.

In [147]:
digraf8=nx.DiGraph([('v1','v2',{'weight':1}),('v1','v5',{'weight':4}),
                    ('v2','v3',{'weight':2}),('v2','v5',{'weight':3}),
                    ('v3','v4',{'weight':5}),('v3','v5',{'weight':1}),
                    ('v4','v3',{'weight':-1}),('v5','v3',{'weight':1}),
                    ('v5','v4',{'weight':-1})])
In [148]:
DSTG.rucni_BellmanFord(digraf8,'v1',poredak=['v1','v2','v3','v4','v5'])

error: digraf ima negativne cikluse
Out[148]:
vrh | korak012345
v1$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$
v2$(-,\infty)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$$(\text{v1},1)$
v3$(-,\infty)$$(-,\infty)$$(\text{v2},3)$$(\text{v4},2)$$(\text{v4},2)$$(\text{v4},2)$
v4$(-,\infty)$$(-,\infty)$$(\text{v5},3)$$(\text{v5},3)$$(\text{v5},3)$$(\text{v5},2)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v3},3)$$(\text{v3},3)$
In [149]:
DSTG.BellmanFord(digraf8,'v1')

error: digraf ima negativne cikluse
Out[149]:
({'v1': 0, 'v2': 1, 'v5': 3, 'v3': 2, 'v4': 2},
 {'v1': None, 'v2': 'v1', 'v5': 'v3', 'v3': 'v4', 'v4': 'v5'})
In [150]:
nx.negative_edge_cycle(digraf8)
Out[150]:
True
In [151]:
DSTG.graphviz_stablo_min_putova(digraf8,'v1',"D8.png",algoritam=DSTG.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,('v2','v5'):14},
                               kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})

error: digraf ima negativne cikluse
Out[151]:
In [152]:
DSTG.rucni_Dijkstra_digraf(digraf8,'v1',poredak=['v1','v2','v3','v4','v5'])

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[152]:
vrh | korak01234
v1$(-,0)$********************
v2$(-,\infty)$$(\text{v1},1)$***************
v3$(-,\infty)$$(-,\infty)$$(\text{v2},3)$**********
v4$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v3},8)$$(\text{v5},3)$
v5$(-,\infty)$$(\text{v1},4)$$(\text{v1},4)$$(\text{v1},4)$*****
In [153]:
DSTG.Dijkstra_digraf(digraf8,'v1')

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[153]:
({'v3': 3, 'v1': 0, 'v2': 1, 'v4': 3, 'v5': 4},
 {'v3': 'v2', 'v1': None, 'v2': 'v1', 'v4': 'v5', 'v5': 'v1'})
In [154]:
DSTG.graphviz_stablo_min_putova(digraf8,'v1',"D8dva.png",algoritam=DSTG.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,('v2','v5'):14},
                               kut={('v4','v3'):-3,('v3','v4'):-1,('v5','v3'):-1,('v3','v5'):-2,('v1','v5'):5,('v2','v5'):3})

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[154]:

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 [155]:
digraf9=nx.DiGraph([('v1','v2',{'weight':3}),('v2','v3',{'weight':-2}),
                    ('v3','v4',{'weight':1}),('v4','v2',{'weight':-1}),
                    ('v4','v5',{'weight':1}),('v5','v6',{'weight':1}),
                    ('v6','v7',{'weight':1}),('v7','v8',{'weight':1})])
In [156]:
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 [157]:
nx.negative_edge_cycle(digraf9)
Out[157]:
True
In [158]:
DSTG.rucni_BellmanFord(digraf9,'v1')

error: digraf ima negativne cikluse
Out[158]:
vrh | korak012345678
v1$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$$(-,0)$
v2$(-,\infty)$$(\text{v1},3)$$(\text{v1},3)$$(\text{v1},3)$$(\text{v4},1)$$(\text{v4},1)$$(\text{v4},1)$$(\text{v4},-1)$$(\text{v4},-1)$
v3$(-,\infty)$$(-,\infty)$$(\text{v2},1)$$(\text{v2},1)$$(\text{v2},1)$$(\text{v2},-1)$$(\text{v2},-1)$$(\text{v2},-1)$$(\text{v2},-3)$
v4$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v3},2)$$(\text{v3},2)$$(\text{v3},2)$$(\text{v3},0)$$(\text{v3},0)$$(\text{v3},0)$
v5$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v4},3)$$(\text{v4},3)$$(\text{v4},3)$$(\text{v4},1)$$(\text{v4},1)$
v6$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v5},4)$$(\text{v5},4)$$(\text{v5},4)$$(\text{v5},2)$
v7$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v6},5)$$(\text{v6},5)$$(\text{v6},5)$
v8$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v7},6)$$(\text{v7},6)$
In [159]:
DSTG.BellmanFord(digraf9,'v1')

error: digraf ima negativne cikluse
Out[159]:
({'v1': 0, 'v2': -1, 'v3': -3, 'v4': 0, 'v5': 1, 'v6': 2, 'v7': 5, 'v8': 6},
 {'v1': None,
  'v2': 'v4',
  'v3': 'v2',
  'v4': 'v3',
  'v5': 'v4',
  'v6': 'v5',
  'v7': 'v6',
  'v8': 'v7'})
In [160]:
DSTG.graphviz_stablo_min_putova(digraf9,'v1',"D9.png",algoritam=DSTG.BellmanFord,slika=(9,8),xy=D9pos,
                               vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
                               fontV=16,debljinaE=2,fontE=16)

error: digraf ima negativne cikluse
Out[160]:
In [161]:
DSTG.rucni_Dijkstra_digraf(digraf9,'v1')

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[161]:
vrh | korak01234567
v1$(-,0)$***********************************
v2$(-,\infty)$$(\text{v1},3)$******************************
v3$(-,\infty)$$(-,\infty)$$(\text{v2},1)$*************************
v4$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v3},2)$********************
v5$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v4},3)$***************
v6$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v5},4)$**********
v7$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v6},5)$*****
v8$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{v7},6)$
In [162]:
DSTG.Dijkstra_digraf(digraf9,'v1')

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[162]:
({'v3': 1, 'v1': 0, 'v2': 3, 'v8': 6, 'v7': 5, 'v6': 4, 'v4': 2, 'v5': 3},
 {'v3': 'v2',
  'v1': None,
  'v2': 'v1',
  'v8': 'v7',
  'v7': 'v6',
  'v6': 'v5',
  'v4': 'v3',
  'v5': 'v4'})
In [163]:
DSTG.graphviz_stablo_min_putova(digraf9,'v1',"D9dva.png",algoritam=DSTG.Dijkstra_digraf,slika=(9,8),xy=D9pos,
                               vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
                               fontV=16,debljinaE=2,fontE=16)

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[163]:

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. Dijkstra također radi ispravno iz vrha $v_1$, ali općenito ne možemo garantirati njegovu točnost.

In [164]:
digraf10=nx.DiGraph([('v1','v4',{'weight':1}),('v2','v1',{'weight':1}),
                    ('v2','v3',{'weight':1}),('v3','v2',{'weight':-2}),
                    ('v3','v4',{'weight':1})])
In [165]:
D10pos={'v1':[0,2],'v2':[4,3],'v3':[7,3.5],'v4':[1,0]}
In [166]:
nx.negative_edge_cycle(digraf10)
Out[166]:
True
In [167]:
DSTG.rucni_BellmanFord(digraf10,'v1')
Out[167]:
vrh | korak012
v1$(-,0)$$(-,0)$$(-,0)$
v4$(-,\infty)$$(\text{v1},1)$$(\text{v1},1)$
v2$(-,\infty)$$(-,\infty)$$(-,\infty)$
v3$(-,\infty)$$(-,\infty)$$(-,\infty)$
In [168]:
DSTG.BellmanFord(digraf10,'v1')
Out[168]:
({'v1': 0, 'v4': 1, 'v2': inf, 'v3': inf},
 {'v1': None, 'v4': 'v1', 'v2': None, 'v3': None})
In [169]:
DSTG.graphviz_stablo_min_putova(digraf10,'v1',"D10.png",algoritam=DSTG.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[169]:
In [170]:
DSTG.rucni_Dijkstra_digraf(digraf10,'v1')

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[170]:
vrh | korak012
v1$(-,0)$**********
v4$(-,\infty)$$(\text{v1},1)$*****
v2$(-,\infty)$$(-,\infty)$$(-,\infty)$
v3$(-,\infty)$$(-,\infty)$$(-,\infty)$
In [171]:
DSTG.Dijkstra_digraf(digraf10,'v1')

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[171]:
({'v2': inf, 'v3': inf, 'v4': 1, 'v1': 0},
 {'v2': None, 'v3': None, 'v4': 'v1', 'v1': None})
In [172]:
DSTG.graphviz_stablo_min_putova(digraf10,'v1',"D10dva.png",algoritam=DSTG.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}) 

error: Dijkstra ne radi ispravno na negativnim tezinama
Out[172]:

algoritam Dijkstra_graf primijenjen na težinski graf

In [173]:
graf=nx.Graph([('A','B',{'weight':5}),('A','C',{'weight':2}),
                    ('A','D',{'weight':4}),('A','E',{'weight':10}),
                    ('B','D',{'weight':8}),('C','E',{'weight':7}),
                    ('C','F',{'weight':5}),('D','E',{'weight':6}),
                    ('D','G',{'weight':2}),('E','F',{'weight':3}),
                    ('E','G',{'weight':2}),('E','H',{'weight':3}),
                    ('F','H',{'weight':2}),('F','I',{'weight':4}),
                    ('G','H',{'weight':3}),('H','I',{'weight':5})])
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 [174]:
DSTG.rucni_Dijkstra_graf(graf,'A',poredak=['A','B','C','D','E','F','G','H','I'])
Out[174]:
vrh | korak012345678
A$(-,0)$****************************************
B$(-,\infty)$$(\text{A},5)$$(\text{A},5)$$(\text{A},5)$*************************
C$(-,\infty)$$(\text{A},2)$***********************************
D$(-,\infty)$$(\text{A},4)$$(\text{A},4)$******************************
E$(-,\infty)$$(\text{A},10)$$(\text{C},9)$$(\text{C},9)$$(\text{C},9)$$(\text{G},8)$$(\text{G},8)$**********
F$(-,\infty)$$(-,\infty)$$(\text{C},7)$$(\text{C},7)$$(\text{C},7)$$(\text{C},7)$***************
G$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{D},6)$$(\text{D},6)$********************
H$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{G},9)$$(\text{G},9)$$(\text{G},9)$*****
I$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(-,\infty)$$(\text{F},11)$$(\text{F},11)$$(\text{F},11)$
In [175]:
DSTG.Dijkstra_graf(graf,'A')
Out[175]:
({'B': 5, 'A': 0, 'F': 7, 'I': 11, 'D': 4, 'G': 6, 'C': 2, 'H': 9, 'E': 8},
 {'B': 'A',
  'A': None,
  'F': 'C',
  'I': 'F',
  'D': 'A',
  'G': 'D',
  'C': 'A',
  'H': 'G',
  'E': 'G'})
In [176]:
DSTG.graphviz_stablo_min_putova(graf,'A',"tezinski.png",algoritam=DSTG.Dijkstra_graf,xy=grafPOS,slika=(4,4),
                               vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
                               fontE=16,debljinaE=1)
Out[176]:

Topološko sortiranje

In [177]:
acDigraf=nx.DiGraph([(2,1),(2,4),(3,1),(3,4),(3,5),(4,5),(6,1),(6,4),(7,2),(7,3),(7,6),(7,8),(8,5),(8,6)])
acPOS={1:[0,0],2:[4,0],3:[1,-1],4:[3,-1],5:[2,-2],6:[1,1],7:[3,1],8:[2,2]}
In [178]:
DSTG.crtaj_graphviz(acDigraf,"acDigraf.png",slika=(4,4),tezine=False,bojaVrha="yellow",xy=acPOS,fontV=20,debljinaE=1)
Out[178]:

digraf jest aciklički

In [179]:
nx.is_directed_acyclic_graph(acDigraf)
Out[179]:
True

topološki sortirani vrhovi promatranog acikličkog digrafa

In [180]:
list(nx.topological_sort(acDigraf))
Out[180]:
[7, 8, 6, 3, 2, 4, 5, 1]

Jaka orijentacija

In [181]:
graf2=nx.grid_2d_graph(3,3)
In [182]:
graf2=nx.relabel_nodes(graf2,dict(zip(graf2.nodes(),range(9))))
In [183]:
graf2POS={0:[0,0],1:[1,0],2:[2,0],3:[0,1],4:[1,1],5:[2,1],6:[0,2],7:[1,2],8:[2,2]}
In [184]:
DSTG.crtaj_graphviz(graf2,"graf2.png",slika=(3,3),tezine=False,bojaVrha="yellow",xy=graf2POS)
Out[184]:

jedna jaka orijentacija na promatranom grafu temeljena na DFS algoritmu iz vrha 0

In [185]:
jaki_graf2=DSTG.DFS_orijentacija(graf2,0)
In [186]:
DSTG.crtaj_graphviz(jaki_graf2,"jaki_graf2.png",slika=(3,3),tezine=False,bojaVrha="yellow",xy=graf2POS)
Out[186]:

jedna jaka orijentacija na kubnom grafu

In [187]:
kub=nx.cubical_graph()
In [188]:
poz_kub=nx.shell_layout(kub,[[0,1,2,3],[4,7,6,5]])
In [189]:
DSTG.crtaj_graphviz(kub,"kub.png",slika=(3,3),tezine=False,bojaVrha="yellow",xy=poz_kub,fontV=12,debljinaE=1)
Out[189]:
In [190]:
jaki_kub=DSTG.DFS_orijentacija(kub,6)
In [191]:
DSTG.crtaj_graphviz(jaki_kub,"jaki_kub.png",slika=(3,3),tezine=False,bojaVrha="yellow",xy=poz_kub,fontV=12,debljinaE=1)
Out[191]:

Transportne mreže

In [192]:
mreza1=nx.DiGraph([('i','u',{'weight':7}),('i','x',{'weight':2}),
                    ('u','x',{'weight':1}),('u','v',{'weight':5}),
                    ('x','y',{'weight':4}),('v','x',{'weight':3}),
                    ('v','y',{'weight':2}),('v','w',{'weight':4}),
                    ('y','z',{'weight':5}),('w','z',{'weight':3}),
                    ('w','p',{'weight':3}),('z','p',{'weight':6})])
In [193]:
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 [194]:
nx.draw(mreza1,pos=mreza1_pos,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(mreza1,pos=mreza1_pos,edge_labels=nx.get_edge_attributes(mreza1,'weight'));
In [195]:
DSTG.crtaj_graphviz(mreza1,"mreza1.png",slika=(8,4),xy=mreza1_pos,bojaVrha="yellow",fontV=18,fontE=18,debljinaE=2,
                   d={('i','x'):10,('w','p'):10},kut={('i','x'):7,('w','p'):-7})
Out[195]:

vrijednost maksimalnog protoka od izvora $i$ do ponora $p$

In [196]:
nx.maximum_flow_value(mreza1,'i','p',capacity='weight')
Out[196]:
8

možemo dobiti i količinu protoka kroz pojedini luk.

In [197]:
nx.maximum_flow(mreza1,'i','p',capacity='weight')
Out[197]:
(8,
 {'i': {'u': 6, 'x': 2},
  'u': {'x': 1, 'v': 5},
  'x': {'y': 3},
  'v': {'x': 0, 'y': 1, 'w': 4},
  'y': {'z': 4},
  'w': {'z': 1, 'p': 3},
  'z': {'p': 5},
  'p': {}})

možemo dobiti potrebne informacije u obliku tablice

In [198]:
DSTG.maksimalni_protok(mreza1,'i','p')

Vrijednost maksimalnog protoka:  8
Out[198]:
lukkapacitet lukaprotok kroz luk
$(\text{i},\text{u})$76
$(\text{i},\text{x})$22
$(\text{u},\text{x})$11
$(\text{u},\text{v})$55
$(\text{x},\text{y})$43
$(\text{v},\text{x})$30
$(\text{v},\text{y})$21
$(\text{v},\text{w})$44
$(\text{y},\text{z})$54
$(\text{w},\text{z})$31
$(\text{w},\text{p})$33
$(\text{z},\text{p})$65

možemo općenito tražiti vrijednost maksimalnog protoka između bilo koja dva vrha koja nisu nužno izvor i ponor

In [199]:
nx.maximum_flow_value(mreza1,'i','v',capacity='weight')
Out[199]:
5
In [200]:
DSTG.maksimalni_protok(mreza1,'i','v')

Vrijednost maksimalnog protoka:  5
Out[200]:
lukkapacitet lukaprotok kroz luk
$(\text{i},\text{u})$75
$(\text{i},\text{x})$20
$(\text{u},\text{x})$10
$(\text{u},\text{v})$55
$(\text{x},\text{y})$40
$(\text{v},\text{x})$30
$(\text{v},\text{y})$20
$(\text{v},\text{w})$40
$(\text{y},\text{z})$50
$(\text{w},\text{z})$30
$(\text{w},\text{p})$30
$(\text{z},\text{p})$60
In [201]:
nx.maximum_flow_value(mreza1,'u','z',capacity='weight')
Out[201]:
6
In [202]:
DSTG.maksimalni_protok(mreza1,'u','z')

Vrijednost maksimalnog protoka:  6
Out[202]:
lukkapacitet lukaprotok kroz luk
$(\text{i},\text{u})$70
$(\text{i},\text{x})$20
$(\text{u},\text{x})$11
$(\text{u},\text{v})$55
$(\text{x},\text{y})$41
$(\text{v},\text{x})$30
$(\text{v},\text{y})$22
$(\text{v},\text{w})$43
$(\text{y},\text{z})$53
$(\text{w},\text{z})$33
$(\text{w},\text{p})$30
$(\text{z},\text{p})$60

od vrha $z$ do vrha $u$ ne postoji protok

In [203]:
nx.maximum_flow_value(mreza1,'z','u',capacity='weight')
Out[203]:
0
In [204]:
DSTG.maksimalni_protok(mreza1,'z','u')

Vrijednost maksimalnog protoka:  0
Out[204]:
lukkapacitet lukaprotok kroz luk
$(\text{i},\text{u})$70
$(\text{i},\text{x})$20
$(\text{u},\text{x})$10
$(\text{u},\text{v})$50
$(\text{x},\text{y})$40
$(\text{v},\text{x})$30
$(\text{v},\text{y})$20
$(\text{v},\text{w})$40
$(\text{y},\text{z})$50
$(\text{w},\text{z})$30
$(\text{w},\text{p})$30
$(\text{z},\text{p})$60

minimalni $(i,p)$-rez

vrijednost minimalnog reza i particija vrhova

In [205]:
nx.minimum_cut(mreza1,'i','p',capacity='weight')
Out[205]:
(8, ({'i', 'u'}, {'p', 'v', 'w', 'x', 'y', 'z'}))

bridovi minimalnog reza i pripadna particija vrhova

In [206]:
DSTG.minimalni_rez(mreza1,'i','p')
Out[206]:
{'particija': ({'i', 'u'}, {'p', 'v', 'w', 'x', 'y', 'z'}),
 'bridovi': [('i', 'x'), ('u', 'v'), ('u', 'x')]}

minimalni rez istaknut na digrafu

In [207]:
DSTG.graphviz_minimalni_rez(mreza1,'i','p',"mreza1.png",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
                           vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
                           d={('i','x'):10,('w','p'):10},kut={('i','x'):7,('w','p'):-7})
Out[207]:

minimalni $(u,z)$-rez

In [208]:
nx.minimum_cut(mreza1,'u','z',capacity='weight')
Out[208]:
(6, ({'p', 'u'}, {'i', 'v', 'w', 'x', 'y', 'z'}))
In [209]:
DSTG.minimalni_rez(mreza1,'u','z')
Out[209]:
{'particija': ({'p', 'u'}, {'i', 'v', 'w', 'x', 'y', 'z'}),
 'bridovi': [('u', 'v'), ('u', 'x')]}
In [210]:
DSTG.graphviz_minimalni_rez(mreza1,'u','z',"mreza1dva.png",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
                           vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
                           d={('i','x'):10,('w','p'):10},kut={('i','x'):7,('w','p'):-7})
Out[210]:

još jedan primjer s drugom transportnom mrežom

In [211]:
mreza2=nx.DiGraph([('i','A',{'weight':3}),('i','C',{'weight':2}),
                    ('i','E',{'weight':6}),('A','B',{'weight':4}),
                    ('C','D',{'weight':2}),('D','p',{'weight':4}),
                    ('E','F',{'weight':2}),('E','H',{'weight':2}),
                    ('F','B',{'weight':2}),('F','G',{'weight':1}),
                    ('G','p',{'weight':5}),('H','D',{'weight':4}),
                    ('H','G',{'weight':1}),('B','p',{'weight':6})])
In [212]:
mreza2_pos={'i':[0,2],'A':[1,4],'B':[3.5,4],'C':[1,0],'D':[3.5,0],'E':[1.2,2],
            'F':[2.25,3.25],'G':[3.5,2],'H':[2.25,1.3],'p':[5,2]}
In [213]:
nx.draw(mreza2,pos=mreza2_pos,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(mreza2,pos=mreza2_pos,edge_labels=nx.get_edge_attributes(mreza2,'weight'));
In [214]:
DSTG.crtaj_graphviz(mreza2,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaVrha="khaki",bojaBrida="black",
                   bojaTezine="blue",fontV=16,fontE=16,debljinaE=1,
                    d={('i','C'):7,('B','p'):8,('H','D'):6,('F','G'):6,('E','H'):4},
                    kut={('i','C'):-7,('B','p'):-7,('H','D'):-7,('F','G'):-7,('E','H'):-12})
Out[214]:

vrijednost maksimalnog protoka od izvora do ponora

In [215]:
nx.maximum_flow_value(mreza2,'i','p',capacity='weight')
Out[215]:
9

količina protoka kroz pojedine lukove

In [216]:
DSTG.maksimalni_protok(mreza2,'i','p')

Vrijednost maksimalnog protoka:  9
Out[216]:
lukkapacitet lukaprotok kroz luk
$(\text{i},\text{A})$33
$(\text{i},\text{C})$22
$(\text{i},\text{E})$64
$(\text{A},\text{B})$43
$(\text{C},\text{D})$22
$(\text{E},\text{F})$22
$(\text{E},\text{H})$22
$(\text{B},\text{p})$65
$(\text{D},\text{p})$44
$(\text{F},\text{B})$22
$(\text{F},\text{G})$10
$(\text{H},\text{D})$42
$(\text{H},\text{G})$10
$(\text{G},\text{p})$50

minimalni $(i,p)$-rez i particija vrhova

In [217]:
nx.minimum_cut(mreza2,'i','p',capacity='weight')
Out[217]:
(9, ({'C', 'E', 'i'}, {'A', 'B', 'D', 'F', 'G', 'H', 'p'}))
In [218]:
DSTG.minimalni_rez(mreza2,'i','p')
Out[218]:
{'particija': ({'C', 'E', 'i'}, {'A', 'B', 'D', 'F', 'G', 'H', 'p'}),
 'bridovi': [('i', 'A'), ('C', 'D'), ('E', 'F'), ('E', 'H')]}
In [219]:
DSTG.graphviz_minimalni_rez(mreza2,'i','p',"mreza2_rez.png",slika=(6,4),xy=mreza2_pos,bojaTezine="blue",
                           fontV=16,fontE=16,debljinaE=1,
                            d={('i','C'):7,('B','p'):8,('H','D'):6,('F','G'):6,('E','H'):4},
                            kut={('i','C'):-7,('B','p'):-7,('H','D'):-7,('F','G'):-7,('E','H'):-12})
Out[219]:
In [ ]: