Usmjereni grafovi u SAGE-u

verzija: SageMath 8.4

Kod konstrukcije digrafa vrijede sva ista pravila kao i kod konstrukcije grafa, jedino umjesto klase Graph treba koristiti klasu DiGraph.

In [1]:
from IPython.core.display import Image
In [2]:
digraf1=DiGraph({"u":["x"],"v":["u","x"],"w":["u"],"x":["w"]})

Kod crtanja digrafa vrijede ista pravila kao i kod crtanja grafa. Također, sve one opcije koje smo koristili kod crtanja grafa se mogu koristiti i kod crtanja digrafa pa ovdje nećemo toliko posebno spominjati sve te opcije.

Digraf1

In [3]:
digraf1.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])

outstupanj vrha v

In [4]:
digraf1.out_degree("v")
Out[4]:
2

instupanj vrha v

In [5]:
digraf1.in_degree("v")
Out[5]:
0

outstupnjevi svih vrhova

In [6]:
digraf1.out_degree()
Out[6]:
[1, 1, 1, 2]
In [7]:
digraf1.out_degree(labels=True)
Out[7]:
{'u': 1, 'v': 2, 'w': 1, 'x': 1}

instupnjevi svih vrhova

In [8]:
digraf1.in_degree()
Out[8]:
[2, 2, 1, 0]
In [9]:
digraf1.in_degree(labels=True)
Out[9]:
{'u': 2, 'v': 0, 'w': 1, 'x': 2}

outstupnjevi vrhova u i v

In [10]:
digraf1.out_degree(["u","v"])
Out[10]:
[1, 2]
In [11]:
digraf1.out_degree(["u","v"],labels=True)
Out[11]:
{'u': 1, 'v': 2}

instupnjevi vrhova u i v

In [12]:
digraf1.in_degree(["u","v"])
Out[12]:
[2, 0]
In [13]:
digraf1.in_degree(["u","v"],labels=True)
Out[13]:
{'u': 2, 'v': 0}

možemo analogno tražiti stupnjeve vrhova u pripadnom grafu

In [14]:
digraf1.degree(labels=True)
Out[14]:
{'u': 3, 'v': 2, 'w': 2, 'x': 3}

matrica susjedstva

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

In [15]:
digraf1.vertices()
Out[15]:
['u', 'v', 'w', 'x']
In [16]:
digraf1.adjacency_matrix()
Out[16]:
[0 0 0 1]
[1 0 0 1]
[1 0 0 0]
[0 0 1 0]

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

In [17]:
digraf1.neighbors_in("x")
Out[17]:
['u', 'v']

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

In [18]:
digraf1.neighbors_out("x")
Out[18]:
['w']

susjedni vrhovi vrha x u pripadnom grafu

In [19]:
digraf1.neighbors("x")
Out[19]:
['u', 'w', 'v']

da li je digraf povezan

In [20]:
digraf1.is_connected()
Out[20]:
True

komponente povezanosti - ima samo jednu komponentu jer je digraf povezan

In [21]:
digraf1.connected_components()
Out[21]:
[['u', 'v', 'w', 'x']]

da li je digraf dipovezan (jako povezan)

In [22]:
digraf1.is_strongly_connected()
Out[22]:
False

dikomponente - digraf1 ima dvije dikomponente

In [23]:
digraf1.strongly_connected_components()
Out[23]:
[['u', 'w', 'x'], ['v']]

dikomponenta koja sadrži vrh x

In [24]:
digraf1.strongly_connected_component_containing_vertex("x")
Out[24]:
['x', 'u', 'w']

digraf dikomponenata - vrhovi predstavljaju dikomponente, a iz prvog vrha prema drugom postoji luk jedino ako se iz prve dikomponente može ući u drugu dikomponentu.

In [25]:
dig1=digraf1.strongly_connected_components_digraph()
In [26]:
dig1.show(pos={dig1.vertices()[0]:[0,0],dig1.vertices()[1]:[20,0]},vertex_shape='h',vertex_size=5000)

dikomponente kao inducirani podgrafovi

In [27]:
dikomponente=digraf1.strongly_connected_components_subgraphs();dikomponente
Out[27]:
[Subgraph of (): Digraph on 3 vertices, Subgraph of (): Digraph on 1 vertex]
In [28]:
graphs_list.show_graphs(dikomponente)
In [29]:
graphics_array([dikomponente[0].plot(graph_border=True),dikomponente[1].plot(graph_border=True)]).show(figsize=[4,2])

da li digraf nema usmjerenih ciklusa

In [30]:
digraf1.is_directed_acyclic()
Out[30]:
False

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

In [31]:
digraf1.shortest_path("v","u")
Out[31]:
['v', 'u']
In [32]:
digraf1.shortest_path_length("v","u")
Out[32]:
1

ne postoji usmjereni put od vrha u prema vrhu v

In [33]:
digraf1.shortest_path("u","v")
Out[33]:
[]
In [34]:
digraf1.shortest_path_length("u","v")
Out[34]:
+Infinity

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

In [35]:
digraf1.shortest_paths("u")
Out[35]:
{'u': ['u'], 'w': ['u', 'x', 'w'], 'x': ['u', 'x']}
In [36]:
digraf1.shortest_path_lengths("u")
Out[36]:
{'u': 0, 'w': 2, 'x': 1}

Digraf2

In [37]:
digraf2=DiGraph({"u":["v"],"v":["u","x"],"w":["u","x"]})
In [38]:
digraf2.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])

matrica susjedstva

In [39]:
digraf2.vertices()
Out[39]:
['u', 'v', 'w', 'x']
In [40]:
digraf2.adjacency_matrix()
Out[40]:
[0 1 0 0]
[1 0 0 1]
[1 0 0 1]
[0 0 0 0]

digraf nije dipovezan

In [41]:
digraf2.is_strongly_connected()
Out[41]:
False

digraf ima tri dikomponente

In [42]:
digraf2.strongly_connected_components()
Out[42]:
[['x'], ['u', 'v'], ['w']]

digraf dikomponenata

In [43]:
dig2=digraf2.strongly_connected_components_digraph();dig2
Out[43]:
In [44]:
dig2.show(pos={dig2.vertices()[0]:[0,0],dig2.vertices()[1]:[20,-10],dig2.vertices()[2]:[40,0]},
          vertex_shape='h',vertex_size=3000,figsize=[5,3],ymax=3)

dikomponente kao inducirani podgrafovi

In [45]:
dikomponente2=digraf2.strongly_connected_components_subgraphs();dikomponente2
Out[45]:
[Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex]
In [46]:
graphs_list.show_graphs(dikomponente2)
In [47]:
gr2=graphics_array([dikomponente2[0].plot(graph_border=True),dikomponente2[1].plot(graph_border=True,
                    pos={"u":[0,1],"v":[1,0]}),dikomponente2[2].plot(graph_border=True)])
gr2.show(figsize=[7,4])

digraf2 sadrži usmjerene cikluse

In [48]:
digraf2.is_directed_acyclic()
Out[48]:
False

Digraf3

In [49]:
digraf3=DiGraph({"u":["v","v"],"v":["x"],"w":["u","x"]})
In [50]:
digraf3.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},
             vertex_size=500,figsize=[3,3])

matrica susjedstva

In [51]:
digraf3.vertices()
Out[51]:
['u', 'v', 'w', 'x']
In [52]:
digraf3.adjacency_matrix()
Out[52]:
[0 2 0 0]
[0 0 0 1]
[1 0 0 1]
[0 0 0 0]

digraf nije dipovezan

In [53]:
digraf3.is_strongly_connected()
Out[53]:
False

digraf ima četiri dikomponente

In [54]:
digraf3.strongly_connected_components()
Out[54]:
[['x'], ['v'], ['u'], ['w']]

digraf ne sadrži usmjerene cikluse

In [55]:
digraf3.is_directed_acyclic()
Out[55]:
True

Digraf4

In [56]:
digraf4=DiGraph({"u1":["u3"],"u2":["u1"],"u3":["u2"],"u4":["u1","u3"]})
In [57]:
digraf4.show(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},vertex_size=400,figsize=[3,3])

matrica susjedstva

In [58]:
digraf4.vertices()
Out[58]:
['u1', 'u2', 'u3', 'u4']
In [59]:
mat4=digraf4.adjacency_matrix();mat4
Out[59]:
[0 0 1 0]
[1 0 0 0]
[0 1 0 0]
[1 0 1 0]

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

In [60]:
(mat4^2)[0,1]
Out[60]:
1

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

In [61]:
(mat4^2)[1,0]
Out[61]:
0

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

In [62]:
(mat4^5)[3,2]
Out[62]:
1

Digraf5

In [63]:
digraf5=DiGraph({"v1":["v2","v4"],"v2":["v4"],"v3":["v2"],"v4":["v3"]})
In [64]:
digraf5.show(graph_border=True,vertex_color="yellow",pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400,figsize=[3,3])

digraf4 i digraf5

In [65]:
graphics_array([digraf4.plot(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},
               vertex_size=400),digraf5.plot(graph_border=True,vertex_color="yellow",
               pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400)]).show(figsize=[6,4])

digraf4 i digraf5 su izomorfni digrafovi

In [66]:
digraf4.is_isomorphic(digraf5)
Out[66]:
True

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

In [67]:
digraf4.is_isomorphic(digraf5,certificate=True)
Out[67]:
(True, {'u1': 'v2', 'u2': 'v3', 'u3': 'v4', 'u4': 'v1'})

ispitivanje izomornosti pomoću networkx modula

In [68]:
import networkx as nx
In [69]:
D4=nx.DiGraph()
D4.add_edges_from([('u1','u3'),('u2','u1'),('u3','u2'),('u4','u1'),('u4','u3')])
In [70]:
D5=nx.DiGraph()
D5.add_edges_from([('v1','v2'),('v1','v4'),('v2','v4'),('v3','v2'),('v4','v3')])
In [71]:
DM=nx.isomorphism.DiGraphMatcher(D4,D5)
In [72]:
DM.is_isomorphic()
Out[72]:
True
In [73]:
DM.mapping
Out[73]:
{'u1': 'v2', 'u2': 'v3', 'u3': 'v4', 'u4': 'v1'}

postoji samo jedan izomorfizam između digrafova digraf4 i digraf5

In [74]:
for u in DM.isomorphisms_iter():
    print u
{'u4': 'v1', 'u1': 'v2', 'u3': 'v4', 'u2': 'v3'}

matrica permutacije

In [75]:
grupa=SymmetricGroup(4)
grupa([2,3,4,1])
Out[75]:
(1,2,3,4)
In [76]:
P=grupa([2,3,4,1]).matrix().transpose();P
Out[76]:
[0 0 0 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
In [77]:
P*digraf4.adjacency_matrix()*P.transpose()==digraf5.adjacency_matrix()
Out[77]:
True

Turnir

In [78]:
turnir=DiGraph({'a':['c','d'],'b':['a','c','e'],'c':['f'],'d':['b','c'],'e':['a','c','d','f'],'f':['a','b','d']})
turpoz={'a':[2,0],'b':[4,0],'c':[6,2],'d':[4,4],'e':[2,4],'f':[0,2]}
In [79]:
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)

vektor uspjeha turnira

In [80]:
turnir.vertices()
Out[80]:
['a', 'b', 'c', 'd', 'e', 'f']
In [81]:
turnir.out_degree(labels=True)
Out[81]:
{'a': 2, 'b': 3, 'c': 1, 'd': 2, 'e': 4, 'f': 3}
In [82]:
turnir.out_degree()
Out[82]:
[2, 1, 3, 4, 2, 3]

najkraći usmjereni put od vrha a do vrha d

In [83]:
turnir.shortest_path("a","d")
Out[83]:
['a', 'd']

najkraći usmjereni put od vrha a do vrha e

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

najkraći put istaknut na digrafu

In [85]:
def najkraci_put(G,v1,v2,raspored_vrhova=None,tezine=False,laj="circular",velicina_vrha=300):
    put=G.shortest_path(v1,v2,by_weight=tezine)
    ostali_vrhovi=list(set(G.vertices()).difference(set([v1,v2])))
    bridovi=G.edges(labels=False)
    bridovi_put=[]
    for i in xrange(len(put)-1):
        if (put[i],put[i+1]) in bridovi:
            bridovi_put.append((put[i],put[i+1]))
        else:
            bridovi_put.append((put[i+1],put[i]))
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={"red":bridovi_put},vertex_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
                     layout=laj,edge_labels=tezine,vertex_size=velicina_vrha)
    else:
        slika=G.plot(edge_colors={"red":bridovi_put},vertex_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
                     pos=raspored_vrhova,edge_labels=tezine,vertex_size=velicina_vrha)
    return slika
In [86]:
najkraci_put(turnir,"a","d",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [87]:
najkraci_put(turnir,"a","e",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)

Brentov algoritam

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

In [88]:
def usmjereni_ciklus(D):
    if not(D.is_directed_acyclic): return "nema usmjerenih ciklusa"
    x0 = choice(D.vertices())
    f = {}
    for v in D.vertices():
        f[v] = choice(D.neighbors_out(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 xrange(lam):
        hare = f[hare]
    while tortoise != hare:
        tortoise = f[tortoise]
        hare = f[hare]
        mu += 1
    ciklus=[tortoise]
    for i in xrange(lam):
        tortoise=f[tortoise]
        ciklus.append(tortoise)
    return ciklus

nekoliko usmjerenih ciklusa u našem promatranom turniru

In [89]:
for i in xrange(5):
 print usmjereni_ciklus(turnir)
['c', 'f', 'd', 'c']
['c', 'f', 'd', 'c']
['b', 'e', 'd', 'b']
['f', 'd', 'c', 'f']
['c', 'f', 'b', 'c']

ako želimo usmjereni ciklus istaknuti na digrafu

In [90]:
def usmjereni_ciklus_digraf(D,raspored_vrhova=None,laj="circular",velicina_vrha=300):
    ciklus = usmjereni_ciklus(D)
    vrhovi2 = list(set(D.vertices()).difference(set(ciklus)))
    lukovi_ciklus = []
    for i in xrange(len(ciklus)-1):
        lukovi_ciklus.append((ciklus[i],ciklus[i+1]))
    if raspored_vrhova == None:
        slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
                       layout=laj,vertex_size=velicina_vrha)
    else:
        slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
                       pos=raspored_vrhova,vertex_size=velicina_vrha)
    return slika

nekoliko usmjerenih ciklusa istaknutih na digrafu

In [91]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [92]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [93]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
In [94]:
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)

promatrani turnir je Hamiltonov digraf

In [95]:
turnir.is_hamiltonian()
Out[95]:
True
In [96]:
turnir.hamiltonian_cycle().show()

Hamiltonov ciklus istaknut na digrafu

In [97]:
def hamiltonov_ciklus(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
    if not(G.is_hamiltonian()):
        return "Error: Graf nije Hamiltonov"
    bridovi=G.hamiltonian_cycle().edges(labels=False)
    if pozicije_vrhova==None:
        slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
    else:
        slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
    return slika
In [98]:
hamiltonov_ciklus(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])

Neki Hamiltonov put u promatranom turniru

In [99]:
def usmjereni_hamiltonov_put(G):
    try:
        H=G.copy()
        H.add_edges(zip(G.vertices(),['vrh']*G.num_verts()))
        H.add_edges(zip(['vrh']*G.num_verts(),G.vertices()))
        ciklus=H.hamiltonian_cycle()
        ciklus.delete_vertex('vrh')
        return ciklus.edges(labels=False)
    except ValueError:
        return "Error: Digraf nema Hamiltonov put"
In [100]:
usmjereni_hamiltonov_put(turnir)
Out[100]:
[('a', 'd'), ('b', 'e'), ('c', 'f'), ('e', 'a'), ('f', 'b')]

Neki Hamiltonov put istaknut na digrafu

In [101]:
def usmjereni_hamiltonov_put_digraf(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
    bridovi = usmjereni_hamiltonov_put(G)
    if pozicije_vrhova==None:
        slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
    else:
        slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
    return slika
In [102]:
usmjereni_hamiltonov_put_digraf(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])

promatrani turnir nije Eulerov digraf

In [103]:
turnir.is_eulerian()
Out[103]:
False

Dva turnira s tri vrha

In [104]:
trokut1=DiGraph({"a":["b"],"b":["c"],"c":["a"]})
trokut2=DiGraph({"a":["b","c"],"b":["c"]})
trokutpoz={"a":[0,0],"b":[2,0],"c":[1,1.5]}
In [105]:
graphics_array([trokut1.plot(graph_border=true,pos=trokutpoz),trokut2.plot(graph_border=true,pos=trokutpoz)]).show(figsize=[6,4])

trokut1 je Eulerov digraf, a trokut2 nije Eulerov digraf

In [106]:
trokut1.is_eulerian()
Out[106]:
True
In [107]:
trokut2.is_eulerian()
Out[107]:
False

trokut1 je Hamiltonov digraf, a trokut2 nije Hamiltonov digraf

In [108]:
trokut1.is_hamiltonian()
Out[108]:
True
In [109]:
trokut2.is_hamiltonian()
Out[109]:
False

međutim, trokut2 ipak ima usmjereni Hamiltonov put

In [110]:
usmjereni_hamiltonov_put_digraf(trokut2,trokutpoz).show(figsize=[3,3])

Rangiranje

In [111]:
def snaga_vrha(T,v0):
    indeks=T.vertices().index(v0)
    matrica=T.adjacency_matrix()+(T.adjacency_matrix())^2
    return sum(matrica.row(indeks))
In [112]:
def rang_lista(turnir,izlaz="html"):
    rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
    rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
    if izlaz == "lista":
        return rezultat
    elif izlaz == "html":
        return table([['igrači','broj pobjeda','snaga pobjeda']]+rezultat)

rang lista za turnir

In [113]:
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)
In [114]:
def rang_lista(turnir,izlaz="html"):
    rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
    rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
    if izlaz == "lista":
        return rezultat
    elif izlaz == "html":
        return table([['igraci','broj pobjeda','snaga pobjeda']]+rezultat)
In [115]:
rang_lista(turnir)
Out[115]:
igraci broj pobjeda snaga pobjeda
e
b
f
d
a
c
In [116]:
rang_lista(turnir,izlaz="lista")
Out[116]:
[['e', 4, 12],
 ['b', 3, 10],
 ['f', 3, 10],
 ['d', 2, 6],
 ['a', 2, 5],
 ['c', 1, 4]]

rang lista za turnir2

In [117]:
turnir2=DiGraph({"A":["B","C","D"],"B":["D","E"],"C":["B","D"],"E":["A","C","D"]})
In [118]:
turnir2.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
In [119]:
rang_lista(turnir2)
Out[119]:
igraci broj pobjeda snaga pobjeda
E
A
B
C
D
In [120]:
rang_lista(turnir2,izlaz="lista")
Out[120]:
[['E', 3, 8], ['A', 3, 7], ['B', 2, 5], ['C', 2, 4], ['D', 0, 0]]

rang lista za turnir3

In [121]:
turnir3=DiGraph({"A":["C","D"],"B":["A","C","E"],"C":["D"],"D":["B"],"E":["A","C","D"]})
In [122]:
turnir3.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
In [123]:
rang_lista(turnir3)
Out[123]:
igraci broj pobjeda snaga pobjeda
B
E
A
D
C

Bellman-Fordov algoritam

U ovom dijelu je napravljena implementacija Bellman-Fordovog algoritma (posebno prilagođena ručnom rješavanju zadataka). Također, implementirana je i poboljšana verzija Dijkstrinog algoritma koja je također posebno prilagođena ručnom rješavanju zadataka. Inače, Dijkstrin algoritam je implementiran u SAGE-u i već smo ga koristili kod težinskih grafova. Bellman-Fordov algoritam je implementiran samo za težinske digrafove, a Dijkstrin algoritam je implementiran za težinske grafove i digrafove.

In [124]:
def BellmanFord(D,v0):
    tezina_brida={}
    for e in D.edges():
        tezina_brida[(e[0],e[1])]=e[2]
    P = {}
    udaljenost = {}
    V = D.vertices()
    E = D.edges()
    udaljenost[0]={}
    for v in V:
        if v == v0:
            udaljenost[0][v] = 0
            P[v] = None
        else:
            udaljenost[0][v] = Infinity
            P[v] = None
    for i in range(1, len(V)+1):
        udaljenost[i]=copy(udaljenost[i-1])
        promjena=False
        for v in V:
            for u in D.neighbors_in(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"
    return (udaljenost[len(udaljenost)-1], P)
In [125]:
def Dijkstra_digraf(D,v0):
    MM=min(map(lambda x: x[2],D.edges()))
    tezina_brida={}
    for e in D.edges():
        tezina_brida[(e[0],e[1])]=e[2]
    P={}
    udaljenost={}
    Q=set(D.vertices())
    for v in Q:
        if v == v0:
            udaljenost[v]=0
            P[v]=None
        else:
            udaljenost[v]=Infinity
            P[v]=None
    while len(Q)>0:
        m=min([udaljenost[u] for u in Q])
        if m == Infinity: break
        v=choice(filter(lambda x: udaljenost[x]==m, Q))
        Q.remove(v)
        for u in set(D.neighbors_out(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 težinama"
    return (udaljenost,P)
In [126]:
def Dijkstra_graf(G,v0):
    MM=min(map(lambda x: x[2],G.edges()))
    tezina_brida={}
    for e in G.edges():
        tezina_brida[(e[0],e[1])]=e[2]
        tezina_brida[(e[1],e[0])]=e[2]
    P={}
    udaljenost={}
    Q=set(G.vertices())
    for v in Q:
        if v == v0:
            udaljenost[v]=0
            P[v]=None
        else:
            udaljenost[v]=Infinity
            P[v]=None
    while len(Q)>0:
        m=min([udaljenost[u] for u in Q])
        if m == Infinity: break
        v=choice(filter(lambda x: udaljenost[x]==m, Q))
        Q.remove(v)
        for u in set(G.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 težinama"
    return (udaljenost,P)
In [127]:
def rucni_BellmanFord(D,v0,poredak=None):
    koraci={}
    if poredak==None:
        V=D.vertices()
    else:
        V=poredak
    tezina_brida={}
    for e in D.edges():
        tezina_brida[(e[0],e[1])]=e[2]
    koraci[0]={}
    for v in V:
        if v==v0:
            koraci[0][v]=('-',0)
        else:
            koraci[0][v]=('-',Infinity)
    for i in xrange(1,len(V)+1):
        koraci[i]=copy(koraci[i-1])
        promjena=False
        for v in V:
            for u in D.neighbors_in(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 xrange(len(koraci)):
        redak=[i]
        for v in V:
            redak.append(koraci[i][v])
        tablica.append(redak)
            
    tablica=[['vrh | korak']+V]+tablica
    tablica=map(list,zip(*tablica))
    if koraci[len(koraci)-1]!=koraci[len(koraci)-2]: print "error: digraf ima negativne cikluse"
    return table(tablica)
In [128]:
def rucni_Dijkstra_digraf(D,v0,poredak=None):
    if poredak==None:
        V=D.vertices()
    else:
        V=poredak
    koraci={}
    tezina_brida={}
    for e in D.edges():
        tezina_brida[(e[0],e[1])]=e[2]
    MM=min(map(lambda x: x[2],D.edges()))
    koraci[0]={}
    for v in V:
        if v==v0:
            koraci[0][v]=('-',0)
        else:
            koraci[0][v]=('-',Infinity)
    Q=set(D.vertices())
    k=1
    while len(Q)>1:
        m=min([koraci[k-1][x][1] for x in Q])
        if m==Infinity:
            break
        else:
            koraci[k]=copy(koraci[k-1])
            w=choice(filter(lambda x: koraci[k-1][x][1]==m, Q))
            Q.remove(w)
            koraci[k][w]='*'
            for v in set(D.neighbors_out(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 xrange(len(koraci)):
        redak=[i]
        for v in V:
            redak.append(koraci[i][v])
        tablica.append(redak)
    
    tablica=[['vrh | korak']+V]+tablica
    tablica=map(list,zip(*tablica))
    if MM<0: print "error: Dijkstra ne radi ispravno na negativnim tezinama"
    return table(tablica)
In [129]:
def rucni_Dijkstra_graf(G,v0, poredak=None):
    if poredak==None:
        V=G.vertices()
    else:
        V=poredak
    koraci={}
    tezina_brida={}
    for e in G.edges():
        tezina_brida[(e[0],e[1])]=e[2]
        tezina_brida[(e[1],e[0])]=e[2]
    koraci[0]={}
    for v in V:
        if v==v0:
            koraci[0][v]=('-',0)
        else:
            koraci[0][v]=('-',Infinity)
    Q=set(G.vertices())
    k=1
    while len(Q)>1:
        m=min([koraci[k-1][x][1] for x in Q])
        if m==Infinity:
            break
        else:
            koraci[k]=copy(koraci[k-1])
            w=choice(filter(lambda x: koraci[k-1][x][1]==m, Q))
            Q.remove(w)
            koraci[k][w]='*'
            for v in set(G.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 xrange(len(koraci)):
        redak=[i]
        for v in V:
            redak.append(koraci[i][v])
        tablica.append(redak)
    
    tablica=[['vrh | korak']+V]+tablica
    tablica=map(list,zip(*tablica))
    
    return table(tablica)

Funkcija stablo_min_putova_DSTG služi za isticanje stabla najkraćih putova od nekog vrha na težinskom grafu ili digrafu na kojeg je primijenjen neki od naših implementiranih algoritama. Stoga opcija algoritam može imati neku od tri vrijednosti: BellmanFord, Dijkstra_digraf, Dijkstra_graf. Pritom, prva dva algoritma primijenjujemo na težinske digrafove, a zadnji na težinske grafove.

In [130]:
def stablo_min_putova_DSTG(D,v0,algoritam=BellmanFord,raspored_vrhova=None,laj="circular",brid0="red",vrh0="yellow",velicina=300):
    P=algoritam(D,v0)[1]
    bridovi=[]
    for x in P:
        if D.is_directed():
            if P[x]!=None: bridovi.append((P[x],x))
        else:
            if P[x]!=None:
                if (P[x],x) in D.edges(labels=False):
                    bridovi.append((P[x],x))
                else:
                    bridovi.append((x,P[x]))
    ostali_bridovi=list(set(D.edges(labels=False)).difference(set(bridovi)))
    if raspored_vrhova==None:
        slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,layout=laj,
                     edge_labels=True,vertex_size=velicina)
    else:
        slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,pos=raspored_vrhova,
                     edge_labels=True,vertex_size=velicina)
    return slika

Nekoliko naredbi koje omogućuju lakše crtanje s Graphvizom

In [131]:
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 sage 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="%d,%d!"\n ' % slika
    rijec+='node [shape=circle width=0 height=0 margin=0 style=filled fontsize=%d penwidth=%d];\n ' % (fontV,debljinaV)
    if dekor:
        rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true decorate=true fontsize=%d penwidth=%d];\n ' 
                % (bojaBrida,bojaTezine,fontE,debljinaE))
    else:
        rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true,fontsize=%d penwidth=%d];\n ' 
                % (bojaBrida,bojaTezine,fontE,debljinaE))
    if bojeVrhova==None:
        bojeVrhova={}
        for v in G.vertices():
            bojeVrhova[v]=bojaVrha
    if xy!=None:
        for v in G.vertices():
            rijec+='"%s" [label="%s" pos="%d,%d!" fillcolor=%s];\n ' % (str(v),str(v),xy[v][0],xy[v][1],bojeVrhova[v])
    else:
        for v in G.vertices():
            rijec+='"%s" [label="%s" style=filled fillcolor=%s];\n ' % (str(v),str(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+='"%s" -> "%s" [color=%s];\n ' % (str(e[0]),str(e[1]),bojeBridova[(e[0],e[1])])
    if tezine==True:
        if d=={}:
            for e in G.edges():
                rijec+='"%s" -%s "%s" [color=%s label="%d"];\n ' % (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2])
        else:
            for e in G.edges():
                if (e[0],e[1]) in d.keys():
                    rijec+=('"%s" -%s "%s" [color=%s headlabel="%d" labeldistance=%d labelangle=%d];\n ' 
                            % (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2],d[(e[0],e[1])],kut[(e[0],e[1])]))
                else:
                    rijec+=('"%s" -%s "%s" [color=%s label="%d"];\n ' 
                    % (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2]))                                    
    rijec+='}'          
    return rijec
In [132]:
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 sage 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 '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
    return Image(filename=ime)
In [133]:
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 D.is_directed():
            if P[x]!=None: bridovi.append((P[x],x))
        else:
            if P[x]!=None:
                if (P[x],x) in D.edges(labels=False):
                    bridovi.append((P[x],x))
                else:
                    bridovi.append((x,P[x]))
    ostali_vrhovi=D.vertices()
    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:
            bojeBridova[(e[0],e[1])]=brid0
        else:
            bojeBridova[(e[0],e[1])]=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)

digraf6 - Bellman-Ford i Dijkstra dobro rade

In [134]:
var('v1 v2 v3 v4 v5 v6 v7 v8')
Out[134]:
(v1, v2, v3, v4, v5, v6, v7, v8)
In [135]:
digraf6=DiGraph({v1:{v2:1,v5:4},
v2:{v3:1,v5:3},
v3:{v4:5,v5:1},
v4:{v3:1},
v5:{v3:1,v4:1}
},weighted=True)
In [136]:
D6pos={v1:[0,2],v2:[2,4],v3:[5,4],v4:[6,0],v5:[2,0]}
In [137]:
rucni_BellmanFord(digraf6,v1,[v1,v2,v3,v4,v5])
Out[137]:
vrh | korak
In [138]:
BellmanFord(digraf6,v1)
Out[138]:
({v5: 3, v4: 4, v3: 2, v2: 1, v1: 0},
 {v5: v3, v4: v5, v3: v2, v2: v1, v1: None})
In [139]:
stablo_min_putova_DSTG(digraf6,v1,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=2000).show(figsize=[6,4])

ljepša slika

In [140]:
graphviz_stablo_min_putova(digraf6,v1,"D6.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[140]:
In [141]:
rucni_Dijkstra_digraf(digraf6,v1,[v1,v2,v3,v4,v5])
Out[141]:
vrh | korak
* * * *
* * *
* *
*
In [142]:
Dijkstra_digraf(digraf6,v1)
Out[142]:
({v5: 3, v4: 4, v3: 2, v2: 1, v1: 0},
 {v5: v3, v4: v5, v3: v2, v2: v1, v1: None})
In [143]:
stablo_min_putova_DSTG(digraf6,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])

ljepša slika

In [144]:
graphviz_stablo_min_putova(digraf6,v1,"D6dva.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[144]:

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

In [145]:
rucni_BellmanFord(digraf6,v4,[v1,v2,v3,v4,v5])
Out[145]:
vrh | korak
In [146]:
BellmanFord(digraf6,v4)
Out[146]:
({v5: 2, v4: 0, v3: 1, v2: +Infinity, v1: +Infinity},
 {v5: v3, v4: None, v3: v4, v2: None, v1: None})
In [147]:
stablo_min_putova_DSTG(digraf6,v4,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])

ljepša slika

In [148]:
graphviz_stablo_min_putova(digraf6,v4,"D6tri.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[148]:
In [149]:
rucni_Dijkstra_digraf(digraf6,v4,[v1,v2,v3,v4,v5])
Out[149]:
vrh | korak
* *
* * *
*
In [150]:
Dijkstra_digraf(digraf6,v4)
Out[150]:
({v5: 2, v4: 0, v3: 1, v2: +Infinity, v1: +Infinity},
 {v5: v3, v4: None, v3: v4, v2: None, v1: None})
In [151]:
graphviz_stablo_min_putova(digraf6,v4,"D6cetiri.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[151]:

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

In [152]:
digraf7=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:4},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
In [153]:
rucni_BellmanFord(digraf7,v1,[v1,v2,v3,v4,v5])
Out[153]:
vrh | korak
In [154]:
BellmanFord(digraf7,v1)
Out[154]:
({v5: 4, v4: 3, v3: 2, v2: 1, v1: 0},
 {v5: v1, v4: v5, v3: v4, v2: v1, v1: None})
In [155]:
graphviz_stablo_min_putova(digraf7,v1,"D7.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
Out[155]:
In [156]:
rucni_Dijkstra_digraf(digraf7,v1,[v1,v2,v3,v4,v5])
error: Dijkstra ne radi ispravno na negativnim tezinama
Out[156]:
vrh | korak
* * * *
* * *
* *
*
In [157]:
Dijkstra_digraf(digraf7,v1)
error: Dijkstra ne radi ispravno na negativnim težinama
Out[157]:
({v5: 4, v4: 3, v3: 3, v2: 1, v1: 0},
 {v5: v1, v4: v5, v3: v2, v2: v1, v1: None})
In [158]:
graphviz_stablo_min_putova(digraf7,v1,"D7dva.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
error: Dijkstra ne radi ispravno na negativnim težinama
Out[158]:

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

In [159]:
digraf8=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:1},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
In [160]:
rucni_BellmanFord(digraf8,v1)
error: digraf ima negativne cikluse
Out[160]:
vrh | korak
In [161]:
BellmanFord(digraf8,v1)
error: digraf ima negativne cikluse
Out[161]:
({v5: 3, v4: 2, v3: 2, v2: 1, v1: 0},
 {v5: v3, v4: v5, v3: v4, v2: v1, v1: None})
In [162]:
graphviz_stablo_min_putova(digraf8,v1,"D8.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
error: digraf ima negativne cikluse
Out[162]:
In [163]:
rucni_Dijkstra_digraf(digraf8,v1)
error: Dijkstra ne radi ispravno na negativnim tezinama
Out[163]:
vrh | korak
*
* *
* * *
* * * *
In [164]:
Dijkstra_digraf(digraf8,v1)
error: Dijkstra ne radi ispravno na negativnim težinama
Out[164]:
({v5: 4, v4: 3, v3: 3, v2: 1, v1: 0},
 {v5: v1, v4: v5, v3: v2, v2: v1, v1: None})
In [165]:
graphviz_stablo_min_putova(digraf8,v1,"D8dva.png",algoritam=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},
                           kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
error: Dijkstra ne radi ispravno na negativnim težinama
Out[165]:

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 [166]:
digraf9=DiGraph({v1:{v2:3},
v2:{v3:-2},
v3:{v4:1},v4:{v2:-1,v5:1},
v5:{v6:1},v6:{v7:1},v7:{v8:1}},weighted=True)
In [167]:
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 [168]:
rucni_BellmanFord(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
error: digraf ima negativne cikluse
Out[168]:
vrh | korak
In [169]:
BellmanFord(digraf9,v1)
error: digraf ima negativne cikluse
Out[169]:
({v3: -3, v6: 2, v2: -1, v5: 1, v1: 0, v8: 6, v4: 0, v7: 5},
 {v3: v2, v6: v5, v2: v4, v5: v4, v1: None, v8: v7, v4: v3, v7: v6})
In [170]:
stablo_min_putova_DSTG(digraf9,v1,algoritam=BellmanFord,raspored_vrhova=D9pos,velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
error: digraf ima negativne cikluse
In [171]:
graphviz_stablo_min_putova(digraf9,v1,"D9.png",algoritam=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[171]:
In [172]:
rucni_Dijkstra_digraf(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
error: Dijkstra ne radi ispravno na negativnim tezinama
Out[172]:
vrh | korak
* * * * * * *
* * * * * *
* * * * *
* * * *
* * *
* *
*
In [173]:
Dijkstra_digraf(digraf9,v1)
error: Dijkstra ne radi ispravno na negativnim težinama
Out[173]:
({v3: 1, v6: 4, v2: 3, v5: 3, v1: 0, v8: 6, v4: 2, v7: 5},
 {v3: v2, v6: v5, v2: v1, v5: v4, v1: None, v8: v7, v4: v3, v7: v6})
In [174]:
stablo_min_putova_DSTG(digraf9,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D9pos,
                       velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
error: Dijkstra ne radi ispravno na negativnim težinama
In [175]:
graphviz_stablo_min_putova(digraf9,v1,"D9dva.png",algoritam=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 težinama
Out[175]:

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

In [176]:
digraf10=DiGraph({v1:{v4:1},
v2:{v1:1,v3:1},
v3:{v2:-2,v4:1}},weighted=True)
In [177]:
D10pos={v1:[0,2],v2:[4,3],v3:[7,3.5],v4:[1,0]}
In [178]:
rucni_BellmanFord(digraf10,v1,[v1,v2,v3,v4])
Out[178]:
vrh | korak
In [179]:
BellmanFord(digraf10,v1)
Out[179]:
({v4: 1, v3: +Infinity, v2: +Infinity, v1: 0},
 {v4: v1, v3: None, v2: None, v1: None})
In [180]:
graphviz_stablo_min_putova(digraf10,v1,"D10.png",algoritam=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[180]:
In [181]:
rucni_Dijkstra_digraf(digraf10,v1)
error: Dijkstra ne radi ispravno na negativnim tezinama
Out[181]:
vrh | korak
*
* *
In [182]:
Dijkstra_digraf(digraf10,v1)
error: Dijkstra ne radi ispravno na negativnim težinama
Out[182]:
({v4: 1, v3: +Infinity, v2: +Infinity, v1: 0},
 {v4: v1, v3: None, v2: None, v1: None})
In [183]:
graphviz_stablo_min_putova(digraf10,v1,"D10dva.png",algoritam=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 težinama
Out[183]:

algoritam Dijkstra_graf primijenjen na težinski graf

In [184]:
var('A,B,C,D,E,F,G,H,I')
Out[184]:
(A, B, C, D, E, F, G, H, I)
In [185]:
graf=Graph({A:{B:5,C:2,D:4,E:10},
B:{D:8},
C:{E:7,F:5},
D:{E:6,G:2},
E:{F:3,G:2,H:3},
F:{H:2,I:4},
G:{H:3},
H:{I:5}
},weighted=True)
In [186]:
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 [187]:
rucni_Dijkstra_graf(graf,A,[A,B,C,D,E,F,G,H,I])
Out[187]:
vrh | korak
* * * * * * * *
* * * * *
* * * * * * *
* * * * * *
* *
* * *
* * * *
*
In [188]:
Dijkstra_graf(graf,A)
Out[188]:
({B: 5, E: 8, A: 0, H: 9, D: 4, I: 11, G: 6, C: 2, F: 7},
 {B: A, E: G, A: None, H: G, D: A, I: F, G: D, C: A, F: C})
In [189]:
stablo_min_putova_DSTG(graf,A,algoritam=Dijkstra_graf,raspored_vrhova=grafPOS,velicina=300).show(figsize=[4,4])
In [190]:
graphviz_stablo_min_putova(graf,A,"tezinski.png",algoritam=Dijkstra_graf,xy=grafPOS,slika=(4,4),vrh0="yellow",
                           vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontE=16,debljinaE=1.5)
Out[190]:

Topološko sortiranje

In [191]:
acDigraf=DiGraph({2:[1,4],3:[1,4,5],4:[5],6:[1,4],7:[2,3,6,8],8:[5,6]})
In [192]:
acPOS={1:[0,0],2:[8,0],3:[2,-2],4:[6,-2],5:[4,-4],6:[2,2],7:[6,2],8:[4,4]}
In [193]:
acDigraf.show(pos=acPOS)

digraf jest aciklički

In [194]:
acDigraf.is_directed_acyclic()
Out[194]:
True

topološki sortirani vrhovi promatranog acikličkog digrafa

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

Jaka orijentacija

In [196]:
graf2=graphs.Grid2dGraph(3,3)
graf2.relabel()
In [197]:
graf2.show(save_pos=True,figsize=[3,3])

jedna jaka orijentacija na promatranom grafu

In [198]:
jaki_graf2=graf2.strong_orientation();jaki_graf2
Out[198]:
In [199]:
jaki_graf2.show(pos=graf2.get_pos(),figsize=[3,3])

jedna jaka orijentacija na kubnom grafu

In [200]:
kub=graphs.CubeGraph(3)
kub.relabel()
kub.strong_orientation().show(figsize=[3,3])

Transportne mreže

In [201]:
var('i u x v y w z p')
Out[201]:
(i, u, x, v, y, w, z, p)
In [202]:
mreza1=DiGraph({i:{u:7,x:2},u:{x:1,v:5},x:{y:4},
                v:{x:3,y:2,w:4},y:{z:5},w:{z:3,p:3},
                z:{p:6}},weighted=True)
In [203]:
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 [204]:
mreza1.show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))

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

In [205]:
mreza1.flow(i,p)
Out[205]:
8

možemo dobiti i digraf u kojemu će težina luka biti količina protoka kroz  pojedini luk. Ukoliko kroz neki luk nema protoka, taj luk se neće nacrtati.

In [206]:
mreza1.flow(i,p,value_only=False)
Out[206]:
(8, Digraph on 8 vertices)
In [207]:
mreza1.flow(i,p,value_only=False)[1].show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))

možemo dobiti potrebne informacije u obliku tablice ako definiramo svoju funkciju

In [208]:
def maksimalni_protok(mreza,v0,v1):
    protok=mreza.flow(v0,v1,value_only=False)
    lukovi=mreza.edges(labels=False)
    lukovi2=protok[1].edges(labels=False)
    kapacitet_luk=[]
    protok_luk=[]
    for e in lukovi:
        kapacitet_luk.append(mreza.edge_label(e[0],e[1]))
        if (e[0],e[1]) in lukovi2:
            protok_luk.append(protok[1].edge_label(e[0],e[1]))
        else:
            protok_luk.append(0)
    
    lukovi=['luk']+lukovi
    kapacitet_luk=['kapacitet luka']+kapacitet_luk
    protok_luk=['protok kroz luk']+protok_luk
    tablica=[lukovi,kapacitet_luk,protok_luk]
    tablica=map(list,zip(*tablica))
    print "Vrijednost maksimalnog protoka: ", protok[0]
    return table(tablica)
In [209]:
maksimalni_protok(mreza1,i,p)
Vrijednost maksimalnog protoka:  8
Out[209]:
luk kapacitet luka protok kroz luk

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

In [210]:
mreza1.flow(i,v)
Out[210]:
5
In [211]:
maksimalni_protok(mreza1,i,v)
Vrijednost maksimalnog protoka:  5
Out[211]:
luk kapacitet luka protok kroz luk
In [212]:
mreza1.flow(u,z)
Out[212]:
6
In [213]:
maksimalni_protok(mreza1,u,z)
Vrijednost maksimalnog protoka:  6
Out[213]:
luk kapacitet luka protok kroz luk

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

In [214]:
mreza1.flow(z,u)
Out[214]:
0
In [215]:
maksimalni_protok(mreza1,z,u)
Vrijednost maksimalnog protoka:  0
Out[215]:
luk kapacitet luka protok kroz luk

minimalni $(i,p)$-rez

vrijednost minimalnog reza

In [216]:
mreza1.edge_cut(i,p,use_edge_labels=True)
Out[216]:
8

vrijednost minimalnog reza i bridovi iz tog reza

In [217]:
mreza1.edge_cut(i,p,use_edge_labels=True,value_only=False)
Out[217]:
[8, [(i, x, 2), (u, x, 1), (u, v, 5)]]

vrijednost minimalnog reza, bridovi iz tog reza i particija vrhova

In [218]:
mreza1.edge_cut(i,p,use_edge_labels=True,vertices=True)
Out[218]:
[8, [(i, x, 2), (u, x, 1), (u, v, 5)], [[i, u], [x, p, w, z, v, y]]]

Želimo li minimalni rez istaknuti na digrafu, definiramo svoju funkciju. Lukovi iz minimalnog reza su po defaultu obojani crvenom bojom (može se njihova boja po želji promijeniti), a vrhovi iz jedne particije su obojani žutom bojom, a iz druge particije svijetlo plavom bojom.

In [219]:
def minimalni_rez(mreza,v1,v2,metoda="FF",raspored_vrhova=None,laj="circular",brid="red",velicina=300):
    rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
    bridovi=map(lambda e: (e[0],e[1]),rez[1])
    ostali_bridovi=list(set(mreza.edges(labels=False)).difference(set(bridovi)))
    if raspored_vrhova==None:
        slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
                         vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},layout=laj,edge_labels=True,vertex_size=velicina)
    else:
        slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
                         vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},pos=raspored_vrhova,edge_labels=True,vertex_size=velicina)
    return slika
In [220]:
def graphviz_minimalni_rez(mreza,v1,v2,ime,metoda="FF",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 na transportnoj mrezi.
    metoda='FF' -> rez se trazi Ford-Fulkersonovim algoritmom
    metoda='LP' -> rez se trazi metodom linearnog programiranja
    
    Slika se crta u graphviz formatu.
    ime -> ime datoteke u koju ce biti spremljena slika
    slika -> dimenzije nacrtane slike na izlazu
    xy -> rjecnik koordinata vrhova grafa G
    vrh0 -> boja vrhova iz particije vrha v1
    vrh1 -> boja vrhova iz particije vrha 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"""
    rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
    bridovi=map(lambda e: (e[0],e[1]),rez[1])
    bojeVrhova={}
    for v in rez[2][0]:
        bojeVrhova[v]=vrh0
    for v in rez[2][1]:
        bojeVrhova[v]=vrh1
    bojeBridova={}
    for e in mreza.edges(labels=False):
        if e in bridovi:
            bojeBridova[e]=brid0
        else:
            bojeBridova[e]=brid1            
    rijec=graf_string(mreza,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)
In [221]:
minimalni_rez(mreza1,i,p,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
In [222]:
graphviz_minimalni_rez(mreza1,i,p,"mreza1.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
                       vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
                      d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
Out[222]:

minimalni $(u,z)$-rez

In [223]:
mreza1.edge_cut(u,z,use_edge_labels=True,vertices=True)
Out[223]:
[6, [(u, x, 1), (u, v, 5)], [[u], [x, i, p, w, z, v, y]]]
In [224]:
minimalni_rez(mreza1,u,z,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
In [225]:
graphviz_minimalni_rez(mreza1,u,z,"mreza1dva.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
                       vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
                      d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
Out[225]:

još jedan primjer s drugom transportnom mrežom

In [226]:
mreza2=DiGraph({i:{A:3,C:2,E:6},A:{B:4},C:{D:2},
                D:{p:4},E:{F:2,H:2},F:{B:2,G:1},
                G:{p:5},H:{D:4,G:1},B:{p:6}},weighted=True)
In [227]:
mreza2_pos={i:[0,4],A:[2,8],B:[7,8],C:[2,0],D:[7,0],E:[3,4],F:[4.5,6.5],G:[6,4],H:[4.5,1.5],p:[10,4]}
In [228]:
mreza2.show(pos=mreza2_pos,edge_labels=True,vertex_size=500,figsize=(6,4),ymin=-0.1)
In [229]:
crtaj_graphviz(mreza2,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaVrha="khaki",bojaBrida="black",bojaTezine="blue",
               fontV=24,fontE=24,debljinaE=2,d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})
Out[229]:

vrijednost maksimalnog protoka od izvora do ponora

In [230]:
mreza2.flow(i,p)
Out[230]:
9

količina protoka kroz pojedine lukove

In [231]:
maksimalni_protok(mreza2,i,p)
Vrijednost maksimalnog protoka:  9
Out[231]:
luk kapacitet luka protok kroz luk

minimalni $(i,p)$-rez

In [232]:
mreza2.edge_cut(i,p,use_edge_labels=True,vertices=True)
Out[232]:
[9,
 [(E, H, 2), (E, F, 2), (i, A, 3), (i, C, 2)],
 [[i, E], [B, A, H, p, D, G, C, F]]]
In [233]:
minimalni_rez(mreza2,i,p,raspored_vrhova=mreza2_pos).show(figsize=[6,4])
In [234]:
graphviz_minimalni_rez(mreza2,i,p,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaTezine="blue",fontV=24,fontE=24,debljinaE=2,
                      d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})
Out[234]:
In [ ]: