Stabla u pythonu

In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
'Linux-4.19.0-2-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]:
from IPython.core.display import Image
In [9]:
import DSTG

neka već definirana stabla u networkx-u

balanced_tree

In [10]:
nx.draw(nx.balanced_tree(3,2),with_labels=True,node_color='y',edgecolors='k')
In [11]:
nx.draw(nx.balanced_tree(2,3),with_labels=True,node_color='y',edgecolors='k')

stablo nacrtano kao korijensko stablo

In [12]:
figure(figsize=(10,5))
gr=nx.balanced_tree(3,2)
nx.draw(gr,pos=DSTG.RootedEmbedding(gr,0),with_labels=True,node_color='y',edgecolors='k')
In [13]:
figure(figsize=(10,5))
nx.draw(gr,pos=DSTG.RootedEmbedding(gr,8),with_labels=True,node_color='y',edgecolors='k')
In [14]:
figure(figsize=(10,5))
gr2=nx.balanced_tree(2,3)
nx.draw(gr2,pos=DSTG.RootedEmbedding(gr2,0),with_labels=True,node_color='y',edgecolors='k')
In [15]:
figure(figsize=(10,5))
nx.draw(gr2,pos=DSTG.RootedEmbedding(gr2,4),with_labels=True,node_color='y',edgecolors='k')

path_graph

In [16]:
figure(figsize=(6,4))
nx.draw(nx.path_graph(8),with_labels=True,node_color='y',edgecolors='k')
In [17]:
figure(figsize=(8,6))
nx.draw(nx.path_graph(20),with_labels=True,node_color='y',edgecolors='k')

star_graph

In [18]:
nx.draw(nx.star_graph(7),with_labels=True,node_color='y',edgecolors='k')
In [19]:
figure(figsize=(8,6))
nx.draw(nx.star_graph(19),with_labels=True,node_color='y',edgecolors='k')

degree_sequence_tree

In [20]:
nx.draw(nx.degree_sequence_tree([2,1,2,3,1,1,1,2,1,4]),with_labels=True,node_color='y',edgecolors='k')
In [21]:
nx.draw(nx.degree_sequence_tree([3,1,3,3,1,1,1,2,1]),with_labels=True,node_color='y',edgecolors='k')

Pazite, u stablu vrijedi $\varepsilon=\nu-1\ $ pa zbog $\sum\limits_{v\in V(G)}{d(v)}=2\varepsilon$ mora biti $\ \nu-\frac{1}{2}\sum\limits_{v\in V(G)}{d(v)}=1$

šuma

In [22]:
stablo1=nx.path_graph(5) 
stablo2=nx.star_graph(7) 
graf=nx.disjoint_union(stablo1,stablo2)
In [23]:
figure(figsize=(6,4))
nx.draw(graf,with_labels=True,node_color='y',edgecolors='k')

Razapinjuća stabla grafa

1. primjer

In [24]:
graf1=nx.Graph({1:[2,4],2:[3,4],3:[4]}) 
poz1={1:[0,0],2:[1,0],3:[1,1],4:[0,1]} 
nx.draw(graf1,pos=poz1,with_labels=True,node_color='y',edgecolors='k')

ukupni broj razapinjućih stabala grafa

In [25]:
DSTG.BrojRazapinjucihStabala(graf1)
Out[25]:
8

neko razapinjuće stablo grafa

In [26]:
bridovi1=list(nx.bfs_edges(graf1,2))
raz_stablo1=nx.Graph(bridovi1)
nx.draw(raz_stablo1,pos=poz1,with_labels=True,node_color='y',edgecolors='k')

2. primjer

In [27]:
graf2=nx.complete_bipartite_graph(2,3)
poz2={0:[0,1.5],1:[0,0.5],2:[2,2],3:[2,1],4:[2,0]} 
nx.draw(graf2,pos=poz2,with_labels=True,node_color='y',edgecolors='k')

ukupni broj razapinjućih stabala grafa

In [28]:
DSTG.BrojRazapinjucihStabala(graf2)
Out[28]:
12

neko razapinjuće stablo grafa

In [29]:
bridovi2=list(nx.dfs_edges(graf2,1))
raz_stablo2=nx.Graph(bridovi2)
nx.draw(raz_stablo2,pos=poz2,with_labels=True,node_color='y',edgecolors='k')

3. primjer

In [30]:
graf3=nx.Graph({1:[2,4,5],2:[3,5],3:[4],4:[5]}) 
poz3={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]} 
nx.draw(graf3,pos=poz3,with_labels=True,node_color='y',edgecolors='k')

ukupni broj razapinjućih stabala grafa

In [31]:
DSTG.BrojRazapinjucihStabala(graf3)
Out[31]:
24

neko razapinjuće stablo grafa

In [32]:
bridovi3=list(nx.bfs_edges(graf3,5))
raz_stablo3=nx.Graph(bridovi3)
nx.draw(raz_stablo3,pos=poz3,with_labels=True,node_color='y',edgecolors='k')

4. primjer

In [33]:
graf4=nx.Graph({1:[2,4],2:[3,5],3:[6],4:[5,7],5:[6,7],6:[7]}) 
poz4={1:[0,0],2:[1,0],3:[2,0],4:[0,1],5:[1,1],6:[2,1],7:[1,2]} 
nx.draw(graf4,pos=poz4,with_labels=True,node_color='y',edgecolors='k')

ukupni broj razapinjućih stabala grafa

In [34]:
DSTG.BrojRazapinjucihStabala(graf4)
Out[34]:
95

neka razapinjuća stabla grafa

In [35]:
bridovi41=list(nx.dfs_edges(graf4,4))
raz_stablo41=nx.Graph(bridovi41)
nx.draw(raz_stablo41,pos=poz4,with_labels=True,node_color='y',edgecolors='k')
In [36]:
bridovi42=list(nx.bfs_edges(graf4,5))
raz_stablo42=nx.Graph(bridovi42)
nx.draw(raz_stablo42,pos=poz4,with_labels=True,node_color='y',edgecolors='k')

5. primjer

In [37]:
graf5=nx.MultiGraph({1:[2,2,2,4,4,4],2:[3,3,3],3:[4,4,4],4:[5,5,5]}) 
poz5={1:[1,-1],2:[0,0],3:[1,1],4:[2,0],5:[3,0]}
graf5vz=nx.nx_agraph.to_agraph(graf5)
graf5vz.draw("graf5.png",prog='circo')
Image(filename="graf5.png")
Out[37]:

ukupni broj razapinjućih stabala grafa

In [38]:
DSTG.BrojRazapinjucihStabala(graf5)
Out[38]:
324

neko razapinjuće stablo grafa

In [39]:
bridovi5=list(nx.dfs_edges(graf5,4))
raz_stablo5=nx.Graph(bridovi5)
nx.draw(raz_stablo5,pos=poz5,with_labels=True,node_color='y',edgecolors='k')

6. primjer

In [40]:
graf6=nx.MultiGraph({1:[1,2,2,2],2:[3,4],3:[3,3,4,4]})
graf6vz=nx.nx_agraph.to_agraph(graf6)
graf6vz.draw('graf6.png',prog='circo')
Image(filename='graf6.png')
Out[40]:

ukupni broj razapinjućih stabala grafa

In [41]:
DSTG.BrojRazapinjucihStabala(graf6)
Out[41]:
15

neko razapinjuće stablo grafa

In [42]:
bridovi6=list(nx.bfs_edges(graf6,2))
raz_stablo6=nx.Graph(bridovi6)
nx.draw(raz_stablo6,with_labels=True,node_color='y',edgecolors='k')

7. primjer

In [43]:
graf7=nx.complete_graph(6)
nx.draw_circular(graf7,with_labels=True,node_color='y',edgecolors='k')

ukupni broj razapinjućih stabala grafa

In [44]:
DSTG.BrojRazapinjucihStabala(graf7)
Out[44]:
1296

neka razapinjuća stabla potpunog grafa $K_6$

In [45]:
figure(figsize=(15,4))
subplot(131)
bridovi71=list(nx.bfs_edges(graf7,4))
raz_stablo71=nx.Graph(bridovi71)
nx.draw_circular(raz_stablo71,with_labels=True,node_color='y',edgecolors='k')
subplot(132)
bridovi72=list(nx.dfs_edges(graf7,4))
raz_stablo72=nx.Graph(bridovi72)
nx.draw_circular(raz_stablo72,with_labels=True,node_color='y',edgecolors='k')
subplot(133)
bridovi73=list(nx.dfs_edges(graf7,0))
raz_stablo73=nx.Graph(bridovi73)
nx.draw_circular(raz_stablo73,with_labels=True,node_color='y',edgecolors='k')

DFS i BFS algoritam

DFS algoritam

In [46]:
gr=nx.Graph({1:[3,5],2:[5],3:[4,6],4:[5,7],5:[8],6:[7],7:[8]}) 
pozicije={1:[1,0],2:[2,0],3:[0,1],4:[1,1],5:[2,1],6:[0,2],7:[1,2],8:[2,2]} 
figure(figsize=(5,5))
nx.draw(gr,pos=pozicije,node_size=500,with_labels=True,node_color='y',edgecolors='k')

DFS algoritam daje preorder redoslijed posjećivanja vrhova počevši s vrhom "1"

In [47]:
list(nx.dfs_preorder_nodes(gr,1))
Out[47]:
[1, 3, 4, 5, 2, 8, 7, 6]

DFS algoritam daje preorder redoslijed posjećivanja vrhova počevši s vrhom "4"

In [48]:
list(nx.dfs_preorder_nodes(gr,4))
Out[48]:
[4, 3, 1, 5, 2, 8, 7, 6]

DFS algoritam daje postorder redoslijed posjećivanja vrhova počevši s vrhom "1"

In [49]:
list(nx.dfs_postorder_nodes(gr,1))
Out[49]:
[2, 6, 7, 8, 5, 4, 3, 1]

DFS algoritam daje postorder redoslijed posjećivanja vrhova počevši s vrhom "4"

In [50]:
list(nx.dfs_postorder_nodes(gr,4))
Out[50]:
[2, 6, 7, 8, 5, 1, 3, 4]

DFS stablo s korijenom "1"

In [51]:
nx.nx_agraph.to_agraph(nx.dfs_tree(gr,1)).draw('dfs1.png',prog='dot')
In [52]:
Image(filename="dfs1.png")
Out[52]:

DFS stablo s korijenom "4"

In [53]:
nx.nx_agraph.to_agraph(nx.dfs_tree(gr,4)).draw('dfs4.png',prog='dot')
In [54]:
Image(filename="dfs4.png")
Out[54]:

bridovi DFS stabla s početnim vrhom "1"

In [55]:
list(nx.dfs_edges(gr,1))
Out[55]:
[(1, 3), (3, 4), (4, 5), (5, 2), (5, 8), (8, 7), (7, 6)]

bridovi DFS stabla s početnim vrhom "4"

In [56]:
list(nx.dfs_edges(gr,4))
Out[56]:
[(4, 3), (3, 1), (1, 5), (5, 2), (5, 8), (8, 7), (7, 6)]

prethodnik pojedinog vrha u DFS stablu s početnim vrhom "1"

In [57]:
nx.dfs_predecessors(gr,1)
Out[57]:
{3: 1, 4: 3, 5: 4, 2: 5, 8: 5, 7: 8, 6: 7}

prethodnik pojedinog vrha u DFS stablu s početnim vrhom "4"

In [58]:
nx.dfs_predecessors(gr,4)
Out[58]:
{3: 4, 1: 3, 5: 1, 2: 5, 8: 5, 7: 8, 6: 7}

sljedbenici pojedinog vrha u DFS stablu s početnim vrhom "1"

In [59]:
nx.dfs_successors(gr,1)
Out[59]:
{1: [3], 3: [4], 4: [5], 5: [2, 8], 8: [7], 7: [6]}

sljedbenici pojedinog vrha u DFS stablu s početnim vrhom "4"

In [60]:
nx.dfs_successors(gr,4)
Out[60]:
{4: [3], 3: [1], 1: [5], 5: [2, 8], 8: [7], 7: [6]}

DFS stablo s početkom u vrhu "1" istaknuto na grafu

In [61]:
figure(figsize=(5,5))
DSTG.DFSstablo(gr,pozicije,1,velicinaVrha=500,rubVrha='k')

DFS stablo s početkom u vrhu "4" istaknuto na grafu

In [62]:
figure(figsize=(5,5))
DSTG.DFSstablo(gr,pozicije,4,velicinaVrha=500,rubVrha='k')

DFS stablo s početkom u vrhu "1" kao korijensko stablo

In [63]:
figure(figsize=(5,5))
DSTG.DFSkorijenskoStablo(gr,1,velicinaVrha=500,rubVrha='k')

DFS stablo s početkom u vrhu "4" kao korijensko stablo

In [64]:
figure(figsize=(5,5))
DSTG.DFSkorijenskoStablo(gr,4,velicinaVrha=500,rubVrha='k')

BFS algoritam

prethodnik pojedinog vrha u BFS stablu s početnim vrhom "1"

In [65]:
dict(nx.bfs_predecessors(gr,1))
Out[65]:
{3: 1, 5: 1, 4: 3, 6: 3, 2: 5, 8: 5, 7: 4}

prethodnik pojedinog vrha u BFS stablu s početnim vrhom "4"

In [66]:
dict(nx.bfs_predecessors(gr,4))
Out[66]:
{3: 4, 5: 4, 7: 4, 1: 3, 6: 3, 2: 5, 8: 5}

sljedbenici pojedinog vrha u BFS stablu s početnim vrhom "1"

In [67]:
dict(nx.bfs_successors(gr,1))
Out[67]:
{1: [3, 5], 3: [4, 6], 5: [2, 8], 4: [7]}

sljedbenici pojedinog vrha u BFS stablu s početnim vrhom "4"

In [68]:
dict(nx.bfs_successors(gr,4))
Out[68]:
{4: [3, 5, 7], 3: [1, 6], 5: [2, 8]}

bridovi u BFS stablu s početnim vrhom "1"

In [69]:
list(nx.bfs_edges(gr,1))
Out[69]:
[(1, 3), (1, 5), (3, 4), (3, 6), (5, 2), (5, 8), (4, 7)]

bridovi u BFS stablu s početnim vrhom "4"

In [70]:
list(nx.bfs_edges(gr,4))
Out[70]:
[(4, 3), (4, 5), (4, 7), (3, 1), (3, 6), (5, 2), (5, 8)]

BFS stablo s korijenom "1"

In [71]:
nx.nx_agraph.to_agraph(nx.bfs_tree(gr,1)).draw('bfs1.png',prog='dot')
In [72]:
Image(filename="bfs1.png")
Out[72]:

BFS stablo s korijenom "4"

In [73]:
nx.nx_agraph.to_agraph(nx.bfs_tree(gr,4)).draw('bfs4.png',prog='dot')
In [74]:
Image(filename="bfs4.png")
Out[74]:

BFS stablo s početkom u vrhu "1" istaknuto na grafu

In [75]:
figure(figsize=(5,5))
DSTG.BFSstablo(gr,pozicije,1,velicinaVrha=500,rubVrha='k')

BFS stablo s početkom u vrhu "4" istaknuto na grafu

In [76]:
figure(figsize=(5,5))
DSTG.BFSstablo(gr,pozicije,4,velicinaVrha=500,rubVrha='k')

BFS stablo s početkom u vrhu "1" kao korijensko stablo

In [77]:
DSTG.BFSkorijenskoStablo(gr,1,velicinaVrha=500,rubVrha='k')

BFS stablo s početkom u vrhu "4" kao korijensko stablo

In [78]:
DSTG.BFSkorijenskoStablo(gr,4,velicinaVrha=500,rubVrha='k')

Algoritam za traženje reznih bridova

Brid u grafu $G$ je rezni ako i samo ako pripada svakom razapinjućem stablu grafa $G$. Na toj činjenici se temelji implementacija funkcije rezni_bridovi za traženje reznih bridova. Na zadani graf, tj. na njegove komponente povezanosti se primijeni DFS algoritam koji će za svaku njegovu komponentu povezanosti pronaći neko razapinjuće stablo. Svi rezni bridovi grafa $G$ pripadaju nekom od tih stabala. Stoga je dovoljno samo ispitati bridove koji pripadaju tim razapinjućim stablima jesu li neki od njih rezni.

donji graf ima samo jedan rezni brid

In [79]:
figure(figsize=(4,4))
nx.draw(gr,pos=pozicije,node_color='y',node_size=500,with_labels=True,edgecolors='k')
In [80]:
DSTG.rezni_bridovi(gr)
Out[80]:
[(5, 2)]

postoji i gotova naredba u networkx-u, ali ona radi samo na jednostavnim grafovima

In [81]:
list(nx.bridges(gr))
Out[81]:
[(2, 5)]

donji graf nema reznih bridova

In [82]:
figure(figsize=(4,4))
nx.draw(graf1,pos=poz1,node_color='y',node_size=500,with_labels=True,edgecolors='k')
In [83]:
DSTG.rezni_bridovi(graf1)
Out[83]:
[]
In [84]:
list(nx.bridges(graf1))
Out[84]:
[]

donji graf ima četiri rezna brida

In [85]:
figure(figsize=(7,4))
G=nx.Graph({0:[3],1:[4],2:[4,5,7,8,9],4:[5],5:[7],6:[]})
nx.draw(G,node_color='y',with_labels=True,edgecolors='k')
In [86]:
DSTG.rezni_bridovi(G)
Out[86]:
[(0, 3), (1, 4), (2, 8), (2, 9)]
In [87]:
list(nx.bridges(G))
Out[87]:
[(0, 3), (1, 4), (2, 8), (2, 9)]

Algoritam za ispitivanje acikličnosti grafa

Implementacija algoritam za ispitivanje acikličnosti grafa se temelji na BFS algoritmu, a zapravo je samo mala modifikacija ranije implementiranog algoritma za računanje struka grafa. Formalno, možemo primijeniti algoritam za računanje struka grafa. Ako je struk grafa manji od $\infty$, tada je graf ciklički, a u protivnom je aciklički. Kako nas kod ispitivanja cikličnosti ne zanima duljina najkraćeg ciklusa, možemo taj algoritam i ranije prekinuti ukoliko dođemo do informacije da postoji u grafu neki ciklus koji možda nije najmanje duljine.

In [88]:
DSTG.is_acyclic(gr)
Out[88]:
False
In [89]:
DSTG.is_acyclic(G)
Out[89]:
False
In [90]:
DSTG.is_acyclic(nx.path_graph(8))
Out[90]:
True

Algoritam za traženje ciklusa u grafu

Postoji gotova naredba za pronalaženje nekog ciklusa u grafu koja na izlazu daje listu bridova pronađenog ciklusa.

In [91]:
nx.find_cycle(gr)
Out[91]:
[(1, 3), (3, 4), (4, 5), (5, 1)]
In [92]:
nx.find_cycle(G)
Out[92]:
[(4, 2), (2, 5), (5, 4)]

Implementacija funkcije random_cycle za traženje nekog ciklusa u grafu temelji se na DFS algoritmu. Algoritam je randomiziran tako da višestrukim pokretanjem na istom grafu daje općenito različite cikluse.

Također, dana je implementacija DFS algoritma pomoću stoga. Funkcija dfs_graf na izlazu daje uređenu šestorku: listu redom posjećivanih vrhova, rječnik trenutaka u kojima su pojedini vrhovi prvi put posjećeni, rječnik trenutaka u kojima je završeno istraživanje pojedinih vrhova, rječnik neposrednih prethodnika svakog vrha, listu bridova koji pripadaju pronađenom razapinjućem stablu i listu preostalih bridova grafa koji nisu u pronađenom razapinjućem stablu.

Uočite kako se višestrukim pokretanjem funkcije find_cycle na donjem grafu dobivaju na izlazu općenito različiti ciklusi u tom grafu.

In [93]:
for k in range(20):
    print(DSTG.random_cycle(gr))

[3, 1, 5, 8, 7, 4, 3]
[1, 3, 6, 7, 8, 5, 1]
[1, 3, 6, 7, 8, 5, 1]
[4, 3, 6, 7, 8, 5, 4]
[4, 3, 6, 7, 4]
[3, 6, 7, 8, 5, 4, 3]
[4, 5, 8, 7, 4]
[5, 4, 3, 6, 7, 8, 5]
[5, 4, 3, 6, 7, 8, 5]
[4, 7, 8, 5, 4]
[1, 5, 8, 7, 6, 3, 1]
[5, 4, 3, 6, 7, 8, 5]
[1, 3, 4, 5, 1]
[4, 5, 8, 7, 4]
[4, 3, 6, 7, 4]
[4, 3, 6, 7, 4]
[1, 3, 4, 5, 1]
[1, 3, 6, 7, 8, 5, 1]
[1, 5, 8, 7, 6, 3, 1]
[1, 3, 4, 5, 1]
In [94]:
DSTG.dfs_graf(gr,3)
Out[94]:
([3, 6, 7, 8, 5, 4, 2, 1],
 {3: 1, 6: 2, 7: 3, 8: 4, 5: 5, 4: 6, 2: 8, 1: 10},
 {4: 7, 2: 9, 1: 11, 5: 12, 8: 13, 7: 14, 6: 15, 3: 16},
 {3: None, 1: 5, 2: 5, 4: 5, 5: 8, 6: 3, 7: 6, 8: 7},
 [(6, 3), (7, 6), (8, 7), (5, 8), (4, 5), (2, 5), (1, 5)],
 [(1, 3), (3, 4), (4, 7)])
In [95]:
DSTG.dfs_graf(gr,1)
Out[95]:
([1, 5, 8, 7, 6, 3, 4, 2],
 {1: 1, 5: 2, 8: 3, 7: 4, 6: 5, 3: 6, 4: 7, 2: 13},
 {4: 8, 3: 9, 6: 10, 7: 11, 8: 12, 2: 14, 5: 15, 1: 16},
 {1: None, 2: 5, 3: 6, 4: 3, 5: 1, 6: 7, 7: 8, 8: 5},
 [(5, 1), (8, 5), (7, 8), (6, 7), (3, 6), (4, 3), (2, 5)],
 [(1, 3), (4, 5), (4, 7)])

Ako želimo pronađeni ciklus istaknuti na grafu

In [96]:
figure(figsize=(5,5))
DSTG.random_cycle_graph(gr,pozicije,velicinaVrha=500,rubVrha='k')
In [97]:
figure(figsize=(5,5))
DSTG.random_cycle_graph(gr,pozicije,velicinaVrha=500,rubVrha='k')

Kruskalov i Primov algoritam

In [98]:
graf=nx.Graph()
graf.add_weighted_edges_from([("A","B",6),("A","D",2),("A","E",9),("A","S",7),
              ("B","C",2),("B","E",3),("B","S",9), ("C","E",2),("C","F",6),("C","S",1),
              ("D","E",5),("D","T",3),("E","F",7),("E","T",9),("F","T",6)])
In [99]:
pozicijeGraf={"A":[2,4],"B":[2,2],"C":[2,0],"D":[4,4],"E":[4,2],"F":[4,0],"S":[0,2],"T":[6,2]}
In [100]:
figure(figsize=(8,5))
DSTG.CrtajTezinskiGraf(graf,pozicijeGraf,velicinaVrha=500,rubVrha='k')

minimalno stablo dobiveno Kruskalovim algoritmom

In [101]:
nx.draw(nx.minimum_spanning_tree(graf),with_labels=True,node_color='y',edgecolors='k')

bridovi minimalnog stabla dobivenog Kruskalovim algoritmom

In [102]:
list(nx.minimum_spanning_edges(graf))
Out[102]:
[('S', 'C', {'weight': 1}),
 ('A', 'D', {'weight': 2}),
 ('B', 'C', {'weight': 2}),
 ('E', 'C', {'weight': 2}),
 ('D', 'T', {'weight': 3}),
 ('D', 'E', {'weight': 5}),
 ('C', 'F', {'weight': 6})]

Minimalno Kruskal stablo istaknuto na grafu

In [103]:
DSTG.KruskalStablo(graf,pozicijeGraf,velicinaVrha=500,rubVrha='k')

Maksimalno Kruskal stablo istaknuto na grafu

In [104]:
DSTG.KruskalStablo(graf,pozicijeGraf,opcija='max',velicinaVrha=500,rubVrha='k')
In [105]:
list(nx.maximum_spanning_edges(graf))
Out[105]:
[('A', 'E', {'weight': 9}),
 ('B', 'S', {'weight': 9}),
 ('E', 'T', {'weight': 9}),
 ('A', 'S', {'weight': 7}),
 ('E', 'F', {'weight': 7}),
 ('C', 'F', {'weight': 6}),
 ('D', 'E', {'weight': 5})]

Minimalno Kruskal stablo kao korijensko stablo s korijenom "A"

In [106]:
figure(figsize=(5,6))
DSTG.KruskalKorijenskoStablo(graf,"A",velicinaVrha=500,rubVrha='k')

Minimalno Kruskal stablo kao korijensko stablo s korijenom "B"

In [107]:
figure(figsize=(5,6))
DSTG.KruskalKorijenskoStablo(graf,"B",velicinaVrha=500,rubVrha='k')

Maksimalno Kruskal stablo kao korijensko stablo s korijenom "A"

In [108]:
figure(figsize=(7,5))
DSTG.KruskalKorijenskoStablo(graf,"A",opcija='max',velicinaVrha=500,rubVrha='k')

Maksimalno Kruskal stablo kao korijensko stablo s korijenom "B"

In [109]:
figure(figsize=(7,7))
DSTG.KruskalKorijenskoStablo(graf,"B",opcija='max',velicinaVrha=500,rubVrha='k')

minimalno stablo dobiveno Primovim algoritmom

In [110]:
figure(figsize=(7,5))
nx.draw(nx.minimum_spanning_tree(graf,algorithm='prim'),with_labels=True,node_color='y',edgecolors='k')

bridovi minimalnog stabla dobivenog Primovim algoritmom

In [111]:
list(nx.minimum_spanning_edges(graf,algorithm='prim'))
Out[111]:
[('A', 'D', {'weight': 2}),
 ('D', 'T', {'weight': 3}),
 ('D', 'E', {'weight': 5}),
 ('E', 'C', {'weight': 2}),
 ('C', 'S', {'weight': 1}),
 ('C', 'B', {'weight': 2}),
 ('T', 'F', {'weight': 6})]

implementacija Primovog algoritma koja dozvoljava da biramo početni vrh

In [112]:
DSTG.prim_alg_min(graf,"A")
Out[112]:
[('A', 'D', 2),
 ('D', 'T', 3),
 ('D', 'E', 5),
 ('E', 'C', 2),
 ('C', 'S', 1),
 ('C', 'B', 2),
 ('T', 'F', 6)]
In [113]:
DSTG.prim_alg_min(graf,"B")
Out[113]:
[('B', 'C', 2),
 ('C', 'S', 1),
 ('C', 'E', 2),
 ('E', 'D', 5),
 ('D', 'A', 2),
 ('D', 'T', 3),
 ('C', 'F', 6)]
In [114]:
DSTG.PrimStablo(graf,"A",pozicijeGraf,velicinaVrha=500,rubVrha='k')
In [115]:
DSTG.PrimStablo(graf,"B",pozicijeGraf,velicinaVrha=500,rubVrha='k')
In [116]:
DSTG.prim_alg_max(graf,"A")
Out[116]:
[('A', 'E', 9),
 ('E', 'T', 9),
 ('A', 'S', 7),
 ('S', 'B', 9),
 ('E', 'F', 7),
 ('F', 'C', 6),
 ('E', 'D', 5)]
In [117]:
DSTG.PrimStablo(graf,"A",pozicijeGraf,opcija='max',velicinaVrha=500,rubVrha='k')
In [118]:
DSTG.PrimKorijenskoStablo(graf,"A",opcija='max',velicinaVrha=500,rubVrha='k')

Ručni Kruskal i Prim

In [119]:
DSTG.rucni_Kruskal(graf)

tezina stabla:  21
Out[119]:
korak1234567
brid('S', 'C')('A', 'D')('B', 'C')('E', 'C')('D', 'T')('D', 'E')('C', 'F')
tezina1222356
In [120]:
DSTG.rucni_Kruskal(graf,'max')

tezina stabla:  52
Out[120]:
korak1234567
brid('A', 'E')('B', 'S')('E', 'T')('A', 'S')('E', 'F')('C', 'F')('D', 'E')
tezina9997765
In [121]:
DSTG.rucni_Prim(graf,"B")

tezina stabla:  21
Out[121]:
B | korak1234567
brid('B', 'C')('C', 'S')('C', 'E')('E', 'D')('D', 'A')('D', 'T')('C', 'F')
tezina2125236
In [122]:
DSTG.rucni_Prim(graf,"B",'max')

tezina stabla:  52
Out[122]:
B | korak1234567
brid('B', 'S')('S', 'A')('A', 'E')('E', 'T')('E', 'F')('F', 'C')('E', 'D')
tezina9799765
In [ ]: