Stabla u SAGE-u

In [1]:
import sage.misc.banner
banner()
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.8.6. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘

neka već definirana stabla u SAGE-u

BalancedTree

In [2]:
graphs.BalancedTree(3,2).show()
In [3]:
graphs.BalancedTree(2,3).show()

stablo nacrtano kao korijensko stablo

In [4]:
graphs.BalancedTree(3,2).show(layout="tree",tree_root=0)
In [5]:
graphs.BalancedTree(3,2).show(layout="tree",tree_root=8)
In [6]:
graphs.BalancedTree(3,2).show(layout="tree",tree_root=1,tree_orientation="up")
In [7]:
graphs.BalancedTree(2,3).show(layout="tree",tree_root=0)
In [8]:
graphs.BalancedTree(2,3).show(layout="tree",tree_root=4)

FibonacciTree

In [9]:
graphs.FibonacciTree(4).show()
In [10]:
graphs.FibonacciTree(8).show(figsize=(12,10),vertex_size=400)

PathGraph

In [11]:
graphs.PathGraph(8).show()
In [12]:
graphs.PathGraph(20).show()

StarGraph

In [13]:
graphs.StarGraph(7).show()
In [14]:
graphs.StarGraph(19).show(vertex_size=400)

DegreeSequenceTree

In [15]:
graphs.DegreeSequenceTree([2,1,2,3,1,1,1,2,1,4]).show(graph_border=True)
In [16]:
graphs.DegreeSequenceTree([3,1,3,3,1,1,1,2,1]).show(graph_border=True)

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$

graphs.trees

sva neizomorfna stabla sa 5 vrha

In [17]:
graphs_list.show_graphs(list(graphs.trees(5)))

sva neizomorfna stabla sa 7 vrhova

In [18]:
graphs_list.show_graphs(list(graphs.trees(7)))

šuma

In [19]:
stablo1=graphs.PathGraph(5)
stablo2=graphs.StarGraph(7)
graf=stablo1.disjoint_union(stablo2)
graf.show(vertex_labels=False,graph_border=True,vertex_size=80)
In [20]:
graf.is_forest()
Out[20]:
True
In [21]:
graf.is_tree()
Out[21]:
False

Kontrakcija brida

ako ne dozvolimo višestruke bridove u grafu

In [22]:
G1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[0,0],2:[2,0],3:[2,2],4:[0,2]}
G2=G1.copy()
G2.merge_vertices([1,5])
graphics_array([G1.plot(pos=pozicije1,graph_border=True),G2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])

ako dozvolimo višestruke bridove u grafu

In [23]:
H1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[0.5,0.5],2:[2,0],3:[2,2],4:[0,2]}
H2=H1.copy()
H2.allow_multiple_edges(True)
H2.merge_vertices([1,5])
graphics_array([H1.plot(pos=pozicije1,graph_border=True),H2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])

općenitije, možemo istovremeno i više vrhova poistovjetiti

In [24]:
T1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[1,1],2:[2,0],4:[0,2]}
T2=T1.copy()
T2.allow_multiple_edges(True)
T2.merge_vertices([1,3,5])
graphics_array([T1.plot(pos=pozicije1,graph_border=True),T2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])

Razapinjuća stabla grafa

1. primjer

In [25]:
graf1=Graph({1:[2,4],2:[3,4],3:[4]})
poz1={1:[0,0],2:[1,0],3:[1,1],4:[0,1]}
graf1.show(pos=poz1,figsize=[3,3])

ukupni broj razapinjućih stabala grafa

In [26]:
graf1.spanning_trees_count()
Out[26]:
8

neko razapinjuće stablo grafa

In [27]:
graf1.edge_disjoint_spanning_trees(1)
Out[27]:
[Graph on 4 vertices]
In [28]:
graf1.edge_disjoint_spanning_trees(1)[0].show(pos=poz1,figsize=[3,3])

promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla

In [29]:
graf1.edge_disjoint_spanning_trees(2)
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6380         try:
-> 6381             p.solve(log=verbose)
   6382 

/usr/lib/python3.8/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:15621)()
   2250         if log is not None: self._backend.set_verbosity(log)
-> 2251         self._backend.solve()
   2252         return self._backend.get_objective_value()

/usr/lib/python3.8/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:10221)()
   1151         else:
-> 1152             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
   1153         return 0

MIPSolverException: GLPK: Problem has no feasible solution

During handling of the above exception, another exception occurred:

EmptySetError                             Traceback (most recent call last)
<ipython-input-29-be8f1f954363> in <module>
----> 1 graf1.edge_disjoint_spanning_trees(Integer(2))

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6383         except MIPSolverException:
   6384             from sage.categories.sets_cat import EmptySetError
-> 6385             raise EmptySetError("this graph does not contain the required number of trees/arborescences")
   6386 
   6387         edges = p.get_values(edges)

EmptySetError: this graph does not contain the required number of trees/arborescences

matrični teorem o stablima

In [30]:
graf1.kirchhoff_matrix()
Out[30]:
[ 2 -1  0 -1]
[-1  3 -1 -1]
[ 0 -1  2 -1]
[-1 -1 -1  3]

svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu

In [31]:
graf1.kirchhoff_matrix().adjugate()
Out[31]:
[8 8 8 8]
[8 8 8 8]
[8 8 8 8]
[8 8 8 8]

2. primjer

In [32]:
graf2=graphs.CompleteBipartiteGraph(2,3)
poz2={0:[0,1.5],1:[0,0.5],2:[2,2],3:[2,1],4:[2,0]}
graf2.show(pos=poz2,figsize=[3,3])

ukupni broj razapinjućih stabala grafa

In [33]:
graf2.spanning_trees_count()
Out[33]:
12

neko razapinjuće stablo grafa

In [34]:
graf2.edge_disjoint_spanning_trees(1)
Out[34]:
[Graph on 5 vertices]
In [35]:
graf2.edge_disjoint_spanning_trees(1)[0].show(pos=poz2,figsize=[3,3])

promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla

In [36]:
graf2.edge_disjoint_spanning_trees(2)
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6380         try:
-> 6381             p.solve(log=verbose)
   6382 

/usr/lib/python3.8/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:15621)()
   2250         if log is not None: self._backend.set_verbosity(log)
-> 2251         self._backend.solve()
   2252         return self._backend.get_objective_value()

/usr/lib/python3.8/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:10221)()
   1151         else:
-> 1152             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
   1153         return 0

MIPSolverException: GLPK: Problem has no feasible solution

During handling of the above exception, another exception occurred:

EmptySetError                             Traceback (most recent call last)
<ipython-input-36-ef82c01ea2c8> in <module>
----> 1 graf2.edge_disjoint_spanning_trees(Integer(2))

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6383         except MIPSolverException:
   6384             from sage.categories.sets_cat import EmptySetError
-> 6385             raise EmptySetError("this graph does not contain the required number of trees/arborescences")
   6386 
   6387         edges = p.get_values(edges)

EmptySetError: this graph does not contain the required number of trees/arborescences

matrični teorem o stablima

In [37]:
graf2.kirchhoff_matrix()
Out[37]:
[ 3  0 -1 -1 -1]
[ 0  3 -1 -1 -1]
[-1 -1  2  0  0]
[-1 -1  0  2  0]
[-1 -1  0  0  2]

svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu

In [38]:
graf2.kirchhoff_matrix().adjugate()
Out[38]:
[12 12 12 12 12]
[12 12 12 12 12]
[12 12 12 12 12]
[12 12 12 12 12]
[12 12 12 12 12]

3. primjer

In [39]:
graf3=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]}
graf3.show(pos=poz3,figsize=[3,3])

ukupni broj razapinjućih stabala grafa

In [40]:
graf3.spanning_trees_count()
Out[40]:
24

neko razapinjuće stablo grafa

In [41]:
graf3.edge_disjoint_spanning_trees(1)
Out[41]:
[Graph on 5 vertices]
In [42]:
graf3.edge_disjoint_spanning_trees(1)[0].show(pos=poz3,figsize=[3,3])

promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla

In [43]:
graf3.edge_disjoint_spanning_trees(2)
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6380         try:
-> 6381             p.solve(log=verbose)
   6382 

/usr/lib/python3.8/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:15621)()
   2250         if log is not None: self._backend.set_verbosity(log)
-> 2251         self._backend.solve()
   2252         return self._backend.get_objective_value()

/usr/lib/python3.8/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:10221)()
   1151         else:
-> 1152             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
   1153         return 0

MIPSolverException: GLPK: Problem has no feasible solution

During handling of the above exception, another exception occurred:

EmptySetError                             Traceback (most recent call last)
<ipython-input-43-e6bbc2e65ed6> in <module>
----> 1 graf3.edge_disjoint_spanning_trees(Integer(2))

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6383         except MIPSolverException:
   6384             from sage.categories.sets_cat import EmptySetError
-> 6385             raise EmptySetError("this graph does not contain the required number of trees/arborescences")
   6386 
   6387         edges = p.get_values(edges)

EmptySetError: this graph does not contain the required number of trees/arborescences

matrični teorem o stablima

In [44]:
graf3.kirchhoff_matrix()
Out[44]:
[ 3 -1  0 -1 -1]
[-1  3 -1  0 -1]
[ 0 -1  2 -1  0]
[-1  0 -1  3 -1]
[-1 -1  0 -1  3]

svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu

In [45]:
graf3.kirchhoff_matrix().adjugate()
Out[45]:
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]

4. primjer

In [46]:
graf4=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]}
graf4.show(pos=poz4,figsize=[3,3])

ukupni broj razapinjućih stabala grafa

In [47]:
graf4.spanning_trees_count()
Out[47]:
95

neko razapinjuće stablo grafa

In [48]:
graf4.edge_disjoint_spanning_trees(1)
Out[48]:
[Graph on 7 vertices]
In [49]:
graf4.edge_disjoint_spanning_trees(1)[0].show(pos=poz4,figsize=[3,3])

promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla

In [50]:
graf4.edge_disjoint_spanning_trees(2)
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6380         try:
-> 6381             p.solve(log=verbose)
   6382 

/usr/lib/python3.8/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:15621)()
   2250         if log is not None: self._backend.set_verbosity(log)
-> 2251         self._backend.solve()
   2252         return self._backend.get_objective_value()

/usr/lib/python3.8/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:10221)()
   1151         else:
-> 1152             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
   1153         return 0

MIPSolverException: GLPK: Problem has no feasible solution

During handling of the above exception, another exception occurred:

EmptySetError                             Traceback (most recent call last)
<ipython-input-50-9276bf5b563f> in <module>
----> 1 graf4.edge_disjoint_spanning_trees(Integer(2))

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6383         except MIPSolverException:
   6384             from sage.categories.sets_cat import EmptySetError
-> 6385             raise EmptySetError("this graph does not contain the required number of trees/arborescences")
   6386 
   6387         edges = p.get_values(edges)

EmptySetError: this graph does not contain the required number of trees/arborescences

matrični teorem o stablima

In [51]:
graf4.kirchhoff_matrix()
Out[51]:
[ 2 -1  0 -1  0  0  0]
[-1  3 -1  0 -1  0  0]
[ 0 -1  2  0  0 -1  0]
[-1  0  0  3 -1  0 -1]
[ 0 -1  0 -1  4 -1 -1]
[ 0  0 -1  0 -1  3 -1]
[ 0  0  0 -1 -1 -1  3]

svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu

In [52]:
graf4.kirchhoff_matrix().adjugate()
Out[52]:
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]
[95 95 95 95 95 95 95]

5. primjer

In [53]:
graf5=Graph({1:[2,2,2,4,4,4],2:[3,3,3],3:[4,4,4],4:[5,5,5]})
poz5={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[-2,2]}
graf5.show(pos=poz5,ymax=2.1,ymin=-0.1)

ukupni broj razapinjućih stabala grafa

In [54]:
graf5.spanning_trees_count()
Out[54]:
324

neko razapinjuće stablo - ne radi baš dobro na grafovima koji nisu jednostavni

In [55]:
graf5.edge_disjoint_spanning_trees(1)[0]
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-55-5677c20bf183> in <module>
----> 1 graf5.edge_disjoint_spanning_trees(Integer(1))[Integer(0)]

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in edge_disjoint_spanning_trees(self, k, root, solver, verbose)
   6394 
   6395             if len(list(g.breadth_first_search(root))) != self.order():
-> 6396                 raise RuntimeError("The computation seems to have gone wrong somewhere..."+
   6397                                    "This is probably because of the value of epsilon, but"+
   6398                                    " in any case please report this bug, with the graph "+

RuntimeError: The computation seems to have gone wrong somewhere...This is probably because of the value of epsilon, but in any case please report this bug, with the graph that produced it ! ;-)

matrični teorem o stablima

In [56]:
graf5.kirchhoff_matrix()
Out[56]:
[ 6 -3  0 -3  0]
[-3  6 -3  0  0]
[ 0 -3  6 -3  0]
[-3  0 -3  9 -3]
[ 0  0  0 -3  3]

svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu

In [57]:
graf5.kirchhoff_matrix().adjugate()
Out[57]:
[324 324 324 324 324]
[324 324 324 324 324]
[324 324 324 324 324]
[324 324 324 324 324]
[324 324 324 324 324]

6. primjer

In [58]:
graphs.CompleteGraph(6).show(layout="circular",figsize=[3,3])
In [59]:
graphs.CompleteGraph(6).spanning_trees_count()
Out[59]:
1296

$K_6$ ima tri po bridovima disjunktna razapinjuća stabla

In [60]:
graphs.CompleteGraph(6).edge_disjoint_spanning_trees(3)
Out[60]:
[Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices]
In [61]:
graphs_list.show_graphs(graphs.CompleteGraph(6).edge_disjoint_spanning_trees(3))

DFS i BFS algoritam

In [62]:
gr=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]}
gr.show(pos=pozicije,figsize=[3,3])

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

In [63]:
gr.depth_first_search(1)
Out[63]:
<generator object GenericGraph.depth_first_search at 0x7f9db77545f0>
In [64]:
list(gr.depth_first_search(1))
Out[64]:
[1, 5, 8, 7, 6, 3, 4, 2]

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

In [65]:
list(gr.depth_first_search(4))
Out[65]:
[4, 7, 8, 5, 2, 1, 3, 6]

Ako želimo dobiti i bridove koji se nalaze u DFS-stablu, implementirat ćemo svoju funkciju. Za svaki vrh $v$, $d[v]$ mjeri u kojem koraku je vrh $v$ prvi puta posjećen, a $f[v]$ mjeri u kojem koraku je završeno posjećivanje svih susjeda vrha $v$. Vrhove bojamo s tri boje: WHITE, GRAY i BLACK. Vrh $v$ je WHITE prije koraka $d[v]$, GRAY između koraka $d[v]$ i $f[v]$, a BLACK nakon koraka $d[v]$. Prethodnik vrha $v$ u DFS-stablu je vrh $P[v]$. Iako nama u ovom trenutku nisu možda potrebne sve navedene varijable, DFS algoritam je ipak implementiran u ovolikoj općenitosti jer je on osnova za neke druge algoritme u kojima spomenute varijable mogu biti od neizmjerne važnosti. Također, dolje je dana rekurzivna implementacija DFS algortima, a za vježbu možete pokušati implementirati nerekurzivnu verziju u kojoj ćete koristiti stog. Za detalje pogledajte knjigu Introduction to Algorithms od autora Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein.

In [66]:
def DFS(G,v0):
    global time
    V=G.vertices()
    V.remove(v0)
    vrhovi=[v0]+V
    color={}
    d={}
    f={}
    P={}
    time=0    
    def DFS_posjet(u):
        global time
        color[u]="GRAY"
        time=time+1
        d[u]=time
        for v in G[u]:
            if color[v]=="WHITE":
                P[v]=u
                DFS_posjet(v)
        color[u]="BLACK"
        time=time+1
        f[u]=time
    for u in vrhovi:
        color[u]="WHITE"
        P[u]=None
    for u in vrhovi:
        if color[u]=="WHITE":
            DFS_posjet(u)
    redoslijed_vrhova=sorted(G.vertices(),key=lambda x: d[x])
    bridovi=[]
    for u in redoslijed_vrhova:
        if P[u]!=None:
            if (u,P[u]) in G.edges(labels=False):
                bridovi.append((u,P[u]))
            else:
                bridovi.append((P[u],u))
    return (redoslijed_vrhova,bridovi,d,f)
In [67]:
DFS(gr,1)
Out[67]:
([1, 3, 4, 5, 2, 8, 7, 6],
 [(3, 1), (4, 3), (5, 4), (2, 5), (8, 5), (7, 8), (6, 7)],
 {1: 1, 3: 2, 4: 3, 5: 4, 2: 5, 8: 7, 7: 8, 6: 9},
 {2: 6, 6: 10, 7: 11, 8: 12, 5: 13, 4: 14, 3: 15, 1: 16})
In [68]:
DFS(gr,4)
Out[68]:
([4, 3, 1, 5, 2, 8, 7, 6],
 [(3, 4), (1, 3), (5, 1), (2, 5), (8, 5), (7, 8), (6, 7)],
 {4: 1, 3: 2, 1: 3, 5: 4, 2: 5, 8: 7, 7: 8, 6: 9},
 {2: 6, 6: 10, 7: 11, 8: 12, 5: 13, 1: 14, 3: 15, 4: 16})

Sada možemo bez problema definirati i funkciju koja će pronađeno DFS-stablo istaknuti na grafu

In [69]:
def DFS_graf(G,v0,raspored_vrhova=None,lay="circular",bojaBridova="red",boja_v0="yellow"):
    podaci=DFS(G,v0)
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},layout=laj)
    else:
        slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},pos=raspored_vrhova)
    return slika
In [70]:
DFS_graf(gr,1,raspored_vrhova=pozicije,boja_v0="red").show(figsize=[3,3])
In [71]:
DFS_graf(gr,4,raspored_vrhova=pozicije).show(figsize=[3,3])

Animacija DFS-stabla s početkom u vrhu 4

Neposjećeni vrhovi su obojani crvenom bojom. Nakon što je vrh posjećen, obojan je sa žutom bojom, a nakon što je se iz njega ne može više dalje prema novim neposjećenim vrhovima, obojan je zelenom bojom. Bridovi koji se postupeno dodaju u DFS stablo, obojani su crvenom bojom.

In [72]:
rjecnik1=DFS(gr,4)[2]
rjecnik2=DFS(gr,4)[3]
bridovi=DFS(gr,4)[1]
algoritam=sorted(list(map(lambda x: (x[0],[x[1],'d']),map(lambda x: (x[1],x[0]), rjecnik1.items()))) + list(map(lambda x: (x[0],[x[1],'f']),
                map(lambda x: (x[1],x[0]), rjecnik2.items()))))
def boja_vrha(korak):
    lista=algoritam[0:korak]
    boje={"yellow":[],"green":[]}
    for x in lista:
        if x[1][1]=='d':
            boje["yellow"].append(x[1][0])
        else:
            boje["yellow"].remove(x[1][0])
            boje["green"].append(x[1][0])
    return boje
def boja_brida(korak):
    if korak==1: return {}
    if korak>=11: return {"red":bridovi}
    if (korak>1) and (korak<6):
        return {"red":bridovi[0:korak-1]}
    if (korak==6):
        return {"red":bridovi[0:4]}
    if (korak>=7) or (korak<=9):
        return {"red":bridovi[0:korak-2]}
    if (korak==10):
        return {"red":bridovi[0:-1]}
aDSF=animate([gr.plot(edge_colors=boja_brida(k),vertex_colors=boja_vrha(k),pos=pozicije,graph_border=True,
                      figsize=[3,3]) for k in srange(1,len(algoritam)+1,1)])
aDSF.show(delay=150,iterations=0)

interaktivno proučavanje pojedinog koraka DFS algoritma

In [73]:
rjecnik1=DFS(gr,4)[2]
rjecnik2=DFS(gr,4)[3]
bridovi=DFS(gr,4)[1]
algoritam=sorted(list(map(lambda x: (x[0],[x[1],'d']),map(lambda x: (x[1],x[0]), rjecnik1.items()))) + list(map(lambda x: (x[0],[x[1],'f']),
            map(lambda x: (x[1],x[0]), rjecnik2.items()))))
def boja_vrha(korak):
    lista=algoritam[0:korak]
    boje={"yellow":[],"green":[]}
    for x in lista:
        if x[1][1]=='d':
            boje["yellow"].append(x[1][0])
        else:
            boje["yellow"].remove(x[1][0])
            boje["green"].append(x[1][0])
    return boje
def boja_brida(korak):
    if korak==1: return {}
    if korak>=11: return {"red":bridovi}
    if (korak>1) and (korak<8):
        return {"red":bridovi[0:korak-1]}
    if (korak>=8) and (korak<11):
        return {"red":bridovi[0:-1]}
d=len(algoritam)
@interact
def _(k=selector([1..d],nrows=1)):
    gr.plot(edge_colors=boja_brida(k),vertex_colors=boja_vrha(k),pos=pozicije,graph_border=True).show(figsize=[4,4])

BFS algoritam daje redoslijed posjećivanja vrhova počevši od vrha "1"

In [74]:
gr.breadth_first_search(1)
Out[74]:
<generator object GenericGraph.breadth_first_search at 0x7f9db77512e0>
In [75]:
list(gr.breadth_first_search(1))
Out[75]:
[1, 3, 5, 4, 6, 2, 8, 7]

BFS algoritam daje redoslijed posjećivanja vrhova počevši od vrha "4"

In [76]:
list(gr.breadth_first_search(4))
Out[76]:
[4, 3, 5, 7, 1, 6, 2, 8]

Ako želimo dobiti i bridove koji se nalaze u BFS-stablu, implementirat ćemo svoju funkciju. Za svaki vrh $v$, $d[v]$ mjeri udaljenost vrha $v$ od početnog vrha $v_0$ s kojim algoritam započinje. Vrhove bojamo s tri boje: WHITE, GRAY i BLACK. Neposjećeni vrhovi su obojani bojom WHITE, posjećeni vrhovi bojom GRAY, a ukoliko su posjećenom vrhu posjećeni i svi njegovi susjedi, tada je on obojan bojom BLACK. Prethodnik vrha $v$ u BFS-stablu je vrh $P[v]$. Za detalje pogledajte knjigu Introduction to Algorithms od autora Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein.

In [77]:
def BFS(G,v0):
    V=G.vertices()
    V.remove(v0)
    color={}
    P={}
    d={}
    for u in V:
        color[u]="WHITE"
        d[u]=Infinity
        P[u]=None
    color[v0]="GRAY"
    d[v0]=0
    P[v0]=None
    Q=[]
    Q.append(v0)
    redoslijed_vrhova=[v0]
    while Q!=[]:
        u=Q.pop(0)
        for v in G[u]:
            if color[v]=="WHITE":
                color[v]="GRAY"
                d[v]=d[u]+1
                P[v]=u
                Q.append(v)
                redoslijed_vrhova.append(v)
        color[u]="BLACK"
    bridovi=[]
    for u in redoslijed_vrhova:
        if P[u]!=None:
            if (u,P[u]) in G.edges(labels=False):
                bridovi.append((u,P[u]))
            else:
                bridovi.append((P[u],u))
    return (redoslijed_vrhova,bridovi,d)
In [78]:
BFS(gr,1)
Out[78]:
([1, 3, 5, 4, 6, 2, 8, 7],
 [(3, 1), (5, 1), (4, 3), (6, 3), (2, 5), (8, 5), (7, 4)],
 {2: 2, 3: 1, 4: 2, 5: 1, 6: 2, 7: 3, 8: 2, 1: 0})
In [79]:
BFS(gr,4)
Out[79]:
([4, 3, 5, 7, 1, 6, 2, 8],
 [(3, 4), (5, 4), (7, 4), (1, 3), (6, 3), (2, 5), (8, 5)],
 {1: 2, 2: 2, 3: 1, 5: 1, 6: 2, 7: 1, 8: 2, 4: 0})

Sada možemo bez problema definirati i funkciju koja će pronađeno BFS-stablo istaknuti na grafu

In [80]:
def BFS_graf(G,v0,raspored_vrhova=None,lay="circular",bojaBridova="red",boja_v0="yellow"):
    podaci=BFS(G,v0)
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},layout=laj)
    else:
        slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},pos=raspored_vrhova)
    return slika
In [81]:
BFS_graf(gr,1,raspored_vrhova=pozicije).show(figsize=[3,3])
In [82]:
BFS_graf(gr,4,raspored_vrhova=pozicije).show(figsize=[3,3])

Animacija BFS-stabla s početkom u vrhu 4

In [83]:
alg=BFS(gr,4)
aBFS=animate([gr.plot(pos=pozicije,graph_border=True,figsize=[3,3],edge_colors={"red":alg[1][0:k-1]},
                      vertex_colors={"yellow":alg[0][0:k]}) for k in srange(1,len(alg[0])+1,1)])
aBFS.show(delay=150,iterations=0)

interaktivno proučavanje pojedinog koraka u BFS algoritmu

In [84]:
alg=BFS(gr,4)
@interact
def _(korak=selector([1..len(alg[0])],nrows=1)):
    gr.plot(pos=pozicije,graph_border=True,edge_colors={"red":alg[1][0:korak-1]},
            vertex_colors={"yellow":alg[0][0:korak]}).show(figsize=[4,4])
In [ ]: